Print error while creating a sudoku solver in c++

Question

The print function in the code prints the original board and not the solution, whereas the solver function prints the solution which suggests that the original board has been updated in place. I passed the board by reference to the functions as you can see, so why is not the original board getting updated after calling the print function?

#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

The first call to solver is:

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

Because board[0][0] is not '.' that first call is only

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

That is: it calls solver(0,1,board,grid,row,col). Then board[0][1] is '.', and x is not 9 and y is not 9 and that call executes:

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

Hence if we inline the first two calls, we can replace solver(0, 0, board, grid, row, col); with the above to get:

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

Here board[0][1] is assigned a i + '0'; then the recursion happens and after that board[0][1] is reset to '.'. Same line of reasoning can be applied when going deeper the call chain of the recursion. Whenever you assign something to board[x][y] it will be reset before solver returns to solveSudoku. You only reach x == 9 and print the updated board when you are the "bottom of the recursion" but you only return to sudokuSolver via the path that executes board[x][y] = '.';.

Don't know how to explain better, perhaps it is more convincing for you to see it live with a debugger.