Home > 算法研究 > [算法]图算法之骑士遍历问题(象棋中马的遍历问题)分析,C语言实现

[算法]图算法之骑士遍历问题(象棋中马的遍历问题)分析,C语言实现

今天再讲点跟N皇后有关的问题,骑士遍历问题,或者象棋中马的遍历问题,当然这里的马是国际象棋了,两者有着很多相似点,同时又有很多不同点,主要还是限制路径的区别,N皇后主要是自由放置只要满足条件就好,马的遍历则跟上下遍历的路径有关了,主要运用了图算法之深度广度遍历,以及图的建立等算法。

要求:实现棋盘上任意位置的一个棋子马,使它不重复的走过棋盘上的每一个棋盘格

分析:首先知道马在棋盘是怎么走的,根据国际象棋规则,马在一个起始位置共有8个可用的行动位置,当然边界方面需要另外考虑,我们的马的行走必须考虑这8种类可能性,排除不能使用的位置,走可用的位置,当8个位置不可以使用的时,需要考虑返回上一步,这点有点像图的广度优先遍历相同,当马走完所有位置,同时没有可用的位置用于行走的时候遍历结束。


分析完毕 ,代码如下,如果各位有疑问,请留言:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*骑士遍历问题
*2008 12 28 CG
**/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
int f[11][11] ;
int adjm[121][121];
long fgf;
int n,m;
 
int es(int i1,int j1,int i2,int j2){
	adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
	adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
	return;/*建立路径连接*/
}/*es*/
 
int creatadjm(){/*绘制可用路径图*/
	int i,j;
	for(i=1;i< =n;i++)
		for(j=1;j<=n;j++)
			f[i][j]=0;/*初始化路径记录*/
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++)
			adjm[i][j]=0;/*初始化棋盘*/
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		if(f[i][j]==0){/*设置有效路径*/
			f[i][j]=1;
			if((i+2<=n)&&(j+1<=n)) es(i,j,i+2,j+1);
			if((i+2<=n)&&(j-1>=1)) es(i,j,i+2,j-1);
			if((i-2>=1)&&(j+1< =n)) es(i,j,i-2,j+1);
			if((i-2>=1)&&(j-1>=1)) es(i,j,i-2,j-1);
			if((j+2< =n)&&(i+1<=n)) es(i,j,i+1,j+2);
			if((j+2<=n)&&(i-1>=1)) es(i,j,i-1,j+2);
			if((j-2>=1)&&(i+1< =n)) es(i,j,i+1,j-2);
			if((j-2>=1)&&(i-1>=1)) es(i,j,i-1,j-2);
		}/*if*/
	return 1;
}/*createadjm*/
 
int travel(int p,int r){/*骑士遍历*/
	int i,j,q;
	for(i = 1 ; i < = n ; i++)
		for(j = 1 ; j <= n ;j++)
			if(f[i][j] > r)/*符合要求?*/
				f[i][j]=0;
	r = r + 1;
	i=((p-1) / n) + 1;
	j=((p-1) % n) + 1;
	f[i][j] = r;
	fgf++;/*记录路径选择记录*/
	for(q = 1 ; q < = m ; q++){
		i=((q-1) / n) + 1;
		j=((q-1) % n) + 1;
		if((adjm[p][q] == 1) && (f[i][j] == 0))
			travel(q , r);/*递归遍历*/
	}/*for*/
	return 1;
}/*travel*/
 
int main(){
	int i,j,k,l;
	clrscr();
	printf("Input chessboard size n:");scanf("%d",&n);/* 输入棋盘大小,最大11*/
	m = n * n;
	creatadjm();/*绘制可用路径*/
	/*输出可用路径
	for(i=1;i<=m;i++){/*输出*/
		for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
			printf("n");
	}
	getchar();
	*/
	printf("Input  a start post i,j:");/*输入开始遍历的起点*/
	scanf("%d %d",&i,&j);
	l = (i - 1) * n + j;
	while ((i > 0) || (j > 0)){/*循环直到输入 0 0*/
		for(i = 1 ; i < = n ; i++)
			for(j = 1 ; j <= n ; j++)
				f[i][j] = 0;/*初始化路径记录*/
	k = 0;
	travel(l , k);/*遍历*/
	printf("select: %d pathnfinal path:n",fgf);/*输出路径选择次数*/
		fgf=0;/*清零*/
	for(i = 1 ; i <= n ; i++){/*输出遍历路径*/
		for(j = 1 ; j <= n ; j++)
			printf("%4d",f[i][j]);
		printf("n");
	}
	printf("Input a start post i,j:");scanf("%d %d",&i,&j);/*继续输入*/
	l = (i - 1) * n + j;
	}/*while*/
	return 0;
}/*main*/
Categories: 算法研究 Tags: , ,
  1. December 28th, 2008 at 20:05 | #1

    代码,天啊。别让我看到。累。

  2. December 30th, 2008 at 11:07 | #2

    以后有问题就到博主这边留言等你解决 呵呵·!

  3. December 30th, 2008 at 13:44 | #3

    好的,非常欢迎您的提问,我会尽快解决你的问题

  4. LittlePig
    January 28th, 2009 at 12:48 | #4

    代码有点小难看.. 可以改精炼些.

  5. January 30th, 2009 at 11:34 | #5

    感谢,我这里的代码主要是提供给初学者使用,因而提供完整代码以便调试使用

  1. No trackbacks yet.