类似于八皇后问题的回溯法。时间复杂度爆炸，然而能过。我还以为过不了。 这段代码中的精髓段如下。判断是否能将数字i填进去，如果能填就试着填一下。如果成立，就返回1，如果不成立，就把之前用来试着填的状态全部改回初始状态。
if (row[r][i] || col[c][i] || box[boxn][i]) continue; row[r][i] = 1; col[c][i] = 1; box[boxn][i] = 1; board[r][c] = '0' + i; if (solve(now + 1, board, le - 1) == 1) { return 1; } row[r][i] = 0; col[c][i] = 0; box[boxn][i] = 0; board[r][c] = '.';还需要注意，用了一个vector存储所有空的块的位置，就不用再挨个扫矩阵中的每个元素了，可以直接跳过非空的块。 综上，这道题的解题代码如下：
class Solution { private: int row[10][11], col[10][11], box[10][11]; struct Node{ int r, c, boxn; Node(){} Node(int rr, int cc, int nn) { r = rr; c = cc; boxn = nn; } }; vector<Node> emp; //存储所有空白块的索引 int FindBox(int r, int c) { int tmp_r = r / 3; int tmp_c = c / 3; if (tmp_r == 0) { if (tmp_c == 0) return 0; if (tmp_c == 1) return 1; if (tmp_c == 2) return 2; } if (tmp_r == 1) { if (tmp_c == 0) return 3; if (tmp_c == 1) return 4; if (tmp_c == 2) return 5; } if (tmp_r == 2) { if (tmp_c == 0) return 6; if (tmp_c == 1) return 7; if (tmp_c == 2) return 8; } return -1; } int solve(int now, vector<vector<char>>& board, int le) { if (le == 0) return 1; int r = emp[now].r; int c = emp[now].c; int boxn = emp[now].boxn; for (int i = 1; i <= 9; i++) { if (row[r][i] || col[c][i] || box[boxn][i]) continue; row[r][i] = 1; col[c][i] = 1; box[boxn][i] = 1; board[r][c] = '0' + i; if (solve(now + 1, board, le - 1) == 1) { return 1; } row[r][i] = 0; col[c][i] = 0; box[boxn][i] = 0; board[r][c] = '.'; } return 0; } public: void solveSudoku(vector<vector<char>>& board) { emp.clear(); memset(row, 0, sizeof(row)); memset(col, 0, sizeof(col)); memset(box, 0, sizeof(box)); int le = 0; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { le++; emp.push_back(Node(i, j, FindBox(i, j))); continue; } int num = board[i][j] - '0'; row[i][num] = 1; col[j][num] = 1; box[FindBox(i, j)][num] = 1; } } solve(0, board, le); return; } };