使用Python解决数独的算法

数独是一种数字放置类的益智游戏。这个游戏的目的是用0-9或1-n的数字填满一个n大小的方格。数独中的数字必须放在每一列、每一行以及由1-'n'组成的子网格中。大多数数独谜题包含一个9x9的网格，网格未被完全或部分填充提示，以确认可以达到解决方案。

这种类型的问题经常在亚马逊、谷歌、微软等大型科技公司的技术面试中被问到。

公司给出的问题描述如下。你有一个二维矩阵形式的数独谜题，你必须在不违反任何规则的情况下填满单元格。数独谜题的规则如下。

1. 每一行必须包含数字1-9。
2. 每一列必须包含数字1-9。
3. 每一个3x3的子网格必须包含数字1-9。

提供一个包含数字1-9和字符'.'的棋盘。谜题应该有一个唯一的解决方案，并且给定的棋盘大小总是9x9。字符'.'代表一个空单元格。

示例展示了给定的数独谜题。

上图显示了一个9x9的数独谜题。谜题包含3x3的子网格，其中一些数字被部分填充。这个游戏的目标是用1-9的值填满方格，并且每一行、每一列和每一个网格都应该有唯一的值。

以上谜题的解是

红色的数字显示了谜题的解。

让我们看看在编程中，输入是如何给出的

输入： 谜题

在上面的输入中，有一个9x9的二维矩阵，它是稀疏的，这意味着它包含更多的零。目标是用1-9的数字替换0，并且每一行和每一列都应该包含唯一的数字。

输出

3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9

在输出中，我们可以看到0被1-9的数字替换，并且输出的每一行、每一列和3x3的网格都包含唯一的值。

解决数独谜题有许多方法。方法包括

朴素方法： 在这种方法中，生成所有可能的解决方案，用1到9的数字来填补空白单元格。逐一检查每一种配置，直到形成正确的谜题。对于每个未分配的位置，用1-9的数字填补该位置。填补未分配的位置后，检查矩阵是否安全。如果谜题矩阵是安全的，则递归处理其他情况。

以下是使用朴素方法解决问题的步骤。

1. 首先，创建一个函数来检查给定的矩阵是否是一个有效的数独。为每一行、每一列和每一个盒子创建一个哈希表。如果哈希表中某个数字的出现次数大于1，则返回false；否则，返回true。
2. 创建一个递归函数，该函数接受一个网格以及当前行和列的索引。
3. 检查了一些基本情况。
   1. 如果索引到达矩阵的末尾，即i = N-1 且 j = N，则检查网格是否安全；如果网格是安全的，则打印网格，并由函数返回true。否则，返回false。
   2. 第二个基本情况是当列值为N时，即j = N，然后索引值移到下一行，即i的值更新为i++ 且 j = 0。
4. 如果当前索引未赋值，则用1到9的数值填补索引，并用下一个元素的索引，即i, j + 1，递归处理所有9种情况。如果递归调用返回true，则中断循环并返回true值。
5. 如果当前索引已赋值，则使用下一个元素的索引，即I, j + 1，调用递归函数。

上述算法的实现是

代码

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9 

说明

在上面的代码中，谜题的大小定义为9，这是一个3x3的二维矩阵。定义了一个函数用于打印二维谜题，另一个函数用于检查索引和单元格是否安全。该函数接受grid、row、column和number作为参数。在函数中，对于1到9的所有值，都会检查条件，如果在相似的行中找到相同的数字，则返回false。否则，如果在列中找到相同的数字，也返回false。如果相同的数字在3x3的矩阵中找到，它们也返回false。另一个函数是solve sudoku函数，它接受grid、row和column作为参数。在函数中，首先检查是否已到达第8行和第9列，如果为true，则返回True以避免进一步的回溯，这是函数的基本条件。接下来，检查列值是否为9的条件。如果列值为9，则移到下一行，并且列从0开始。如果网格的当前位置已填好，则移到下一列。然后检查安全位置。

给定行和列中的数字1到9移到下一列。在网格的当前行和列中赋值，并假设在该位置赋值的数字是正确的。赋值后，检查下一列的下一个可能性。移除已赋值的数字，因为所做的假设是错误的，然后尝试用不同的数字值进行下一次假设。

时间复杂度： 上述方法的_时间复杂度_为O(9^(N*N))；对于每个未分配的索引，有9种可能的选择。因此，时间复杂度为O(9^(N*N))。

空间复杂度： 上述方法的_空间复杂度_为O(N*N)。需要一个二维矩阵来存储输出。

使用回溯法解决数独的算法

数独可以通过逐个为空白单元格赋值来解决。首先，检查给定单元格是否安全可以赋值，然后赋值。检查一个条件，看当前行、当前列和当前3x3子网格中是否存在相同的数字。如果安全，则赋值，并递归检查所赋的数字是否能导致解决方案。如果赋值后没有解决方案，则尝试为当前空白单元格赋值下一个数字。如果从1到9的数字能够为谜题提供解决方案，则返回false并打印“无解决方案”。

以下是使用回溯法解决数独谜题的步骤。

1. 创建一个函数，该函数检查在当前索引值赋值给数字后，给定的网格是否安全。为行、列和盒子维护一个哈希表。如果哈希表中任何数字的出现次数大于1，则返回false，否则返回true。可以通过循环来避免使用哈希表。
2. 创建一个接受网格的递归函数。
3. 一个语句检查是否还有未分配的位置。
   1. 如果存在该位置，则赋值的数字为1到9。
   2. 一个语句检查当前索引赋值的数字是否使网格安全。
   3. 如果当前索引是安全的，则递归调用函数处理所有0到9的安全情况。
   4. 如果任何递归调用返回true，则结束循环并返回true。如果没有递归调用返回true，则返回false。
4. 如果没有剩余的未分配位置，则返回true。

代码

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9

说明

在上面的代码中，使用回溯法来解决数独谜题。在代码中，display函数用于打印完整的谜题。一个函数用于查找网格中尚未使用的条目。搜索网格以查找尚未赋值的条目。如果找到条目，则引用行、列将设置为未赋值的位置，并返回true。如果没有剩余的未赋值条目，则函数返回false。在代码中，l是solve sudoku函数传递过来的列表变量，用于记录行和列的增量。返回一个布尔值，表示指定行中是否有已赋值的条目与给定数字匹配。检查状态，看给定的数字是否可以合法地赋值给给定的行、列和网格。返回一个布尔值，表示将num赋值给给定的行、列位置是否合法。最后一个函数，solveSudoku函数，完成了整个网格，它接受一个部分填充的网格作为输入，并尝试为所有未赋值的位置赋值，以满足数独解决方案的要求。

• 时间复杂度： 上述算法的时间复杂度为O(9^(N*N))，因为每个未赋值的索引都有9种可能性，所以时间复杂度为O(9^(N*N))。时间复杂度与朴素方法相同，但区别在于会有一些早期剪枝，因此耗时会比朴素方法少。
• 空间复杂度： 算法的空间复杂度为O(N*N)，因为需要一个输出矩阵来存储输出，并且还需要3个大小为n的额外数组用于位掩码。

使用位掩码解决数独

位掩码方法是另一种优化的数独求解方法。在这种方法中，为每一行、每一列和3x3的网格创建一个位掩码，对于网格中的每个元素，将位置值设置为1，以实现O(1)的检查。

位掩码算法

1. 创建三个大小为N的数组（一个用于行，一个用于列，一个用于3x3的盒子）。
2. 盒子的索引值从0到8设置。
3. 初始值映射到第一个网格。
4. 每次将一个元素添加到网格或从网格中移除时，为相应的位掩码设置1或0位。

代码

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9 

说明

在上面的数独问题代码中，print_grid函数用于打印完整的数独网格，一个函数用于检查行、列和3x3网格的安全条件。另一个用于解决数独谜题的函数是：如果索引到达第8行和第9列，则返回true以避免进一步的回溯。检查一个条件以确定列值是否等于9。如果列值为9，则索引移到下一行，并且列从0开始。如果网格的当前位置的值大于0，则迭代到下一列。如果索引位置安全，则在给定行中放置数字（1-9），然后移到下一列。在网格的当前行或列位置赋值，并假设我们在此位置赋值的数字是正确的。检查下一列的下一个可能性。

• 时间复杂度： 上述算法的复杂度为O(9^(N*N))，因为每个未赋值的索引都有9种可能性。因此，时间复杂度为O(9^(N*N))。
• 空间复杂度： 算法的空间复杂度为O(N*N)，因为需要一个输出数组来存储输出，并且还需要3个大小为n的额外数组用于位掩码。

使用交叉划线和回溯法解决数独

这是位掩码方法的一种优化方法。它的速度比位掩码方法快5倍。在按位方法中，数独首先通过找到几乎填满的元素来填充。在这种方法中，会确定元素应该放置的行和列。

以下是解决数独谜题的算法

1. 创建一个图，其中包含剩余的元素，并将其映射到原始矩阵中可以放置它们的行和列坐标。
2. 从图中选择一个元素，并按需要填补的元素数量较少进行排序。
3. 使用图递归地将元素填入矩阵。一旦发现不安全的位置，就进行回溯。

代码

输出

[3, 1, 6, 5, 7, 8, 4, 9, 2]
[5, 2, 9, 1, 3, 4, 7, 6, 8]
[4, 8, 7, 6, 2, 9, 5, 3, 1]
[2, 6, 3, 4, 1, 5, 9, 8, 7]
[9, 7, 4, 8, 6, 3, 1, 2, 5]
[8, 5, 1, 7, 9, 2, 6, 4, 3]
[1, 3, 8, 9, 4, 7, 2, 5, 6]
[6, 9, 2, 3, 5, 1, 8, 7, 4]
[7, 4, 5, 2, 8, 6, 3, 1, 9]

结论

数独谜题是一个著名的谜题，在许多跨国公司中都会被问到，并且有许多方法可以解决该谜题。回溯法是解决该问题的最佳方法。