数独解法小探：从回溯到约束编程

数独解法小探：从回溯到约束编程

引用

CSDN

1.

https://blog.csdn.net/zdy0_2004/article/details/51760947

数独是一种经典的逻辑游戏，要求在一个9x9的网格中填入1~9的数字，使得每一行、每一列以及九个3x3的子区域内都没有重复的数字。如何用程序的方法来解这个问题呢？本文将详细介绍五种不同的数独解法，包括回溯法、排列组合法、精确覆盖问题法、模拟退火法以及约束编程法。

回溯法

回溯法是一种经典的递归算法，通过尝试所有可能的解来寻找正确的答案。具体步骤如下：

1. 依次扫描每一个待填数字的空格。
2. 在第一个空格里面填上“1”，检查这个数字是否合法（其所在的行、列，以及3x3的子区域里不存在重复的数字）。如果合法，则前进到第二个格子。否则，在这个格子里继续试2，3，… ，直到合法为止。
3. 在第二个格子里面继续填数字，从“1”开始试起，直到找到一个合法的数字，继续进到下一格。
4. 如果在某个格子里，从“1”到“9”都不合法，这说明前面某个格子填错了。这时就回退到上一格，从还没试的数字里面继续试。例如，如果上一格已填的数字是3，就继续试4，5，6，… 是否合法。如果找到一个合法的数字，则又前进到下一格。如果找不到，说明前面还有格子也填错了，则继续回退到更前面一格，… 如此反复。
5. 如果这个数独是有解的，我们总会遇到“每个格子都碰巧填对了”的情况。如果这个数独是没有解的，那么我们会遇到“第一个格子试了1~9所有的数字都不行”的情况。

排列组合法

排列组合法的核心思想是减少需要验证的解的数量。具体步骤如下：

1. 对于每一空格子，考虑其所在行、列以及子区域，找出所有可能取值的列表S1
2. 对每一个3x3的子区域，对其包含的所有空格子的取值S1进行排列组合，找出该子区域的所有解的列表S2.
3. 9个3x3的子区域排成了三行。对每一行，对其包含的三个子区域的解S2排列组合，找出这一行的解的列表S3.
4. 对三行的解S3排列组合，找出整张数独表的解。

精确覆盖问题法

将数独问题抽象为精确覆盖问题，再用解精确覆盖问题的算法如舞蹈链算法去解它。具体而言，我们是将解数独的问题转化为求一个“Exact Hitting Set”的问题。

模拟退火法

将数独问题表达为一个优化问题，再用求解优化问题的算法去解。核心是定义一个评价函数：将数独表里待填的数字当作自变量，将当前整个表格与有效解局面的区别程度当作函数值，数独问题即转化为一个优化问题：当数独表里填哪些数字时，评价函数的值最小？

约束编程法

将数独看成是一个约束求解问题，然后用约束编程的方法去解。这其实是一个很自然的理解方式：把数独表里的每一个空格看成一个变量，这些变量的可取值范围是1~9之间的整数。“每行、每列及每个3x3子区域内的变量均各不相等”就是这些变量要满足的约束。

总结

小小一个数独，竟可以从这么多的角度来看待和分析，不由得让人感叹思维之奇，数字之妙啊！

本文原文来自CSDN博客