C++刷LeetCode（37. 解数独）【回溯】

糖逗

题目描述：

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。



一个数独。



答案被标成红色。

Note:

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

class Solution {
private:
    int row[9][9] = {0};
    int col[9][9] = {0};
    int matrix[9][9] = {0};
public:
    bool dfs(vector<vector<char> >&board, int index1, int index2){
        if(index1 > 8) return true;
        if(board[index1][index2] == '.'){
            for(char number = '1' ; number <= '9'; number++){
                int number1 = number - '1';
                if(row[index1][number1] == 1 || col[index2][number1] == 1 || matrix[index1 / 3*3 + index2 /3][number1] == 1)continue;
                row[index1][number1] = 1;
                col[index2][number1] = 1;
                matrix[index1 / 3*3 + index2 /3][number1] = 1;
                board[index1][index2] = number;

                if(dfs(board, index1 + (index2 + 1)/9, (index2 + 1)%9)) return true;
                //回溯
                board[index1][index2] = '.';
                matrix[index1 / 3*3 + index2 /3][number1] = 0;
                col[index2][number1] = 0;
                row[index1][number1] = 0;
            }
        }
        else return dfs(board,index1 + (index2 + 1)/9, (index2 + 1)%9);
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        //初始化变量
        for(int i = 0 ; i < 9; i++){
            for(int j = 0; j < 9; j ++){
                if(board[i][j] != '.'){
                    int number = board[i][j] - '1';
                    row[i][number] = 1;
                    col[j][number] = 1;
                    matrix[i / 3 * 3 + j / 3][number] = 1;
                }
            }
        }
        dfs(board, 0, 0);
        return;
    }
};

参考链接：https://leetcode-cn.com/problems ... i-ji-de-dai-ma-hen/


注意事项：注意函数dfs的写法。

糖逗

没写出来