Peter Norvig:用 Python 解决数独问题

697 查看

在这篇文章中,我要处理求解任意数独这个问题。用了两个想法(idea):约束传播搜索后,它其实是很简单的(主旨大约只有一页代码,加上润色后也不过两页)。

数独记号和初步概念

首先我们要在记号上达成一致。一个数独谜题是由 81 个方块组成的网格。大部分爱好者把列标为 1-9,把行标为 A-I,把 9 个方块的一组(列,行,或者方框)称为一个单元,把处于同一单元的方块称为对等方块。谜题中有些方块是空白的,其他的填入了数字。谜题的主旨是这样的:

当每个单元的方块填入了 1 到 9 的一个排列时,谜题就解决了。

也就是说,在一个单元中,任何数字都不能出现两次,而且每个数字都要出现一次。这意味着每个方块的值和它的对等方块的值是不同的。下面是方块的名字、一个典型的谜题及其解答:

每个方块都属于 3 个单元,有 20 个对等方块。例如,如下是方块 C2 的单元和对等方块: