用c语言实现马踏棋盘问题

#include <stdio.h>

#define N 8
#define MAX_STEP N * N

int moves[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, 2}, {2, 1}, {2, -1}, {1, -2}}; // 马在棋盘上可能的8个移动方向

int board[N][N]; // 记录马在棋盘上的位置
int total_step; // 记录马走的总步数

void print_board() {
printf("Solution %d:\n", total_step);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
printf("%2d ", board[i][j]);
}
printf("\n");
}
}

int can_move(int x, int y) {
/* 判断坐标(x, y)是否越界，以及是否已经走过 */
if (x < 0 || x >= N || y < 0 || y >= N || board[x][y] != 0) {
return 0;
}
return 1;
}

void move(int x, int y) {
++total_step;
board[x][y] = total_step;
}

void unmove(int x, int y) {
board[x][y] = 0;
--total_step;
}

int find_path(int x, int y) {
move(x, y);
if (total_step == MAX_STEP) { // 已经走完了所有步数，找到了一组解
print_board();
return 1;
}
for (int i = 0; i < 8; ++i) {
int new_x = x + moves[i][0];
int new_y = y + moves[i][1];
if (can_move(new_x, new_y)) {
if (find_path(new_x, new_y)) { // 如果找到了解，直接返回
return 1;
}
}
}
unmove(x, y); // 所有方向都走不通，回溯
return 0;
}

int main() {
int start_x, start_y;
printf("Enter the starting position (x, y): ");
scanf("%d %d", &start_x, &start_y);
if (start_x < 0 || start_x >= N || start_y < 0 || start_y >= N) {
printf("Invalid starting position.\n");
return 0;
}
find_path(start_x, start_y);
return 0;
}