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- '로 채워질 것입니다. 그러면 직접 검색이 끝나고 잘못된 결과가 반환됩니다.