Peter Norvig：用 Python 解决数独问题_程序人生

Peter Norvig：用 Python 解决数独问题

admin

2023-07-30 22:07:41

0次

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

数独记号和初步概念

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

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

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

1234567891011

A1 A2 A3| A4 A5 A6| A7 A8 A9 4 . . |. . . |8 . 5 4 1 7 |3 6 9 |8 2 5 B1 B2 B3| B4 B5 B6| B7 B8 B9 . 3 . |. . . |. . . 6 3 2 |1 5 8 |9 4 7 C1 C2 C3| C4 C5 C6| C7 C8 C9 . . . |7 . . |. . . 9 5 8 |7 2 4 |3 1 6 ————–+————–+————– ———+———+——— ———+———+——— D1 D2 D3| D4 D5 D6| D7 D8 D9 . 2 . |. . . |. 6 . 8 2 5 |4 3 7 |1 6 9 E1 E2 E3| E4 E5 E6| E7 E8 E9 . . . |. 8 . |4 . . 7 9 1 |5 8 6 |4 3 2 F1 F2 F3| F4 F5 F6| F7 F8 F9 . . . |. 1 . |. . . 3 4 6 |9 1 2 |7 5 8 ————–+————–+————– ———+———+——— ———+———+——— G1 G2 G3| G4 G5 G6| G7 G8 G9 . . . |6 . 3 |. 7 . 2 8 9 |6 4 3 |5 7 1 H1 H2 H3| H4 H5 H6| H7 H8 H9 5 . . |2 . . |. . . 5 7 3 |2 9 1 |6 8 4 I1 I2 I3| I4 I5 I6| I7 I8 I9 1 . 4 |. . . |. . . 1 6 4 |8 7 5 |2 9 3

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

1234567891011

A2 | | | | A1 A2 A3| | B2 | | | | B1 B2 B3| | C2 | | C1 C2 C3| C4 C5 C6| C7 C8 C9 C1 C2 C3| | ————–+————–+————– ————–+————–+————– ————–+————–+————– ————–+————– 独这个问题。用了两个想法（idea）：约束传播和搜索后，它其实是很简单的（主旨大约只有一页代码，加上润色后也不过两页）。

数独记号和初步概念

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

1234567891011

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

1234567891011

A2 | | | | A1 A2 A3| | B2 | | | | B1 B2 B3| | C2 | | C1 C2 C3| C4 C5 C6| C7 C8 C9 C1 C2 C3| | ————–+————–+————– ————–+————–+————– ————–+————–+————– an> . . 9 5 8 |7 2 4 |

上一篇：利用 scrapy爬知乎用户关系网以及下载头像

下一篇：如何在Python中实现这五类强大的概率分布

Peter Norvig：用 Python 解决数独问题

数独记号和初步概念

数独记号和初步概念

相关内容

热门资讯