八皇后问题中的回溯算法让我感到困惑

4
我很难理解递归和回溯,尽管我已经做了一些简单的练习(例如斐波那契数列)。所以请允许我在这里展示我的“思维流程”:
1. 我读了教科书,知道可以使用回溯来移除前一个皇后,如果其当前位置消除了在下一列放置下一个皇后的可能性。所以这似乎很容易,我所需要做的就是删除它并让程序确定下一个可能的位置。
2. 过了一会儿,我发现程序在第6个皇后处停滞不前,所以我想出了一个方法:如果我只是简单地移除第5个皇后,程序会将其放回原位(即给定前四个皇后,第5个皇后总是落在同样的位置,这并不奇怪)。所以我认为我需要跟踪最后一个皇后的位置。
3. 这就是我感到困惑的地方。如果我要跟踪最后一个皇后的位置(这样当我回溯时,程序就不能将皇后放在同一个位置上),那么有两个潜在的困难:
a) 假设我移除了第5个皇后,并且我必须编写代码来决定它的下一个可能的位置。这可以通过忽略其当前位置(在被删除之前)并继续在以下行中寻找可能的位置来解决。
b) 我应该跟踪所有以前的皇后吗?看起来是这样。假设我实际上不仅需要移除一个皇后,而是两个皇后(甚至更多),我肯定需要跟踪它们所有的当前位置。但这比看起来要复杂得多。
4. 所以我开始在教科书中寻找答案。可悲的是,它没有回溯代码,只有递归代码。然后我在这里找到了代码: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个皇后,以此类推。
是的,看起来它能够工作,嗯,是的。

1
根据 isSafe 参数,此函数可能始终返回 true。 - Some programmer dude
1
booltrue 进行比较没有意义。直接使用 bool ---这就是该类型的用途。 - James Kanze
3个回答

8
考虑您的初始棋盘:
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

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

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

然后,您会递归调用该函数,使用col = 1,因此您将尝试在col=1line=0放置皇后。由于皇后可能互相攻击,所以您得到了一个不可能的放置结果,因此您继续执行for (int i = 0; i < N; i++)循环,并最终成功地在col=1line=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的新调用创建了一个新的堆栈帧。当该函数返回时,前一个函数可以继续执行,在这种情况下,它将尝试将皇后放置在哪一行进行递增。
希望这可以帮助您。最好的方法是将问题缩小到更小的领域(例如更少的皇后),并使用调试器逐步执行。

非常感谢你详细的答复!我成功找到问题所在:我的大脑一直认为需要记忆先前皇后的位置以进行回溯,但实际上并不需要这样做,因为递归中的简单for循环已经解决了这个问题 ---- 大脑只需要命令我的手移除先前的皇后并将其放入下一行,然后检查它是否可行。当然,我相信对于下一个递归回溯问题,我需要重新说服自己的大脑。 - Nicholas Humphrey
1
@FanZhang 很高兴我能帮到你!递归是那种在某个时刻你就会“领悟”的东西,看起来这是你的“哦~”时刻 ;) - anthonyvd
1
谢谢pwny,我成功地根据上面的代码修改了我的代码,尽管我有些怀疑。我会尝试更多递归练习来提高自己的水平。 - Nicholas Humphrey

2
请记住,将皇后向下移动的原因有两个
  • 它不在安全位置
  • 它在安全位置,但当您尝试放置下一个皇后时,递归调用返回false,这意味着您已经用完了下一列中的所有可能性
由于未考虑第二种情况,因此您的程序在第5个皇后处停顿。像James所说的那样,没有必要跟踪位置,因为每个递归调用都隐式跟踪要放置的皇后。
试着想象调用堆栈(实际上,您可以修改程序以生成相同类型的输出):
Queen 1 is safe on row 1
    Queen 2 is safe on row 3
        Queen 3 is safe on row 5
            Queen 4 is safe on row 2
                Queen 5 is safe on row 4
                    No more rows to try for Queen 6. Backtracking...
                Queen 5 is safe on row 8
                    No more rows to try for Queen 6. Backtracking...
                No more rows to try for Queen 5. Backtracking...
            Queen 4 is safe on row 7
                Queen 5 is safe on row 2
                    Queen 6 is safe on row 4
                        Queen 7 is safe on row 6
                           No more rows to try for Queen 8. Backtracking...

