骑士巡游问题
什么是骑士巡游问题？
在骑士巡游问题中，我们给定一个大小为NxN的空棋盘和一匹骑士。在国际象棋中，骑士是一种外形酷似马的棋子。假设它可以从棋盘上的任意位置出发。现在，我们的任务是检查骑士是否可以访问棋盘上的所有方格。如果它可以访问所有方格，则打印从起点到达该位置所需的跳跃次数。
骑士可以通过两种方式完成巡游。第一种方式是，骑士移动一步并返回起始位置，形成一个循环，这称为闭环。第二种方式，即开路，它会在棋盘上的任何位置结束。
对于不熟悉国际象棋的人来说，请注意，骑士的走法很特殊。它可以水平移动两格，垂直移动一格，也可以在每个方向上垂直移动两格，水平移动一格。因此，完整的走法看起来像英文字母"L"。
假设给定的国际象棋棋盘大小为8，骑士位于棋盘左上角。接下来的可能走法如下所示 −
上图棋盘中的每个格子都有一个数字，表示骑士从哪里开始以及需要多少步才能到达该格子。格子的最终值将由以下矩阵表示 −
0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
请记住，这个问题可能有多个解，上面的矩阵只是其中一种可能的解。
解决骑士巡游问题的一种方法是逐一生成所有巡游路径，然后检查它们是否满足指定的约束条件。然而，这种方法既耗时又低效。
回溯法解决骑士巡游问题
另一种解决这个问题的方法是使用回溯法。回溯法会尝试各种可能性，直到找到解或尝试完所有选项。它包括选择一步棋、执行一步棋，然后递归地尝试解决问题的其余部分。如果当前移动导致死胡同，我们将回溯并撤销该移动，然后尝试下一个移动。
要使用回溯方法解决骑士的旅程问题，请按照以下步骤操作 −
从棋盘上的任意单元格开始，并将其标记为骑士已访问过。
将骑士移动到一个有效的未访问单元格，并将其标记为已访问。从任意单元格开始，骑士最多可以移动 8 步。
如果当前单元格无效或不适用于解决方案，则回溯并尝试其他可能找到解决方案的移动方式。
重复此过程，直到骑士的移动次数等于 8 x 8 = 64。
示例
在下面的示例中，我们将实际演示如何解决骑士的巡回问题。
#include <stdio.h>
#define N 8
int sol[N][N];
//检查地点是否在范围内且尚未分配
int isValid(int x, int y) {
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
printf("The possible solution:
");
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
printf("%3d ", sol[x][y]);
printf("
");
}
}
int knightTour(int x, int y, int move, int xMove[N], int yMove[N]) {
int xNext, yNext;
//当整个棋盘被覆盖时
if (move == N*N)
return 1;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//检查房间是否有人
if (isValid(xNext, yNext)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, xMove, yMove) == 1)
return 1;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return 0;
}
int findKnightTourSol() {
//最初将解矩阵的所有值设置为 -1
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//骑士的所有可能走法
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//starting from room (0, 0)
sol[0][0] = 0;
if (knightTour(0, 0, 1, xMove, yMove) == 0) {
printf("Solution does not exist");
return 0;
} else
displaySolution();
return 1;
}
int main() {
findKnightTourSol();
return 0;
}
#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
//检查地点是否在范围内且尚未分配
bool isValid(int x, int y, int sol[N][N]) {
return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
cout << "The possible solution: " << endl;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << setw(3) << sol[x][y] << " ";
cout << endl;
}
}
int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
int xNext, yNext;
//当整个棋盘被覆盖时
if (move == N*N)
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//检查房间是否有人
if (isValid(xNext, yNext, sol)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
return true;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return false;
}
bool findKnightTourSol() {
//最初将解矩阵的所有值设置为 -1
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
//骑士的所有可能走法
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
//starting from room (0, 0)
sol[0][0] = 0;
if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
cout << "Solution does not exist";
return false;
} else
displaySolution();
return true;
}
int main() {
findKnightTourSol();
}
import java.util.Arrays;
public class Main {
static final int N = 8;
static int[][] sol = new int[N][N];
//检查地点是否在范围内且尚未分配
static boolean isValid(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
static void displaySolution() {
System.out.println("The possible solution: ");
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
System.out.printf("%3d ", sol[x][y]);
System.out.println();
}
}
static boolean knightTour(int x, int y, int move, int[] xMove, int[] yMove) {
int xNext, yNext;
//当整个棋盘被覆盖时
if (move == N*N)
return true;
for (int k = 0; k < 8; k++) {
xNext = x + xMove[k];
yNext = y + yMove[k];
//检查房间是否有人
if (isValid(xNext, yNext)) {
sol[xNext][yNext] = move;
if (knightTour(xNext, yNext, move+1, xMove, yMove))
return true;
else
// backtracking
sol[xNext][yNext] = -1;
}
}
return false;
}
static boolean findKnightTourSol() {
//最初将解矩阵的所有值设置为 -1
for (int[] row : sol)
Arrays.fill(row, -1);
//骑士的所有可能走法
int[] xMove = {2, 1, -1, -2, -2, -1, 1, 2};
int[] yMove = {1, 2, 2, 1, -1, -2, -2, -1};
//starting from room (0, 0)
sol[0][0] = 0;
if (!knightTour(0, 0, 1, xMove, yMove)) {
System.out.println("Solution does not exist");
return false;
} else
displaySolution();
return true;
}
public static void main(String[] args) {
findKnightTourSol();
}
}
N = 8
# 解决方案矩阵
sol = [[-1 for _ in range(N)] for _ in range(N)]
# 检查地点是否在范围内且尚未分配
def isValid(x, y):
return (x >= 0 and x < N and y >= 0 and y < N and sol[x][y] == -1)
# 打印解决方案的函数
def displaySolution():
print("The possible solution: ")
for x in range(N):
for y in range(N):
print(f"{sol[x][y]:3}", end=" ")
print()
# 递归函数解决问题
def knightTour(x, y, move, xMove, yMove):
if move == N*N:
return True
for k in range(8):
xNext = x + xMove[k]
yNext = y + yMove[k]
if isValid(xNext, yNext):
sol[xNext][yNext] = move
if knightTour(xNext, yNext, move+1, xMove, yMove):
return True
else:
# Backtracking
sol[xNext][yNext] = -1
return False
def findKnightTourSol():
# 骑士的所有可能走法
xMove = [2, 1, -1, -2, -2, -1, 1, 2]
yMove = [1, 2, 2, 1, -1, -2, -2, -1]
# Starting from room (0, 0)
sol[0][0] = 0
if not knightTour(0, 0, 1, xMove, yMove):
print("Solution does not exist")
return False
else:
displaySolution()
return True
if __name__ == "__main__":
findKnightTourSol()
输出
The possible solution: 0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
