引言

我发现在以前的回溯算法中,很少提到链表的使用,虽然 Dancing link 算法已经用的炉火纯青了,但介绍它属于是“跳级”了,咱们既然从零单排回溯算法,那还要从链表在回溯中的简单用法讲起,这就要提 Langford 对的生成了。

Langford 对是一个组合数学中的概念。给定一个正整数 ,Langford 对是将数字 1 到 n 的每个数字重复两次,并以一种特定的方式排列,使得两个相同的数字之间恰好间隔等于该数字的位置数。 例如,对于 n=4,一种可能的 Langford 对排列是 23421314。在这里,每个数字重复两次,且两个 1 之间间隔 1 个位置;两个 2 之间间隔 2 个位置;以此类推。

Read more


引言

如果你看懂了上一篇的回溯基本法,那这篇更是小菜一碟,我将尝试在 read more 之前讲明白它。

相比基本法每次尝试是从$D_l$依次取一个然后验证,如果为假则剪枝,否则即等待成立,Walker 则从另一个角度出发,每次从$S_l$取完最小元素$x_l$后,直接更新下次的 $S_{l+1}$,把不符合条件从集合中删掉,然后接着往下走直到$l>n$。回溯时则直接令$S_l\leftarrow S_l \backslash x_l$ 去除$x_l$,然后接着选下一个。

Read more


引言

当我要介绍 Knuth 在 23 年圣诞节时的演讲 Dancing cell 时,我发现我缺少了太多的上下文,算法虽然不难讲清楚,但为什么要这么做,这个算法有什么应用价值我并不清楚,视频中提到了这是从 Knuth 的经典著作《The Art of Computer Programming》(TAOCP)第 7 章开始的。出于好奇,我翻看了整个第 7 章,发现整章都在讲述回溯算法(Backtrack),包括我之前提到的 Dancing Link 实际上是一个比较优化的算法。

Read more



引言

我在翻看 Knuth 最近的更新时,发现他每年圣诞节都会跑到斯坦福去做演讲,去年我也写(ken)了他的圣诞三重奏, 2023年圣诞的主题是 Dancing Cell,我瞅了一眼,发现要搞懂这个就得先弄明白 Dancing Link。这个算法我早在 2011 年就听说过,只晓得用它解数独超快,但具体咋做、我也从来没实现过。所以呀,我决定先从 Dancing Link 开始学起。

Read more