在 C++ 中创建数独解算器时打印错误

Question

代码中的 print 函数打印原始电路板而不是解决方案，而 solver 函数打印解决方案，这表明原始电路板已就地更新。如您所见，我是参照函数传递的板子，为什么调用打印函数后原板子没有更新？

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n = 9;

void print(vector<vector<char>>& board){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < n; j++){
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

void solver(int x, int y, vector<vector<char>>& board, map< pair<int, int>, map<int, int> >& grid, vector<map<int, int>> row,vector<map<int, int>>& col){

    if(x == 9){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < n; j++){
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
        return;
    }

    if(y == 9){
        solver(x + 1, 0, board, grid, row, col);
        return;
    }

    if(board[x][y] != '.'){
        solver(x, y + 1, board, grid, row,  col);
        return;
    }

    for(int i = 1; i <= 9; i++){
        if(!grid[{x/3, y/3}][i] && !row[x][i] && !col[y][i]){
            board[x][y] = i + '0';
            grid[{x/3, y/3}][i] = 1;
            row[x][i] = 1;
            col[y][i] = 1;
            solver(x, y + 1, board, grid, row, col);
            board[x][y] = '.';
            grid[{x/3, y/3}][i] = 0;
            row[x][i] = 0;
            col[y][i] = 0;
        }
    }

}

void solveSudoku(vector<vector<char>>& board) {
    //int n = board.size();
    vector< map<int, int> > row(n);
    vector< map<int, int> > col(n);
    map< pair<int, int>, map<int, int> > grid;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] != '.'){
                row[i][board[i][j] - '0'] = 1;
                col[j][board[i][j] - '0'] = 1;
                grid[{i/3, j/3}][board[i][j] - '0'] = 1;
            }
        }
    }
    solver(0, 0, board, grid, row, col);
}

int main(){

    vector<vector<char>> board =
    {{ '5','3','.','.','7','.','.','.','.'},
     {'6','.','.','1','9','5','.','.','.'},
     {'.','9','8','.','.','.','.','6','.'},
     {'8','.','.','.','6','.','.','.','3'},
     {'4','.','.','8','.','3','.','.','1'},
     {'7','.','.','.','2','.','.','.','6'},
     {'.','6','.','.','.','.','2','8','.'},
     {'.','.','.','4','1','9','.','.','5'},
     {'.','.','.','.','8','.','.','7','9'}};
    solveSudoku(board);
    cout << endl;
    print(board);

    return 0;
}

Answer 1

第一次调用 solver 是：

solver(0, 0, board, grid, row, col);

因为board[0][0]不是'.'所以第一次调用只是

if(board[x][y] != '.'){
    solver(x, y + 1, board, grid, row,  col);
    return;
}

即：调用solver(0,1,board,grid,row,col)。然后 board[0][1] 是 '.'，并且 x 不是 9 并且 y 不是 9 并且该调用执行：

for(int i = 1; i <= 9; i++){
    if(!grid[{x/3, y/3}][i] && !row[x][i] && !col[y][i]){
        board[x][y] = i + '0';
        grid[{x/3, y/3}][i] = 1;
        row[x][i] = 1;
        col[y][i] = 1;
        solver(x, y + 1, board, grid, row, col);
        board[x][y] = '.';
        grid[{x/3, y/3}][i] = 0;
        row[x][i] = 0;
        col[y][i] = 0;
    }
}

因此，如果我们内联前两个调用，我们可以将 solver(0, 0, board, grid, row, col); 替换为上面的内容以获得：

void solveSudoku(vector<vector<char>>& board) {
    //int n = board.size();
    vector< map<int, int> > row(n);
    vector< map<int, int> > col(n);
    map< pair<int, int>, map<int, int> > grid;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] != '.'){
                row[i][board[i][j] - '0'] = 1;
                col[j][board[i][j] - '0'] = 1;
                grid[{i/3, j/3}][board[i][j] - '0'] = 1;
            }
        }
    }

    size_t x = 0; 
    size_t y = 1;
    for(int i = 1; i <= 9; i++){
        if(!grid[{x/3, y/3}][i] && !row[x][i] && !col[y][i]){
            board[x][y] = i + '0';
            grid[{x/3, y/3}][i] = 1;
            row[x][i] = 1;
            col[y][i] = 1;
            solver(x, y + 1, board, grid, row, col);
            board[x][y] = '.';
            grid[{x/3, y/3}][i] = 0;
            row[x][i] = 0;
            col[y][i] = 0;
        }
    }    
}

这里 board[0][1] 被分配了一个 i + '0'; 然后递归发生，然后 board[0][1] 被重置为 '.'。当深入递归的调用链时，可以应用相同的推理。每当您将某些内容分配给 board[x][y] 时，它将在 solver return 之前重置为 solveSudoku。当你是“递归的底部”时，你只能到达 x == 9 并打印更新的板，但你只能通过执行 board[x][y] = '.';.[= 的路径 return 到 sudokuSolver 35=]

不知道怎么解释比较好，也许用调试器现场看会更有说服力。

在 C++ 中创建数独解算器时打印错误

Print error while creating a sudoku solver in c++

c++

recursion

sudoku

backtracking