C++ - Sodoku Killer(DFS) - 实现一个数独解算器

以前挺喜欢玩数独的。

觉得这些组合之间有这么“巧合”的关系，真的很神奇。

既然现在要重温C++，那就用C++写个数独解算。

数独相关知识 什么是数独

什么是数独，详细可参考1。

一个好的数独题，是只有一个解的，意思每个格子能填的数字最终是唯一的。

有一些没有设计好的数独题，会有多个解，也称无解。

解题技巧

数独技巧

我的数独解算器就参考了里面的部分直观法，与候选数法。

史上最难数独

在世界最难数独2

普通解法

数独技巧，之前说的这个都是普通解法。

DFS解法

除了普通解法，还有DFS数独解法，这种解法一般是用于计算机（非人类）的计算方法。

DFS了解：

• DFS数独解法3
• DFS(深度优先搜索算法)4 - 这篇是说明与代码都比较好
• 深度优先搜索5

因为DFS需要渗透数独的每个数字的分支结果。

试填数字的次数会非常非常大。

最糟糕时的时间复杂度为：O(!n)。

下面代码我是参考了：3，我将原文的代码中添加了更详细的注释：

这个版本的DFS算法，只要数独的数字位置合理的，就可以解算出来。 如果设计数独数字初始不足17个，解算来了会有不定个解，也就是我们说的数独无解，因为这并不数独。

// jave.lin - DFS解算数独
// 这个算法可以递归渗透9x9数独的所有分支，前提是每个已填的数字是合理的
// 參考：https://blog.csdn.net/qq_42837885/article/details/90085051
#include
#include

// #define SHOW_PROC 	// 是否显示DFS处理过程

int max_deep = 0;
int rec_count = 0;
// 检测x,y格中，fillNum是否可填
bool check(int arr[9][9], int x, int y, int fillNum) {
	for (int i = 0; i