我很难理解递归和回溯,尽管我已经做了一些简单的练习(例如斐波那契数列)。所以请允许我在这里展示我的“思维流程”:
1. 我读了教科书,知道可以使用回溯来移除前一个皇后,如果其当前位置消除了在下一列放置下一个皇后的可能性。所以这似乎很容易,我所需要做的就是删除它并让程序确定下一个可能的位置。
2. 过了一会儿,我发现程序在第6个皇后处停滞不前,所以我想出了一个方法:如果我只是简单地移除第5个皇后,程序会将其放回原位(即给定前四个皇后,第5个皇后总是落在同样的位置,这并不奇怪)。所以我认为我需要跟踪最后一个皇后的位置。
3. 这就是我感到困惑的地方。如果我要跟踪最后一个皇后的位置(这样当我回溯时,程序就不能将皇后放在同一个位置上),那么有两个潜在的困难:
a) 假设我移除了第5个皇后,并且我必须编写代码来决定它的下一个可能的位置。这可以通过忽略其当前位置(在被删除之前)并继续在以下行中寻找可能的位置来解决。
b) 我应该跟踪所有以前的皇后吗?看起来是这样。假设我实际上不仅需要移除一个皇后,而是两个皇后(甚至更多),我肯定需要跟踪它们所有的当前位置。但这比看起来要复杂得多。
4. 所以我开始在教科书中寻找答案。可悲的是,它没有回溯代码,只有递归代码。然后我在这里找到了代码:http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/。这让我感到非常惊讶,因为它如此简单,却能够工作!唯一的回溯部分就是删除最后一个皇后!那么问题是:以下代码如何确保当给定4个皇后的位置时,第5个皇后不会一次又一次地落在同一个位置上?我认为我不理解的是如何递归地回溯(例如,如果你需要移除更多的皇后)。我在递归向前移动时没有问题,但是如何递归向后移动呢?
假设numQueen为5,因此在for循环中,我们将检查是否可以放置第6个皇后。正如我们所知,这在所有行中都是不可能的,因此函数返回false。我假设它会“缩回”到被调用的位置,也就是当numQueen为4时。因此调用ClearQueen(4),并移除最后一个皇后(第5个)。显然,for循环尚未完成,因此我们将尝试下一行,看看它是否允许进一步的发展。也就是说,我们将检查第5个皇后是否可以放置在下一行上,如果可以,我们将进一步检查是否可以放置第6个皇后,以此类推。
是的,看起来它能够工作,嗯,是的。
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个皇后,以此类推。
是的,看起来它能够工作,嗯,是的。
isSafe
参数,此函数可能始终返回 true。 - Some programmer dudebool
与true
进行比较没有意义。直接使用bool
---这就是该类型的用途。 - James Kanze