我迷失了骑士的回溯方式使用递归。我已经尝试了多种方法,因为您可以看到它已经评论了一些尝试,但是它如何知道回溯到回去的距离有多远才能重新开始前进呢?我对递归的理解是每次函数每次呼叫,新的参数构建了堆栈框架,当它到达基本情况时,它会返回堆栈框架,在这种情况下,向后移动。有人可以将我指向正确的方向吗?谢谢。
#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;
int GAMEBOARD[8][8] = { 0 };
int TOTAL_MOVES = 0, BAD_MOVES = 0;
bool moveKnight(int row, int col, int movNum);
void print();
int main()
{
int startRow = 3, startCol = 3;
int moveNum = 1;
GAMEBOARD[startRow][startCol] = moveNum;
TOTAL_MOVES++;
moveKnight(startRow, startCol, moveNum);
if (moveKnight(startRow, startCol, moveNum) == true) {
cout << "Knight's Tour Solved! It took " << TOTAL_MOVES <<
" total moves and " << BAD_MOVES << " bad moves." << endl;
}
system("pause");
return 0;
}
bool moveKnight(int row, int col, int moveNum)
{
GAMEBOARD[row][col] = moveNum;
TOTAL_MOVES++;
if (moveNum == 64) {
return true;
}
if (GAMEBOARD[row][col] != 0) {
GAMEBOARD[row][col] = 0;
print();
system("pause");
return moveKnight(row, col, moveNum);
}
// commented out
/*if (GAMEBOARD[row - 2][col + 1] != 0) {
print();
system("pause");
return moveKnight(row - 2, col + 1, moveNum + 1);
}
else if (GAMEBOARD[row - 1][col + 2] != 0) {
print();
system("pause");
return moveKnight(row - 1, col + 2, moveNum + 1);
}
else if (GAMEBOARD[row + 1][col + 2] != 0) {
print();
system("pause");
return moveKnight(row + 1, col + 2, moveNum + 1);
}
else if (GAMEBOARD[row + 2][col + 1] != 0) {
print();
system("pause");
return moveKnight(row + 2, col + 1, moveNum + 1);
}
else if (GAMEBOARD[row + 2][col - 1] != 0) {
print();
system("pause");
return moveKnight(row + 2, col - 1, moveNum + 1);
}
else if (GAMEBOARD[row + 1][col - 2] != 0) {
print();
system("pause");
return moveKnight(row + 1, col - 2, moveNum + 1);
}
else if (GAMEBOARD[row - 1][col - 2] != 0) {
print();
system("pause");
return moveKnight(row - 1, col - 2, moveNum + 1);
}
else if (GAMEBOARD[row - 2][col - 1] != 0) {
print();
system("pause");
return moveKnight(row - 2, col - 1, moveNum + 1);
}
return false;*/
else if (row - 2 >= 0 && row - 2 <= 7 && col + 1 >= 0
&& col + 1 <= 7 && GAMEBOARD[row - 2][col + 1] == 0) {
GAMEBOARD[row - 2][col + 1] = moveNum;
print();
system("pause");
return moveKnight(row - 2, col + 1, moveNum + 1);
}
else if (row - 1 >= 0 && row - 1 <= 7 && col + 2 >= 0
&& col + 2 <= 7 && GAMEBOARD[row - 1][col + 2] == 0) {
GAMEBOARD[row - 1][col + 2] = moveNum;
print();
system("pause");
return moveKnight(row - 1, col + 2, moveNum + 1);
}
else if (row + 1 >= 0 && row + 1 <= 7 && col + 2 >= 0
&& col + 2 <= 7 && GAMEBOARD[row + 1][col + 2] == 0) {
GAMEBOARD[row + 1][col + 2] = moveNum;
print();
system("pause");
return moveKnight(row + 1, col + 2, moveNum + 1);
}
else if (row + 2 >= 0 && row + 2 <= 7 && col + 1 >= 0
&& col + 1 <= 7 && GAMEBOARD[row + 2][col + 1] == 0) {
GAMEBOARD[row + 2][col + 1] = moveNum;
print();
system("pause");
return moveKnight(row + 2, col + 1, moveNum + 1);
}
else if (row + 2 >= 0 && row + 2 <= 7 && col - 1 >= 0
&& col - 1 <= 7 && GAMEBOARD[row + 2][col - 1] == 0) {
GAMEBOARD[row + 2][col - 1] = moveNum;
print();
system("pause");
return moveKnight(row + 2, col - 1, moveNum + 1);
}
else if (row + 1 >= 0 && row + 1 <= 7 && col - 2 >= 0
&& col - 2 <= 7 && GAMEBOARD[row + 1][col - 2] == 0) {
GAMEBOARD[row + 1][col - 2] = moveNum;
print();
system("pause");
return moveKnight(row + 1, col - 2, moveNum + 1);
}
else if (row - 1 >= 0 && row - 1 <= 7 && col - 2 >= 0
&& col - 2 <= 7 && GAMEBOARD[row - 1][col - 2] == 0) {
GAMEBOARD[row - 1][col - 2] = moveNum;
print();
system("pause");
return moveKnight(row - 1, col - 2, moveNum + 1);
}
else if (row - 2 >= 0 && row - 2 <= 7 && col - 1 >= 0
&& col - 1 <= 7 && GAMEBOARD[row - 2][col - 1] == 0) {
GAMEBOARD[row - 2][col - 1] = moveNum;
print();
system("pause");
return moveKnight(row - 2, col - 1, moveNum + 1);
}
// commented out
/*if (row - 2 < 0 || row - 2 > 7 || col + 1 < 0
|| col + 1 > 7 || GAMEBOARD[row - 2][col + 1] != 0) {
GAMEBOARD[row - 2][col + 1] = 0;
return moveKnight(row - 2, col + 1, moveNum + 1);
}
else if (row - 1 < 0 || row - 1 > 7 || col + 2 < 0
|| col + 2 > 7 || GAMEBOARD[row - 1][col + 2] != 0) {
GAMEBOARD[row - 1][col + 2] = 0;
return moveKnight(row - 1, col + 2, moveNum + 1);
}
else if (row + 1 < 0 || row + 1 > 7 || col + 2 < 0
|| col + 2 > 7 || GAMEBOARD[row + 1][col + 2] != 0) {
GAMEBOARD[row + 1][col + 2] = 0;
moveKnight(row + 1, col + 2, moveNum + 1);
return false;
}
else if (row + 2 < 0 || row + 2 > 7 || col + 1 < 0
|| col + 1 > 7 || GAMEBOARD[row + 2][col + 1] != 0) {
GAMEBOARD[row + 2][col + 1] = 0;
moveKnight(row + 2, col + 1, moveNum + 1);
return false;
}
else if (row + 2 < 0 || row + 2 > 7 || col - 1 < 0
|| col - 1 > 7 || GAMEBOARD[row + 2][col - 1] != 0) {
GAMEBOARD[row + 2][col - 1] = 0;
moveKnight(row + 2, col - 1, moveNum + 1);
return false;
}
else if (row + 1 < 0 || row + 1 > 7 || col - 2 < 0
|| col - 2 > 7 || GAMEBOARD[row + 1][col - 2] != 0) {
GAMEBOARD[row + 1][col - 2] = 0;
moveKnight(row + 1, col - 2, moveNum + 1);
return false;
}
else if (row - 1 < 0 || row - 1 > 7 || col - 2 < 0
|| col - 2 > 7 || GAMEBOARD[row - 1][col - 2] != 0) {
GAMEBOARD[row - 1][col - 2] = 0;
moveKnight(row - 1, col - 2, moveNum + 1);
return false;
}
else if (row - 2 < 0 || row - 2 > 7 || col - 1 < 0
|| col - 1 > 7 || GAMEBOARD[row - 2][col - 1] != 0) {
GAMEBOARD[row - 2][col - 1] = 0;
moveKnight(row - 2, col - 1, moveNum + 1);
return false;
}
*/
cout << endl << endl;
return false;
}
void print()
{
for (int row = 0; row <= 7; row++) {
for (int col = 0; col <= 7; col++) {
cout << setw(5) << GAMEBOARD[row][col];
}
cout << endl;
}
}
递归很棘手!我强烈建议您尝试在尝试编写代码之前考虑您的算法如何工作。
首先要明确定义您的基本案例。你做得很好。我们有:
if (moveNum == 64) {
return true;
}
现在,我们需要处理思考如何从每个位置处理骑士的8个可能的动作。我将使用一些sudo代码简化您的代码:
moves = [[2, 1], [2, 1], [-2, -1], etc...]; // 8 moves total
for (move : moves) {
newRow = row + move[0];
newCol = col + move[1];
if (InBounds(newRow, newCol) && GAMEBOARD[newRow][newCol] == 0) {
// Backtracking logic goes here
}
}
此代码本质上与您的IF语句相同,但使用和概念化更容易。
递归回溯基本上有2个步骤。首先,我们检查是否达到了基本案例。其次,我们处理恢复案件。通过递归回溯,这包括几个步骤:
- 做某事(在这种情况下,移动骑士(
- 进行递归调用以检查这是否导致解决方案
- 如果这导致解决方案,请告诉呼叫者此功能我们找到了解决方案。此外,您可能想使用找到的解决方案来做些事情。
- 这没有导致解决方案。撤消我们在第一步中所做的事情,看看其他递归情况是否导致解决方案
- 如果没有递归情况导致找到解决方案,请告诉呼叫者从当前位置找不到解决方案。
将此格式应用于骑士旅行:
- 在板上移动:
GAMEBOARD[newRow][newCol] = moveNum
- 测试此移动是否导致解决方案:
result = moveKnight(newRow, newCol, moveNum + 1)
- 如果我们找到了解决方案,则暂时返回true。
if (result) {return true;}
- 如果此举不起作用,请撤消我们所做的举动:
GAMEBOARD[newRow][newCol] = 0
。然后,我们应该看看其他递归情况是否导致解决方案。我的代码通过遍历每个动作来处理此操作。您通过执行一系列if/else语句来处理它。 - 从此陈述中没有任何动作,导致解决方案。我们应该
return false
表示此。
将所有这些放在一起,我们得到:
bool moveKnight(int row, int col, int moveNum) {
if (moveNum == 64) {
return true;
}
moves = [[2, 1], [2, 1], [-2, -1], etc...]; // 8 moves total
for (move : moves) {
int newRow = row + move[0];
int newCol = col + move[1];
if (InBounds(newRow, newCol) && GAMEBOARD[newRow][newCol] == 0) {
GAMEBOARD[newRow][newCol] = moveNum;
bool result = moveKnight(newRow, newCol, moveNum + 1);
if (result) {
return true;
} else {
// Undo this move
GAMEBOARD[newRow][newCol] = 0;
}
}
}
return false;
}
由于找到正确的解决方案时我们不会撤消移动,因此当moveKnight
返回true时,游戏板将包含解决方案。