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