递归数独求解器不正确的解决方案（C++）

Question

我想实现一个递归回溯解决方案到soduko板，但是，我得到一个不正确的解决方案的板。我不确定为什么当我的复发是正确的时候：

bool solveSudoku(vector< vector<char> >& board) { 
    for (int i=0; i<9; ++i){ 
     for (int j=0; j<9; ++j){ 
      if (board[i][j]=='.'){ 
       for (int k=0; k<9; ++k){ 
        board[i][j]=('1'+k); 
        if (check(i,j, board) && solveSudoku(board)){ 
          return true; 
        } 
       } 
       return false; 
      } 
     } 
    } 
    return true; 
} 
bool check(int i, int j, vector< vector<char> >& board){ 
    //check horizontal 
    for (int l=0; l<9; ++l){ 
     if (board[i][l]==board[i][j] && l!=j){ 
      return false; 
     } 
    } 
    //check vertical 
    for (int l=0; l<9; ++l){ 
     if (board[l][j]==board[i][j] && l!=i){ 
      return false; 
     } 
    } 
    //check block 
    int block_x = i/3; 
    int block_y = j/3; 
    block_x*=3; 
    block_y*=3; 
    for(int l=0; l<3; ++l){ 
     for (int k=0; k<3; ++k){ 
      if (board[block_x+l][block_y+k]==board[i][j] && block_x+l!=i && block_y+k!=j){ 
       return false; 
      } 
     } 
    } 
    //all valid so return true 
    return true; 
} 

Answer 1

我终于弄明白了。我只需要添加board [i] [j] ='。'之前返回假！这里是完整的代码：

bool solveSudoku(vector< vector<char> >& board) { 
    for (int i=0; i<9; ++i){ 
     for (int j=0; j<9; ++j){ 
      if (board[i][j]=='.'){ 
       for (int k=0; k<9; ++k){ 
        board[i][j]=('1'+k); 
        if (check(i,j, board) && solveSudoku(board)){ 
          return true; 
        } 
       } 
       board[i][j]='.'; 
       return false; 
      } 
     } 
    } 
    return true; 
} 
bool check(int i, int j, vector< vector<char> >& board){ 
    //check horizontal 
    for (int l=0; l<9; ++l){ 
     if (board[i][l]==board[i][j] && l!=j){ 
      return false; 
     } 
    } 
    //check vertical 
    for (int l=0; l<9; ++l){ 
     if (board[l][j]==board[i][j] && l!=i){ 
      return false; 
     } 
    } 
    //check block 
    int block_x = i/3; 
    int block_y = j/3; 
    block_x*=3; 
    block_y*=3; 
    for(int l=0; l<3; ++l){ 
     for (int k=0; k<3; ++k){ 
      if (board[block_x+l][block_y+k]==board[i][j] && block_x+l!=i && block_y+k!=j){ 
       return false; 
      } 
     } 
    } 
    //all valid so return true 
    return true; 
}