c++ - 递归数独求解器不正确的解决方案(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]='.'之前返回false!这是完整的代码:

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