#include <stdio.h>
#include <stdbool.h>
#define SIZE 8
int move_x[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int move_y[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool is_valid_move(int x, int y, int board[SIZE][SIZE]) {
if (x >= 0 && x < SIZE && y >= 0 && y < SIZE && board[x][y] == -1) {
return true;
}
return false;
}
void print_board(int board[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf("%2d ", board[i][j]);
}
printf("\n");
}
}
void solve_knight_tour(int start_x, int start_y) {
int board[SIZE][SIZE];
int move_count = 1;
// 初始化棋盘
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
board[i][j] = -1;
}
}
int x = start_x;
int y = start_y;
board[x][y] = move_count;
while (move_count < SIZE * SIZE) {
int min_deg = SIZE + 1;
int min_index = -1;
int next_x, next_y;
// 尝试所有可能的移动
for (int i = 0; i < 8; i++) {
next_x = x + move_x[i];
next_y = y + move_y[i];
if (is_valid_move(next_x, next_y, board)) {
int deg = 0;
// 计算下一个位置的度数
for (int j = 0; j < 8; j++) {
int new_x = next_x + move_x[j];
int new_y = next_y + move_y[j];
if (is_valid_move(new_x, new_y, board)) {
deg++;
}
}
// 更新最小度数和对应的索引
if (deg < min_deg) {
min_deg = deg;
min_index = i;
}
}
}
// 没有找到合适的下一步移动位置
if (min_index == -1) {
break;
}
// 移动到下一个位置
x += move_x[min_index];
y += move_y[min_index];
board[x][y] = ++move_count;
}
// 输出结果
print_board(board);
}
int main(int argc, char *argv[]) {
int start_x, start_y;
// printf("请输入马的初始位置(x, y):");
// scanf("%d %d", &start_x, &start_y);
// start_x = 2;
// start_y = 2;
start_x = *argv[1] - '0';
start_y = *argv[2] - '0';
// printf("%d %d",start_x,start_y);
solve_knight_tour(start_x, start_y);
return 0;
}
这段代码使用一个while循环来控制马的移动,直到访问了棋盘上的所有格子(move_count达到SIZE * SIZE)或者无法找到合适的下一步移动位置。
在每次循环迭代中,首先初始化min_deg为SIZE + 1,min_index为-1,用来记录最小度数和对应的索引。next_x和next_y是下一个可能的移动位置的坐标。
接下来,通过一个for循环尝试所有可能的移动方式。对于每一种移动方式,计算出下一个位置的坐标next_x和next_y。然后使用is_valid_move函数判断下一个位置是否是一个有效的移动位置。如果是,进入内部的计算度数的循环。
在内部的循环中,通过move_x和move_y数组计算出下一个位置的所有可能移动方式。然后使用is_valid_move函数判断每个可能的移动位置是否有效。如果是,将度数deg加一。
完成内部的循环后,比较当前位置的度数deg和最小度数min_deg的大小。如果deg小于min_deg,则更新min_deg为deg,同时更新min_index为当前移动方式的索引i。
完成所有移动方式的尝试后,判断min_index是否仍然为-1。如果是,表示无法找到合适的下一步移动位置,即无法继续遍历所有格子。在这种情况下,跳出while循环。
如果找到了合适的下一步移动位置,将马移动到该位置。更新当前位置的坐标x和y为下一个位置的坐标next_x和next_y,然后将move_count加一,并将其赋值给当前位置的board数组。这表示马已经访问了该位置。
当循环结束后,solve_knight_tour函数就完成了马踏棋盘问题的求解,棋盘上每个格子的访问顺序已经被记录在board数组中。
请注意,该算法并不能保证一定能找到马踏棋盘问题的解,因为在某些起始位置和棋盘大小的情况下,可能无法找到完整的遍历路径。
在这里,"度数"指的是马在当前位置的下一个可能移动位置的可访问格子数量。也可以将其理解为下一个位置的邻居节点数。
在代码中,通过计算每个可能的移动位置的度数,可以评估每个位置的可达性。度数越小表示该位置的可访问格子数量越少,即相对来说更"紧凑"。在马踏棋盘问题中,选择度数最小的位置作为下一步移动的目标,有助于保持马的移动范围广阔,增加找到解的可能性。
通过选择度数最小的位置作为下一步移动目标,可以尽量避免陷入死胡同或者无法继续遍历的局面。这种策略在一定程度上增加了找到马踏棋盘问题解的概率。
在马踏棋盘问题中,度数最小的位置不一定是下一步移动的最佳选择。尽管选择度数最小的位置有助于保持马的移动范围广阔,但并不能保证一定能找到问题的解。
马踏棋盘问题是一个非常复杂的组合问题,具有高度的分支因子和状态空间。在某些情况下,选择度数最小的位置可能导致陷入局部最优解,从而无法找到全局最优解,或者根本找不到解。
在某些特定的起始位置和棋盘大小下,可能存在一些特殊的路径或遍历顺序,使得度数最小的位置并不是最佳的选择。因此,仅凭度数最小来确定下一步移动的位置并不能保证找到最佳解。
为了提高找到最佳解的概率,通常需要采用更加复杂的算法和启发式策略,例如回溯算法、深度优先搜索、广度优先搜索、剪枝等。这些算法可以考虑更多的因素,如节点的可达性、棋盘上的局部结构、路径的延伸性等,以更有效地搜索解空间并找到更优的解。
因此,在解决马踏棋盘问题时,度数最小的位置可以作为一种启发式指导,但不能保证一定是下一步移动的最佳选择,需要结合其他算法和策略来综合评估和确定下一步的移动位置。
import sys
from time import sleep
import numpy as np
import matplotlib.pyplot as plt
lines = sys.stdin.readlines()
# 删除换行符并转换为整数
lines = np.array([list(map(int, line.strip().split())) for line in lines])
# lines是一个矩阵,每个点的值代表该点的访问顺序
# 例如,lines[0][0] = 1,代表第一个访问的点是(0, 0)
# lines[0][1] = 34,代表第三十四个访问的点是(0, 1)
# lines[1][0] = 4,代表第四个访问的点是(1, 0)
order_x = []
order_y = []
count = 1
while count <= len(lines)**2:
for i in range(len(lines)):
for j in range(len(lines)):
if lines[i][j] == count:
order_x.append(i)
order_y.append(j)
count += 1
# 绘制棋盘
plt.figure(figsize=(8, 8))
# 绘制棋盘的格子
for i in range(len(lines)+1):
plt.plot([i, i], [0, len(lines)], color='black')
plt.plot([0, len(lines)], [i, i], color='black')
count = 1
# 绘制马的行走路线
for i in range(len(order_x)-1):
plt.plot([order_x[i]+0.5, order_x[i+1]+0.5], [order_y[i]+0.5, order_y[i+1]+0.5], color='red', )
plt.scatter(order_x[i]+0.5, order_y[i]+0.5, color='red')
# 加上序号
plt.text(order_x[i]+0.5, order_y[i]+0.5, str(count), fontsize=12)
count += 1
plt.pause(0.01)
# 绘制最后一个点
plt.scatter(order_x[-1]+0.5, order_y[-1]+0.5, color='red')
plt.text(order_x[-1]+0.6, order_y[-1]+0.6, str(count), fontsize=12)
plt.show()