Why isn't my backtracking solution for N queens problem working?

Question

Here's the output that it returns when I call it from the main function by passing args: 0 and board where 0 is the row number to start from and board is a 4x4 board filled with zeros:

9       1       1       1
1       1       9       1
1       1       1       1
1       0       1       1

Note: 9 means a queen and 1 means a cell attacked by a queen, 0 is a safe cell which neither has a queen on it nor is attacked by a queen.

bool queen_placer(int row, std::vector<std::vector<int>> &board)
{
    if (row == board.size())
    {
        return true;
    }
    for (int col = 0; col < board[0].size(); col++)
    {
        bool safe = is_valid(row, col, board); //is_valid returns true if the position doesn't contain any queen and is not attacked by any queen
        if (safe)
        {
            board[row][col] = 9;
            value_assigner(row, col, board); //value assigner just assigns the attack values of the queen so placed
            if (queen_placer(row++, board))
            {
                return true;
            }
            else
            {
                continue;
            }
        }
    }
    return false;
}

Answer 1

You're not backtracking - backtracking involves undoing a choice that leads to failure, but your board[row][col] is forever.

You need to restore the board to its previous state if the recursion fails.

Answer 2

The following is the correct code which solves this problem with changes made to the original code only on lines 9 and 21:

bool queen_placer(int row, std::vector<std::vector<int>> &board)
{
    if (row == board.size())
    {
        return true;
    }
    for (int col = 0; col < board[0].size(); col++)
    {
        std::vector<std::vector<int>> board_prev = board; //Added line
        bool safe = is_valid(row, col, board); //is_valid returns true if the position doesn't contain any queen and is not attacked by any queen
        if (safe)
        {
            board[row][col] = 9;
            value_assigner(row, col, board); //value assigner just assigns the attack values of the queen so placed
            if (queen_placer(row + 1, board))
            {
                return true;
            }
            else
            {
                board = board_prev; //Added line
                continue;
            }
        }
    }
    return false;
}

Here's the output that this code gives:

1       9       1       1
1       1       1       9
9       1       1       1
1       1       9       1