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

Question

这是当我通过传递 args 从主函数调用它时 returns 的输出：0 和板，其中 0 是开始的行号，板是一个 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

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

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

c++

backtracking

n-queens