有趣的数据结构算法18——马踏棋盘问题（骑士周游问题）的C语言实现（回溯法）及其解析

灰太狼 2021-10-30 02:28 745阅读 0赞

### 有趣的数据结构算法18——马踏棋盘问题（骑士周游问题）的C语言实现（回溯法）及其解析 ###

*  问题复述
 *  题目分析
 *  利用c语言实现马踏棋盘问题
 *  GITHUB下载连接

马踏棋盘问题就是要求使用国际象棋的棋子马?，走过全部的棋盘，我一想到国际象棋的棋盘有8\*8的大小，一匹马只能斜着跳，我就知道我的脑子解决不了这个问题。  
我的脑子解决不了，computer可以啊！  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 问题复述 #

将马随机放在国际象棋的8\*8的某个方格中，马按走棋规则（斜着走）进行移动。仅仅使用63步走遍棋盘上的全部方格。求出马的行走路线。将数字1，2，…，64依次填入一个8×8的方阵，并输出。

# 题目分析 #

本文采用回溯法解决马踏棋盘问题。  
回溯法是一种选优搜索法，不断尝试并向前搜索，以达到目标。但当探索到某一步时，发现无法实现目标，就退回一步重新选择更优秀的方式进行搜索，这种走不通就退回再重新走的方法被称作回溯法。  
本文将程序的子函数分为两个部分，第一部分函数用于寻找当马处于x，y时，下一步可以走向哪个方向，**该函数通过count尝试不同方向的跳跃，判断是否能够进行该方向的跳跃**。当count处于0~7时，跳跃方向如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
其c语言函数的实现如下：

