题目描述

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

• 一个数独。

• 答案被标成红色。

说明

• 给定的数独序列只包含数字 1-9 和字符 '.'。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

算法

(递归回溯)

1. 首先按照 Valid Sudoku 的方法，预处理出 col、row 和 squ 数组。
2. 从 (0,0) 位置开始尝试并递归。遇到 . 时，枚举可以填充的数字，然后判重并加入 col、row 和 squ 数组中。
3. 如果成功到达结尾，则返回 true，告知递归可以终止。

C++ 代码

class Solution {
public:
    bool solve(int x, int y, vector<vector<char>>& board,
            vector<int>& row, vector<int>& col, vector<int>& squ) {
        if (y == 9) {
            x++;
            y = 0;
        }

        if (x == 9)
            return true;

        if (board[x][y] == '.') {
            for (int i = 1; i <= 9; i++)
                if (! (
                    (row[x] & (1 << i)) ||
                    (col[y] & (1 << i)) ||
                    (squ[(x / 3) * 3 + (y / 3)] & (1 << i))
                )) {
                    row[x] |= (1 << i);
                    col[y] |= (1 << i);
                    squ[(x / 3) * 3 + (y / 3)] |= (1 << i);
                    board[x][y] = i + '0';

                    if (solve(x, y + 1, board, row, col, squ))
                        return true;

                    board[x][y] = '.';
                    row[x] -= (1 << i);
                    col[y] -= (1 << i);
                    squ[(x / 3) * 3 + (y / 3)] -= (1 << i);
                }
        } else {
            if (solve(x, y + 1, board, row, col, squ))
                return true;
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        vector<int> row(9), col(9), squ(9);
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;

                int num = board[i][j] - '0';
                row[i] |= (1 << num);
                col[j] |= (1 << num);
                squ[(i / 3) * 3 + (j / 3)] |= (1 << num);
            }

        solve(0, 0, board, row, col, squ);
    }
};