对八皇后的回溯感到困惑 [英] Puzzled about backtracking in Eight Queen

问题描述

尽管我做了一些简单的练习(例如，斐波那契)，但我很难理解递归和回溯.因此，请允许我在此处介绍我的大脑流动":

I have a difficult time understanding recursion and backtracking, albeit I have done some simple exercises (e.g. Fibonacci). So allow me to present my "brain flow" here:

1. 我阅读了教科书，并且知道，如果前一个皇后的当前位置消除了将下一个皇后放置在下一列中的可能性，则可以使用回溯删除该皇后.因此，这似乎很容易，我所需要做的就是将其删除，然后让程序确定下一个可能的位置.

1. I read the textbook and know that you can use backtracking to remove the previous queen if its current position eliminates the possibility of placing the next queen in the next column. So this seems to be easy and all I need to do is to remove it and let the program decide the next possible place.

过了一会儿，我发现程序停在了第6个皇后，所以我发现，如果我简单地删除了第5个皇后，程序就会简单地将其放回当前位置(即，将第4个皇后设置为第5个皇后).皇后总是落在同一个地方，这并不奇怪.所以我认为我需要跟踪最后一个女王的位置.

After a while I found that the program stalled at the 6th queen so I figured out that if I simply removed the 5th queen the program simply put it back to its current position (i.e. given the first four queens the 5th queen always falls into the same place, which is not surprising). So I thought that I need to track the position of the last queen.

这是我感到困惑的时候.如果我要跟踪最后一个皇后的位置(因此，当我回溯该程序时，不允许将女王放置在同一位置)，存在两个潜在的困难:

This is when I got puzzled. If I were to track the position of the last queen (so that when I backtrack the program is NOT allowed to put the queen into the same place), there are two potential difficulties:

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

a) Say that I remove the 5th queen, and I have to write code deciding its next possible position. This can be solved by ignoring its current position (before been removed) and continues to look for possible places in the following rows.

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

b) Should I track all the previous queens? It seems to be so. Let's say that actually I have to remove not one queen, but two queens (or even more), I surely need to track all of their current positions. But this is much more complex than what it seems to be.

1. 因此，我开始在教科书中寻找答案.遗憾的是，它没有回溯代码，而只有递归代码.然后我在这里找到了代码:

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

这让我非常惊讶，因为它是如此简单，但却有效！唯一的回溯部分是删除最后一个女王！所以问题是:下面的代码如何确保在给定4个皇后的位置时，第5个皇后并不总是一次又一次地落在同一个地方?我认为我不了解的是如何递归回溯(例如您需要删除更多的皇后区).递归向前移动没有问题，但是如何递归向后移动?

It greatly amazed me because this is so simple and yet it works! The only backtracking part is to remove the last queen! So the question is: How does the following code make sure that when given the position of 4 queens the 5th one does not always fall into the same place again and again? I think what I do not understand is how can you backtrack recursively (say that you need to remove more queens). I have no problem when moving forward recursively, but how can I move backward recursively?

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

好.现在我有一些可以正常工作的代码，但是我大多根据上述代码修改了自己的代码，所以我很不稳定:

OK. Now I have some code that DOES work but I mostly modified my own codes according to the above ones so I'm quite shaky:

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循环尚未完成，因此我们将尝试下一行以查看是否允许进一步开发.即，我们检查是否可以将第五个皇后放在下一行，如果可以，我们将进一步检查是否可以放置第六个皇后，依此类推.

Say that numQueen is 5, so in the for loop we are going to check if the 6th queen can be placed. As we know this is impossible for all rows, so the function returns false. I assume that it then "shrinks" back to where it was called, that is when numQueen is 4. So ClearQueen(4) is called and the last queen (the 5th) is removed. Apparently the for loop has not finished so we will try the next row to see if it allows further development. i.e. We check if the 5th Queen can be placed on the next row and if it does we will further check if the sixth queen can be placed and so on.

是的，看起来不错，嗯，是的.

Yeah it seems to work, well, eh, yeah.

推荐答案

请考虑您的初衷:

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

首次调用函数时，该算法在第0列和第0行放置一个女王/王后，因为您使用col = 0进行了调用，并且因为for (int i = 0; i < N; i++)从0开始.您的面板变成了

When you first call your function, the algorithm places a queen at column 0 and line 0 because you call it with col = 0 and because the for (int i = 0; i < N; i++) starts at 0. Your board becomes

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

然后，使用col = 1递归调用该函数，因此您将尝试在col=1和line=0处放置一个女王.您会得到一个不可能的放置位置，因为女王之间可能会互相影响，因此您继续执行for (int i = 0; i < N; i++)循环并最终成功在col=1和line=2处放置了女王之后，您将获得此木板:

Then, you call the function recursively, with col = 1, so you'll attempt to place a queen at col=1 and line=0. You get an impossible placement because the queens could take each other, so you continue the for (int i = 0; i < N; i++) loop and eventually succeed in placing a queen at col=1 and line=2, you get this board:

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

现在您继续执行此操作，每次增加col.最终，您将进入此论坛:

Now you keep doing this, incrementing col every time. Eventually, you'll get to this board:

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

您在这里遇到了问题，因为此委员会不允许在第7列中加入女王位置.您必须回溯.发生的情况是，递归函数仅在尝试了列中的所有位置且未找到任何位置之后才达到return false;.当该函数返回false时，上一个函数调用将在该行上恢复执行

You have a problem here, because this board doesn't admit a queen position in column 7. You'll have to backtrack. What happens is that the recursive function only reaches return false; after all positions in a column were attempted and no position was found. When the function returns false, the previous function call will resume execution on the line

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

由于调用返回true，因此将执行for循环主体的其余部分，i将递增，并且算法将保持尝试位置.可以将其视为嵌套的for循环的巨大集合:

Since the call returned true, the rest of the for loop's body will be executed, i will be incremented and the algorithm will keep trying positions. Think of this as a gigantic set of nested for loop:

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

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

That you replace with recursive function calls. This illustrates that "backtracking" is really just letting the previous recursive level iterate to its next attempt. In this case, it means trying a new position while in other applications it would be to attempt the next generated move.

我认为您需要了解的是，当您再次调用同一函数时，上一个递归调用的状态不会丢失.当您到达线路

I think what you need to understand is that the state of the previous recursive call is not lost when you call the same function again. When you reach the line

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

当前函数的状态仍在堆栈上，并为对solveNQUtil的新调用创建新的堆栈框架.当该函数返回时，上一个函数可以继续执行，在这种情况下，可以增加尝试将皇后放置在哪一行的代码.

The state of the current function is still on the stack and a new stack frame is created for the new call to solveNQUtil. When that function returns, the previous one can continue its execution and, in this case, increment which line it's attempting to place the queen in.

希望这会有所帮助.最好的办法是将问题减少到较小的范围(例如，较少的皇后区)，并使用调试器逐步执行.

Hope this helps. The best way to wrap your head around this stuff is to reduce your problem to a smaller domain (say a smaller amount of queens) and step through the execution using a debugger.

这篇关于对八皇后的回溯感到困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！