Sodokuソルバーは、再帰的なバックトラック法を用いた

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; 
    } 
}; 

上記の解決策は非常に直接的かつユニークな数独を解決するために効率的であるが、私をたくさん混乱し、それについての質問があります：

ボード[R] [cは] = '。'; //元の状態に復元する。

なぜこれを追加する必要がありますか？現在のフィルアップが大丈夫ならばそれはちょうど戻ってきます。そうでなければ答えは次の候補になります。私が理解するように、トークンをリセットすることだけがここで必要です。しかし、私はそれを削除すると、結果は間違っています。プロセス全体を追跡するのは難しいので、ここで私はいくつかの有用なアイデアを探しています。

お時間を頂きありがとうございます！

Answer 1

ボードの特定のセルについて、最初の '。'のユニークな答えを考えてみましょう。セルが '2'である場合、最初のセルで最初に '1'を試してみると、次の '。'セルが失敗し、検索後に復元しないと、最初の '2'を試してみるとセル、元の '。'細胞は既にun-'で満たされています。直接検索を終了し、間違った結果を返します。