为什么我的 N 皇后问题的回溯解决方案不起作用？

Question

这是我通过传递args:0和board从主函数调用它时返回的输出，其中0是要开始的行号，board是一个充满零的4x4板：

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

注：9表示女王，1表示被女王攻击的牢房，0是一个既没有女王也没有女王攻击的安全牢房。

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

你不是在回溯-回溯包括撤销导致失败的选择，但你的board[row][col]是永远的。

如果递归失败，则需要将板恢复到以前的状态。

Answer 2

以下是正确的代码，它只在第9行和第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;
}

以下是该代码给出的输出：

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