数独求解器程序 - 输出没有变化

Question

solveSudoku 函数从 main() 函数调用。

我写了以下函数来解决数独问题：

bool isFull(vector<vector<char>>& board){
        for(int i = 0 ; i < board.size(); i++){
            for(int j = 0 ; j < board[0].size(); j++){
                if(board[i][j] == '.') return false;
            }
        }  
        return true;
    }
    
    vector<int> poss(vector<vector<char>>& board, int x, int y){
        vector<int> ans;
        set<int> s;
        
        //check across columns
        for(int j = 0 ; j < board[0].size(); j++){
            if(board[x][j]!='.')  s.insert(board[x][j] -'0');
        }
        
        //check acroos rows
        for(int i = 0 ; i < board.size(); i++){
            if(board[i][y]!='.')   s.insert(board[i][y] - '0');
        }
        
        //check in square
        int r, c;
        if(x>=0 && x<=2) r = 0;
        if(x>=3 && x<=5) r = 3;
        if(x>=6 && x<=8) r = 6;
        
        if(y>=0 && y<=2) c = 0;
        if(y>=3 && y<=5) c = 3;
        if(y>=6 && y<=8) c = 6;
        
        for(int i = r; i <= r + 2; i++){
            for(int j = c; j <= c + 2; j++){
                if(board[i][j]!='.') s.insert(board[i][j]-'0');
            }
        }
        
        for(int n = 1; n <=9 ; n++){
            if(s.find(n) == s.end()){
                ans.push_back(n);
            }
        }
        
        
        return ans;
    }
    
    vector<int> Fempty(vector<vector<char>>& board){
        vector<int> ans;
        
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == '.'){
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        
        return ans;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        
        if(isFull(board))  return;
        
        //not full
        //Fempty returns first empty cell coordinate
        vector<int> empty = Fempty(board);
        int xe = empty[0], ye = empty[1];
        
        //poss returns the vector of possible values
        vector<int> pos = poss(board, xe, ye);
        
        if(!pos.empty()){
        for(int i = 0; i < pos.size(); i++){
            board[xe][ye] = pos[i] + '0';
            solveSudoku(board);
        }}
        board[xe][ye] = '.';
        
        return;
        
        
    }

当在 main() 函数中调用 solveSudoku 时，输入数独作为参数给出。它由 1 到 9 的字符和 . 代表空字符组成。 solveSudoku 函数的工作是正确填充数独中的所有元素（更改 board 中的值）。

当我运行这个程序时，我的输出显示没有变化。

如果我注释掉 board[xe][ye] = '.'，我的输出会显示一些变化，但在单元格运行s 超出可能值后它仍然保持不变。

编辑：众所周知board有一个解决方案。

我做错了什么？

Answer 1

假设棋盘包含一个完整的数独游戏，只有一个单元格空白（'.'） SolveSudoku 将识别单元格，pos 将具有单个值，for 循环将只执行一个步骤（并做一些奇怪的事情来登机！）然后在循环中递归调用 SolveSudoku，因为现在棋盘已满，此递归调用将首先 return if 语句。程序将在 for 循环之后继续之前的调用。最后一条指令放了一个“。” char 再次在空单元格中......这是 for 循环之后的指令 ...

数独求解器程序 - 输出没有变化

Sudoku Solver Program - no change in output

c++

recursion

backtracking

recursive-backtracking