马踏棋盘

c代码

#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数组中。

请注意，该算法并不能保证一定能找到马踏棋盘问题的解，因为在某些起始位置和棋盘大小的情况下，可能无法找到完整的遍历路径。

度数在这里代表什么?

在这里，"度数"指的是马在当前位置的下一个可能移动位置的可访问格子数量。也可以将其理解为下一个位置的邻居节点数。

在代码中，通过计算每个可能的移动位置的度数，可以评估每个位置的可达性。度数越小表示该位置的可访问格子数量越少，即相对来说更"紧凑"。在马踏棋盘问题中，选择度数最小的位置作为下一步移动的目标，有助于保持马的移动范围广阔，增加找到解的可能性。

通过选择度数最小的位置作为下一步移动目标，可以尽量避免陷入死胡同或者无法继续遍历的局面。这种策略在一定程度上增加了找到马踏棋盘问题解的概率。

马踏棋盘问题中，度数最小的位置是否一定是下一步移动的最佳选择？

在马踏棋盘问题中，度数最小的位置不一定是下一步移动的最佳选择。尽管选择度数最小的位置有助于保持马的移动范围广阔，但并不能保证一定能找到问题的解。

马踏棋盘问题是一个非常复杂的组合问题，具有高度的分支因子和状态空间。在某些情况下，选择度数最小的位置可能导致陷入局部最优解，从而无法找到全局最优解，或者根本找不到解。

在某些特定的起始位置和棋盘大小下，可能存在一些特殊的路径或遍历顺序，使得度数最小的位置并不是最佳的选择。因此，仅凭度数最小来确定下一步移动的位置并不能保证找到最佳解。

为了提高找到最佳解的概率，通常需要采用更加复杂的算法和启发式策略，例如回溯算法、深度优先搜索、广度优先搜索、剪枝等。这些算法可以考虑更多的因素，如节点的可达性、棋盘上的局部结构、路径的延伸性等，以更有效地搜索解空间并找到更优的解。

因此，在解决马踏棋盘问题时，度数最小的位置可以作为一种启发式指导，但不能保证一定是下一步移动的最佳选择，需要结合其他算法和策略来综合评估和确定下一步的移动位置。

python代码

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()