Search code examples
c++backtrackingn-queens

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


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

Solution

  • 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.