每次回溯时,请意识到您会返回到上一个函数调用中,处于相同的状态。所以当您到达Queen 6并且没有可能性时,该函数将返回false,这意味着solveNQUtil(board,col + 1)已为Queen 5完成。您回到了Queen 5的for循环中,接下来要发生的事情是i被递增,然后尝试将Queen 5放在第5行,以此类推... 我建议您尝试这个演示(尝试放置控件:“手动带帮助”选项),我们的大脑更擅长通过视觉理解事物。代码太抽象了。

感谢Miklos Aubert。我亲手玩了4-皇后问题,最终发现我的大脑顽固地认为我需要保留“堆栈”以存储之前皇后的位置。我还发现,尽管我知道递归结束后会返回到for循环,但在编程时我并不理解它。恐怕只有通过几天灌输各种递归问题来让我的大脑接受这个概念。 - Nicholas Humphrey
我理解你的困惑。看着一个“单一”的函数,想象它将在不同的层次上执行并始终返回到应该返回的位置是很难的。不知何故,当一个函数调用“另一个”函数,然后再调用“另一个”函数时,大脑更容易理解调用堆栈的概念,尽管在实践中,递归调用与此相同!你必须看到,递归调用就像任何其他函数调用一样,事实上,你所在的仍然是同一个函数,并不意味着你“原地踏步”。你真正做的是_移动_到一个新状态。 - Miklos Aubert
经过几分钟的考虑,我意识到我也在与那个for循环挣扎。这就像是看着镜子,说服自己迟早能够找到问题的核心并找到解决方案。我不确定该如何表达,但是,好吧,我猜更多的练习会有所帮助。 - Nicholas Humphrey

2

回答您的问题很简单:您需要在循环中定位并移除皇后,下一次循环时,您将尝试下一个位置。

这就引出了下一个问题:您说教科书没有回溯代码,只有递归代码。递归代码就是回溯代码。在递归时,每个函数实例都有自己的完整变量集。因此,在这种情况下,当调用solveNQUtil时,问题已经解决了前面col-1列。函数遍历行,每次测试是否可以放置一个皇后,如果可以,就放置它并递归。迭代确保将检查所有可能的位置(必要时---您的代码一旦找到解决方案就终止)。


谢谢,我开始看到问题所在了,但我仍然有困难弄清楚程序如何自动迭代行。我相信for循环可以解决这个问题,因为它通过i(即行)进行迭代。我会仔细阅读代码,过几分钟再回来。 - Nicholas Humphrey
好的,谢谢。我现在明白问题了:算法像一棵树(虽然我还没有读过这一章,但有些想法),每个皇后都被视为一个节点,给定几个节点后,您会循环遍历下一个节点的可能位置,如果没有找到可能的解决方案,则只需删除最后一个节点。程序会自动将最后一个节点向下移动一行,因为当最后一个递归结束时,程序会返回到上一个for循环中,该循环负责处理最后一个节点的位置。我知道这很混乱,但我想问题可能是我并不真正理解递归。 - Nicholas Humphrey
1
@FanZhang 是的,回溯法有点像一棵树,但实际上并不需要建立一棵真正的树。而且通过行迭代也不是自动完成的,必须通过 for 循环来明确地完成。 - James Kanze
谢谢,现在我明白了我的问题所在:当我阅读递归的教材时,教材告诉我递归对于某些问题可能更直观,这可能是真的。例如,当我手动解决八皇后问题时,我的大脑并没有实际地将前面皇后的位置保存到“堆栈”中,而只是看着前一个皇后并命令我的手将其向下移动到下一行(并查看是否有其他皇后的攻击)。我相信我需要做更多的练习才能对递归感到舒适(不再使用堆栈!)。 - Nicholas Humphrey

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接