基于C语言用递归算法实现马踏棋盘解法的计算

---

title: 基于C语言用递归算法实现马踏棋盘解法的计算
date: 2020-03-17 21:11:41
summary:
categories: 编程实例
tags: C语言
img:

基于C语言用递归算法实现马踏棋盘解法的计算
如有不懂欢迎提问

#include<stdio.h>

#define X 7//棋盘x
#define Y 7//棋盘y
#define A 1//起始横坐标
#define B 1//起始纵坐标

void house (int , int);//递归求解，依次传入横纵坐标
void printboard();//打印具体解法
void initialization();//棋盘初始化

int board[X + 4][Y + 4];//其中下标2至X+1或Y+1为棋盘
int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标

int main() {
	if (X <= 2 || Y <= 2 || X * Y > 10000) {
		//经测试，个人计算机计算10*10已经有些吃力
		printf("棋盘不合法!");
		return 0;
	}
	if (A > X || B > Y || A <= 0 || B <= 0) {
		printf("初始坐标不合法!");
		return 0;
	}
	printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
	initialization();
	board[A + 1][B + 1] = ++step;
	house(A, B);
	printf("\n\n计算完毕!\n");
	printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
	printf("共找到%d组解\n",sum);
	return 0;
}

void initialization() {
	int i, j;
	//给棋盘赋值0，周围赋值-1即不可走
	for (i = 0; i <= X + 3; i++) {
		for (j = 0; j <= Y + 3; j++) {
			if (i == 0 || i == 1 || i == X + 3 || i == X + 2 || j == 0 || j == 1 || j == Y + 3 || j == Y + 2)
				board[i][j] = -1;
			else
				board[i][j] = 0;
		}
	}
	return;
}

void house(int a , int b) {
	if (step == X*Y) {
		sum++;
		printboard();
		return;
	}
	for (int i = 0; i <= 7; i++) {
		if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
			step++;
			board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
			house(a+move[i][0], b+move[i][1]);
			board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
			step--;
		}
	}
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard() {
	int i, j, k;
	printf("\n第%d种解法：\n",sum);
	printf("┌───");
	for (i = 1; i <= Y- 1; i++) 
		printf("┬───");
	printf("┐\n");
	for ( i = 2; i <= X + 1; i++) {
		for ( j = 2; j <= Y + 1; j++) 
			printf("│%3.2d", board[i][j]);
		printf("│\n");
		if (i <= X) {
			printf("├───");
			for(k=1;k<=Y-1;k++)
				printf("┼───");
			printf("┤\n");
		}
	}
	printf("└───");
	for (i = 1; i <= Y - 1; i++)
		printf("┴───");
	printf("┘\n");
	return;
}

上文为了方便使用define来确定棋盘尺寸X、Y。如果想用scanf来确定，需要用到动态数组，并且需要向函数传递地址

#include<stdio.h>
#include<stdlib.h>//包含malloc

void house(int, int, int**);//递归求解，依次传入横纵坐标ab，二维数组指针
void printboard(int**);//传入二维数组指针，打印具体解法
void initialization(int**);//棋盘初始化，依次传入二维数组指针

int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标
int x, y;//定义全局变量

int main() {
	printf("马踏棋盘v2.0\n");
	printf("请输入棋盘大小x*y：\n");
	printf("x=");
	scanf("%d", &x);
	printf("y=");
	scanf("%d", &y);
	int a, b;//无需全局变量
	printf("请输入起始位置(a, b)，其中最小为(1, 1)：\n");
	printf("a=");
	scanf("%d", &a);
	printf("b=");
	scanf("%d", &b);
	int **board;
	board = (int**)malloc(sizeof(int *) * (x + 4));
	for (int i = 0; i < x + 4; i++) {
		board[i] = (int*)malloc(sizeof(int *) * (y + 4));
	}
	//相当于声明了动态数组board[x + 4][y + 4];其中下标2至X+1或Y+1为棋盘
	if (x <= 2 || x <= 2 || x * y > 10000) {
		//经测试，由于递归算法，计算10*10已经极为吃力
		printf("棋盘不合法!");
		return 0;
	}
	if (a > x || a > y || a <= 0 || a <= 0) {
		printf("初始坐标不合法!");
		return 0;
	}
	printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
	initialization(board);
	board[a + 1][a + 1] = ++step;
	house(a, b, board);
	printf("\n\n计算完毕!\n");
	printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
	printf("共找到%d组解\n", sum);
	return 0;
}

void initialization(int** board) {
	int i, j;
	//给棋盘赋值0，周围赋值-1即不可走
	for (i = 0; i <= x + 3; i++) {
		for (j = 0; j <= y + 3; j++) {
			if (i == 0 || i == 1 || i == x + 3 || i == x + 2 || j == 0 || j == 1 || j == y + 3 || j == y + 2)
				board[i][j] = -1;
			else
				board[i][j] = 0;
		}
	}
	return;
}

void house(int a, int b, int** board) {
	if (step == x*y) {
		sum++;
		printboard(board);
		return;
	}
	for (int i = 0; i <= 7; i++) {
		if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
			step++;
			board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
			house(a + move[i][0], b + move[i][1], board);
			board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
			step--;
		}
	}
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard(int **board) {
	int i, j, k;
	printf("\n第%d种解法：\n", sum);
	printf("┌───");
	for (i = 1; i <= y - 1; i++)
		printf("┬───");
	printf("┐\n");
	for (i = 2; i <= x + 1; i++) {
		for (j = 2; j <= y + 1; j++)
			printf("│%3.2d", board[i][j]);
		printf("│\n");
		if (i <= x) {
			printf("├───");
			for (k = 1; k <= y - 1; k++)
				printf("┼───");
			printf("┤\n");
		}
	}
	printf("└───");
	for (i = 1; i <= y - 1; i++)
		printf("┴───");
	printf("┘\n");
	return;
}

交流讨论等具体内容请访问我的博客

原文地址：https://boyinthesun.cn/post/c-house/