c++ - 对八皇后中的回溯感到困惑

Question

尽管我做了一些简单的练习(例如斐波那契)，但我很难理解递归和回溯。所以请允许我在这里展示我的“脑流”:

1. 我读过教科书，知道如果前一个皇后的当前位置消除了将下一个皇后放在下一列的可能性，则可以使用回溯删除前一个皇后。所以这看起来很简单，我需要做的就是将其删除并让程序决定下一个可能的位置。

2. 一段时间后，我发现程序在第 6 个皇后停止，所以我发现如果我简单地删除第 5 个皇后，程序只需将它放回当前位置(即给定前四个皇后第 5 个queen 总是落在同一个地方，这并不奇怪)。所以我想我需要跟踪最后一个女王的位置。

3. 这就是我困惑的时候。如果我要跟踪最后一个皇后的位置(这样当我回溯程序时不允许将皇后放在同一个地方)，有两个潜在的困难:

a) 假设我移除了第 5 个皇后，我必须编写代码来决定它的下一个可能位置。这可以通过忽略其当前位置(在被删除之前)并继续在以下行中寻找可能的位置来解决。

b) 我应该跟踪所有以前的皇后吗？好像是这样。假设实际上我必须移除的不是一个皇后，而是两个皇后(或更多)，我当然需要跟踪它们的所有当前位置。但这比看起来要复杂得多。

1. 于是我开始在课本上寻找答案。遗憾的是它没有回溯代码，只有递归代码。然后我在这里找到了代码:

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

这让我非常惊讶，因为它是如此简单而且有效!唯一的回溯部分是删除最后一个女王!所以问题是:下面的代码如何确保当给定 4 个皇后的位置时，第 5 个皇后不会一次又一次地落在同一个地方？我想我不明白的是你怎么能递归地回溯(比如你需要删除更多的皇后)。递归前进没问题，递归后退怎么办？

/* A recursive utility function to solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed then return true */
if (col >= N)
    return true;

/* Consider this column and try placing this queen in all rows
   one by one */
for (int i = 0; i < N; i++)
{
    /* Check if queen can be placed on board[i][col] */
    if ( isSafe(board, i, col) )
    {
        /* Place this queen in board[i][col] */
        board[i][col] = 1;

        /* recur to place rest of the queens */
        if ( solveNQUtil(board, col + 1) == true )
            return true;

        /* If placing queen in board[i][col] doesn't lead to a solution
           then remove queen from board[i][col] */
        board[i][col] = 0; // BACKTRACK
    }
}

 /* If queen can not be place in any row in this colum col
    then return false */
return false;
}

好的。现在我有了一些确实有效的代码，但我主要是根据上面的代码修改了我自己的代码，所以我很不稳定:

bool EightQueen(int& numQueen)  {   

if (numQueen == 8)  {
    return true;
}
if (numQueen == 0)  {
    PlaceQueen(0, 0);
    numQueen ++;
    EightQueen(numQueen);
}

int row = 0;

for (row = 0; row <= 7; row ++) {
    if (CheckThis(row, numQueen))   {   //Check if next queen can be  put
        PlaceQueen(row, numQueen);  //Place next queen
        numQueen ++;
        DisplayQueen();
        cout << endl;
        if (EightQueen(numQueen))   {   //Try next queen
            return true;
        }
        ClearQueen(numQueen - 1);
        numQueen --;
    }
}
return false;
}

假设 numQueen 为 5，那么在 for 循环中我们将检查是否可以放置第 6 个皇后。正如我们所知，这对所有行都是不可能的，因此该函数返回 false。我假设它然后“缩小”回到它被调用的位置，即当 numQueen 为 4 时。因此调用 ClearQueen(4) 并删除最后一个女王(第 5 个)。显然 for 循环还没有完成，所以我们将尝试下一行以查看它是否允许进一步开发。即我们检查是否可以将第 5 个皇后放在下一行，如果可以，我们将进一步检查是否可以放置第 6 个皇后，依此类推。

是的，它似乎有效，嗯，嗯，是的。

Answer 1

考虑您的初始董事会:

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

当您第一次调用函数时，算法会在第 0 列和第 0 行放置一个皇后，因为您使用 col = 0 调用它因为 for (int i = 0; i < N; i++)从 0 开始。你的棋盘变成了

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

然后，您递归调用该函数，使用 col = 1 ，因此您将尝试在 col=1 处放置一个皇后和 line=0 .你得到一个不可能的位置，因为皇后可以互相拿走，所以你继续 for (int i = 0; i < N; i++)循环并最终成功地在 col=1 放置一个女王和 line=2 ，你得到这个板:

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

现在你继续这样做，递增 col每次。最终，您将到达此板:

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+

这里有问题，因为该板不承认第 7 列中的皇后位置。您将不得不回溯。发生的事情是递归函数只到达 return false;在尝试了列中的所有位置但未找到任何位置之后。当函数返回false时，之前的函数调用会在该行继续执行

if ( solveNQUtil(board, col + 1) == true )

由于调用返回 true，for 循环主体的其余部分将被执行，i将递增，算法将继续尝试位置。将其视为一组巨大的嵌套 for 循环:

for(int i = 0; i < 8; ++i) {
  for(int j = 0; j < 8; ++j) {

    //Snip 6 other fors

    board[0, i] = 1;
    board[1, j] = 1;

    //Snip

    if(isValid(board)) return board;

    //Snip clean up
  }
}

用递归函数调用替换。这说明“回溯”实际上只是让先前的递归级别迭代到下一次尝试。在这种情况下，这意味着尝试一个新位置，而在其他应用程序中，这将是尝试下一个生成的移动。

我想你需要明白的是，当你再次调用同一个函数时，之前递归调用的状态并没有丢失。当你到达终点时

if ( solveNQUtil(board, col + 1) == true )

当前函数的状态仍然在栈上，并且为新调用solveNQUtil创建了一个新的栈帧。 .当该函数返回时，前一个函数可以继续执行，在这种情况下，增加它试图将皇后放在哪一行。

希望这对您有所帮助。解决这些问题的最佳方法是将问题缩小到更小的域(比如更少的皇后区)并使用调试器逐步执行。