//找到当马位于(x，y)位置的时候，下一个可走的位置
    int nextxy(int *x, int *y, int count)
    {
        
    	switch (count){
        
    
    	case 0:
    		if (*x + 2 < X && *y - 1 >= 0 && !chess[*x + 2][*y - 1]){
        
    			*x += 2;
    			*y -= 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 1:
    		if (*x + 2 < X && *y + 1 < Y && !chess[*x + 2][*y + 1]){
        
    			*x += 2;
    			*y += 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 2:
    		if (*x + 1 < X && *y - 2 >= 0 && !chess[*x + 1][*y - 2]){
        
    			*x += 1;
    			*y -= 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 3:
    		if (*x + 1 < X && *y + 2 < Y && !chess[*x + 1][*y + 2]){
        
    			*x += 1;
    			*y += 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 4:
    		if (*x - 2 >= 0 && *y - 1 >= 0 && !chess[*x - 2][*y - 1]){
        
    			*x -= 2;
    			*y -= 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 5:
    		if (*x - 2 >= 0 && *y + 1 <Y && !chess[*x - 2][*y + 1]){
        
    			*x -= 2;
    			*y += 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 6:
    		if (*x - 1 >= 0 && *y - 2 >= 0 && !chess[*x - 1][*y - 2]){
        
    			*x -= 1;
    			*y -= 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 7:
    		if (*x - 1 >= 0 && *y + 2 < Y && !chess[*x - 1][*y + 2]){
        
    			*x -= 1;
    			*y += 2;
    			return 1;
    		}
    		return 0;
    		break;
    	default :
    		return 0;
    		break;
    	}
    }

第二部分函数是回溯法的主体部分。  
**当马处于某一个x，y的时候，其会根据count的值由0至7，尝试八个方向；  
初始化tag为1，当tag最后增加到64时，代表棋盘上每一个落位都放上了棋子；  
当某一条路走不通时，该函数会返回上一个点继续重试。  
如果可以正常落子则return 1;**  
其c语言函数的实现如下：

// 深度优先遍历
    // (x,y)为位置坐标
    // tag是一个标记变量，每走一步，tag+1
    int travel(int x,int y,int tag){
        
    	int x1 = x, y1 = y, flag = 0, count = 0;
    	chess[x][y] = tag;
    
    	if (tag == X*Y){
         //当棋盘已经布满的时候
    		// 打印棋盘
    		for (int i = 0; i < X; i++){
        
    			for (int j = 0; j < Y; j++){
        
    				printf("%2d ", chess[i][j]);
    			}
    			printf("\n");
    		}
    		printf("\n");
    		return 1;
    	}
    	//尝试8个位置
    	flag = nextxy(&x1, &y1, count);
    	while (0 == flag&&count < 7){
        
    		count++;
    		flag = nextxy(&x1, &y1, count);
    	}
    
    	while (flag){
        
    		if(travel(x1, y1, tag + 1)){
        
    			return 1;
    		}
    		//返回上一个点，重试。
    		x1 = x;
    		y1 = y;
    		count++;
    		flag = nextxy(&x1, &y1, count);
    		while (0 == flag && count < 7){
        
    			count++;
    			flag = nextxy(&x1, &y1, count);
    		}
    		//找到马的下一步可走坐标，则flag = 1，否则为0。
    	}
    	if (flag == 0){
        
    		chess[x][y] = 0;
    	}
    	return 0;
    }

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

代码源自鱼c工作室。

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    #define X 8
    #define Y 8
    
    int chess[X][Y];
    
    //找到当马位于(x，y)位置的时候，下一个可走的位置
    int nextxy(int *x, int *y, int count)
    {
        
    	switch (count){
        
    
    	case 0:
    		if (*x + 2 < X && *y - 1 >= 0 && !chess[*x + 2][*y - 1]){
        
    			*x += 2;
    			*y -= 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 1:
    		if (*x + 2 < X && *y + 1 < Y && !chess[*x + 2][*y + 1]){
        
    			*x += 2;
    			*y += 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 2:
    		if (*x + 1 < X && *y - 2 >= 0 && !chess[*x + 1][*y - 2]){
        
    			*x += 1;
    			*y -= 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 3:
    		if (*x + 1 < X && *y + 2 < Y && !chess[*x + 1][*y + 2]){
        
    			*x += 1;
    			*y += 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 4:
    		if (*x - 2 >= 0 && *y - 1 >= 0 && !chess[*x - 2][*y - 1]){
        
    			*x -= 2;
    			*y -= 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 5:
    		if (*x - 2 >= 0 && *y + 1 <Y && !chess[*x - 2][*y + 1]){
        
    			*x -= 2;
    			*y += 1;
    			return 1;
    		}
    		return 0;
    		break;
    	case 6:
    		if (*x - 1 >= 0 && *y - 2 >= 0 && !chess[*x - 1][*y - 2]){
        
    			*x -= 1;
    			*y -= 2;
    			return 1;
    		}
    		return 0;
    		break;
    	case 7:
    		if (*x - 1 >= 0 && *y + 2 < Y && !chess[*x - 1][*y + 2]){
        
    			*x -= 1;
    			*y += 2;
    			return 1;
    		}
    		return 0;
    		break;
    	default :
    		return 0;
    		break;
    	}
    }
    
    // 深度优先遍历
    // (x,y)为位置坐标
    // tag是一个标记变量，每走一步，tag+1
    int travel(int x,int y,int tag){
        
    	int x1 = x, y1 = y, flag = 0, count = 0;
    	chess[x][y] = tag;
    
    	if (tag == X*Y){
         //当棋盘已经布满的时候
    		// 打印棋盘
    		for (int i = 0; i < X; i++){
        
    			for (int j = 0; j < Y; j++){
        
    				printf("%2d ", chess[i][j]);
    			}
    			printf("\n");
    		}
    		printf("\n");
    		return 1;
    	}
    	//尝试8个位置
    	flag = nextxy(&x1, &y1, count);
    	while (0 == flag&&count < 7){
        
    		count++;
    		flag = nextxy(&x1, &y1, count);
    	}
    
    	while (flag){
        
    		if(travel(x1, y1, tag + 1)){
        
    			return 1;
    		}
    		//返回上一个点，重试。
    		x1 = x;
    		y1 = y;
    		count++;
    		flag = nextxy(&x1, &y1, count);
    		while (0 == flag && count < 7){
        
    			count++;
    			flag = nextxy(&x1, &y1, count);
    		}
    		//找到马的下一步可走坐标，则flag = 1，否则为0。
    	}
    	if (flag == 0){
        
    		chess[x][y] = 0;
    	}
    	return 0;
    }
    
    void main(){
        
    	clock_t start, finish;
    	start = clock();
    	for (int i = 0; i < X; i++){
        
    		for (int j = 0; j < Y; j++){
        
    			chess[i][j] = 0;
    		}
    	}
    	if (!travel(2, 0, 1)){
        
    		printf("该起始点无法遍历全局。");
    	}
    	for (int i = 0; i < X; i++){
        
    		for (int j = 0; j < Y; j++){
        
    			printf("%2d ", chess[i][j]);
    		}
    		printf("\n");
    	}
    	printf("\n");
    
    	finish = clock();
    	printf("本次计算共用%f", double(finish-start)/CLOCKS_PER_SEC);
    
    }

# GITHUB下载连接 #

https://github.com/bubbliiiing/Data-Structure-and-Algorithm

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: /images/20211029/db5faf3f3dd8425c97362e273e03cb50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20211029/3fa1c35b8bc84e90be048818c8dc84b4.png