有意思的难题——LeetCode题目37：解数独
原题描述
+
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用'.'表示。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
原题链接：https://leetcode-cn.com/problems/sudoku-solver
思路解析
+
这道题目的难度在于，我们不太容易把自己做数独时候的思路写成代码。解数独题目的思路是非常朴素的，就是不断地尝试+回溯，但回溯程序意味着涉及到递归，这显然是编程的一个门槛。
在划归思路之前，建议还是看一下这道题目，至少应该知道如何去判断一个数独是否合法。
现在我们开始思考整个过程。
一般情况下，我们首先要逐行扫描数独盘面，找到空的位置（即标记为'.'的位置），然后开始从1到9尝试。当然，有些尝试是可以马上知道合法性的，因此可以丢弃。
比如当前位置所在的行、列、子宫格包含了某个数字，那么该数字就可以不用尝试了。如此可以做到有效的剪枝，此数字之后的所有探索空间均是无效空间。
难点在于回溯。当我们尝试放置某个数字之后，经过继续尝试了若干步才发现，一开始就是条死路，我们需要回退这一步重新选择。这就是容易思维混乱的一步。
其实这里面包含了子问题，当我们在某个空位上放置了某个数字之后，剩下的数独和原数独问题其实是等价的，要用同样的方法解决，这就是关键递归思路。
我们规定一个探索的顺序，假设我们沿着从左上角到右下角的顺序逐个探索。
现在用函数solveFrom(x, y)来表示从x, y坐标处开始，直到解完数独，那么当我们处理完(x,y)之后，问题就变成了solveFrom(x, y+1)（从当前行的下一个元素开始）或者solveFrom(x+1, 0)（当前行已经遍历完，需要开启下一行）。因此，原问题和子问题是有联系的。
那么何时回溯？假设我们在解solveFrom(x, y)时，在(x, y)处放置了某个数字n，那么如果运气不好，solveFrom(x, y+1)无论如何都找不到解，此时就要回溯(x, y)上的值。那么代码思路就很明显了，伪代码如下。
def solveFrom(x, y):
'''该函数宏观上表示，从(x, y)开始直到解完数独'''
if board(x, y) == ‘.’: # 找到空位，开始探索
for d in range(1, 10):
if could_place(x, y, d): # 检查是否可以放置数字d
placeAt(x, y, d) # 在(x, y)放置数字d
if not finish_all:
solveFrom(x+1, y) or solveFrom(x, y+1)
else:
solved = True
if (!solved): # 因所有子问题解决失败，回退
remove(x, y, d)
else:
solveFrom(x+1, y) or solveFrom(x, y+1)复杂度分析
+
数独的规模是固定的，所以计算复杂度没有意义。但同学们可以自己思考一下计算的次数。
C++参考代码
+
class Solution {
public:
const static int n = 3;
const static int N = 9;
const static int M = 10;
int rows_[N][M];
int cols_[N][M];
int boxes_[N][M];
bool solved = false;
void placeAt(vector<vector<char>>& board, int row, int col, int val) {
int idx = (row / n) * n + col / n;
++rows_[row][val];
++cols_[col][val];
++boxes_[idx][val];
board[row][col] = char(val + '0');
}
void initialize(vector<vector<char>>& board) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= N; ++j) {
rows_[i][j] = 0;
cols_[i][j] = 0;
boxes_[i][j] = 0;
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (board[i][j] != '.') {
int idx = (i / n) * n + j / n;
int val = int(board[i][j] - '0');
++rows_[i][val];
++cols_[j][val];
++boxes_[idx][val];
}
}
}
}
bool couldPlace(int row, int col, int val) {
int idx = (row / n) * n + col / n;
return !(rows_[row][val] + cols_[col][val] + boxes_[idx][val]);
}
void removeAt(vector<vector<char>>& board, int row, int col, int val) {
int idx = (row / n) * n + col / n;
--rows_[row][val];
--cols_[col][val];
--boxes_[idx][val];
board[row][col] = '.';
}
void solveFrom(vector<vector<char>>& board, int row, int col) {
if (board[row][col] == '.') {
for (int val = 1; val <= N; ++val) {
if (couldPlace(row, col, val)) {
placeAt(board, row, col, val);
if (row == N-1 && col == N-1) solved = true;
else if (col == N-1) solveFrom(board, row + 1, 0);
else solveFrom(board, row, col + 1);
if (!solved) removeAt(board, row, col, val);
}
}
} else {
if (row == N-1 && col == N-1) solved = true;
else if (col == N-1) solveFrom(board, row + 1, 0);
else solveFrom(board, row, col + 1);
}
}
void solveSudoku(vector<vector<char>>& board) {
initialize(board);
solveFrom(board, 0, 0);
}
};