数独求解器使用递归回溯法

Question

class Solution {
private:
    bool search(vector<vector<char>>& board, int r, int c, bool rTakens[][9], bool cTakens[][9], bool subTakens[][9])
    {
        if(r == 9) return true; //level checking;
        if(c == 9) return search(board, r+1, 0, rTakens, cTakens, subTakens);
        if(board[r][c] != '.') return search(board, r, c+1, rTakens, cTakens, subTakens);
        for(char a = '1'; a <= '9'; ++a) //try different cases;
        {
            int num = a -'0', k = r/3*3+c/3;
            if(!(rTakens[r][num] || cTakens[c][num] || subTakens[k][num])) //filter out the invalid;
            {
                rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                board[r][c] = a;
                if(search(board, r, c+1, rTakens, cTakens, subTakens)) return true;
                board[r][c] = '.'; //restore to its original state;
                rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = false;
            }
        }
        return false;
    }
public:
    //AC - 4ms - best submission;
    void solveSudoku(vector<vector<char>>& board) 
    {
        bool rTakens[9][9]{{false}}, cTakens[9][9]{{false}}, subTakens[9][9]{{false}};
        for(int r = 0; r < 9; ++r) //initialize the takens;
            for(int c = 0; c < 9; ++c)
                if(board[r][c] != '.')
                {
                    int num = board[r][c] -'0', k = r/3*3+c/3;
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                }
        search(board, 0, 0, rTakens, cTakens, subTakens); //time to search and fill up the board;
    }
};

上面的解决方案对于解决独特的数独问题非常直接和有效，但是有一个问题让我很困惑：

board[r][c] = '.'; //restore to its original state;

为什么我必须添加这个？如果当前填充没问题，那么它将只是 return，如果不是，那么答案将在以下候选中，这些候选将在进一步搜索之前替换它；所以据我所知，这里只需要重置令牌。但是当我删除它时，结果将是错误的。跟踪整个过程很棘手，所以我在这里寻找一些有用的想法。

Thanks for your time and answers for this in advance!

Answer 1

对于电路板的特定单元格，让我们假设第一个“.”的唯一答案。单元格为“2”，然后当我们首先为第一个单元格尝试“1”时，然后是以下所有“。”单元将失败，如果我们在搜索后不恢复它们，那么当我们尝试为第一个 '.' 尝试 '2' 时。单元格，原来的'.'单元格将已经被 un-'.' 填满。这将直接结束搜索并且 return 一个错误的结果。

数独求解器使用递归回溯法

Sodoku Solver using recursive backtracking method

recursion

backtracking