LeetCode 刷题【37. 解数独】

37. 解数独

自己做

解：排除填空（做不出）

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<vector<bool>>> target(9,vector<vector<bool>(9,vector<bool>(9,true)));             //标记元素是否可取

        //初始化target
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
                if(board[i][j] != '.'){
                    //对board[i][j]该位置所有元素标记不可取
                    for(int z = 0; z < 9; z++)
                        target[i][j][z] = false;
                    
                    //对同行、同列、3*3的该元素标记不可取
                    for(int z = 0; z < 9; z++)                  //对同行
                        target[i][z][board[i][j] - 1] = false;
                    for(int z = 0; z < 9; z++)                  //对同列
                        target[z][j][board[i][j] - 1] = false;
                    for(int z = 0; z < 9; z++)                  //对3*3
                        //计算该位置是在哪个3*3的块内： i/3，j/3，3*3块的起始块位置为【(i/3)*3,(j/3)*3】=>【(0,0)、(0,1)、(0,2)、(1,2)...】
                        target[(i / 3) * 3 + z / 3][(j / 3) * 3 + z % 3][board[i][j] - 1] = false;
                }

        for(int i = 0; i < 9; i++)             //两重for遍历位置
            for(int j = 0; j < 9; j++){  
                if(board[i][j] == '.')               //遇到空格，填充元素
                    for(int z = 1; z <= 9; z++){     //填充元素遍历
                        if(target[i][j][z - 1] == true){  //查看该元素能否填充  
                            board[i][j] = z;        //填充

                            //填充后
                            //对board[i][j]该位置所有元素标记不可取
                            for(int k = 0; k < 9; k++)
                                target[i][j][k] = false;
                            
                            //对同行、同列、3*3的该元素标记不可取
                            for(int k = 0; k < 9; k++)                  //对同行
                                target[i][k][board[i][j] - 1] = false;
                            for(int k = 0; k < 9; k++)                  //对同列
                                target[k][j][board[i][j] - 1] = false;
                            for(int k = 0; k < 9; k++)                  //对3*3
                                //计算该位置是在哪个3*3的块内： i/3，j/3，3*3块的起始块位置为【(i/3)*3,(j/3)*3】=>【(0,0)、(0,1)、(0,2)、(1,2)...】
                                target[(i / 3) * 3 + k / 3][(j / 3) * 3 + k % 3][board[i][j] - 1] = false;
                            break;
                        }
                    }
            
                //填充失败，说明之前有取错了的元素
                if(board[i][j] == '.'){
                    //回退
                }

            }
        
    }
};

看题解

触摸到禁忌知识了属于是，留到后面回顾

37. 解数独 - 力扣（LeetCode）

官方代码：

class Solution {
private:
    bool line[9][9];
    bool column[9][9];
    bool block[3][3][9];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = digit + '0' + 1;
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, false, sizeof(line));
        memset(column, false, sizeof(column));
        memset(block, false, sizeof(block));
        valid = false;

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                }
                else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0);
    }
};