马踏棋盘：（八皇后+迷宫）

将马随机放在国际象棋的Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。，走遍棋盘上全部64个方格。编制递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。将每个格子作为起始位置。求所有解。

思想：马踏棋盘：（八皇后+迷宫）

8*8的棋盘，其中最中间的格子，马按日走，共有八个方向，边框的格子并没有八个方向，角的格子更少，为使问题简单化，可以在存储棋盘时，在棋盘的外围在家两层格子，但不可走，这样可走的每个格子都有八个方向（但每个方向不一定可以走），使得问题得到普遍化。

对于每个格子的八个方向依次进行试探，看其是否可走（包含这个格子本身是否为可行走的格子，与是由走过），若某方向可走，便对其标记，并踏上去，将此格子作为新的格子依次试探其八个方向；若不可走，则返回上一个格子，撤除标记，继续试探未试探的其他方向。依次循环，当踏遍64个格子时，便可得到一组解，。

要得到以一个起始位置的所有解，则当找到一组解时，将其输出，返回上一个格子，继续试探其他方向。找到新的一组解，输出，返回，当此格子的方向试探完毕，返回上一层，试探上一层的剩余方向，依次循环，便可得到所有解。

所需借助的存储工具：

1.棋盘：根据思想，需用一个12*12的二维数组来存放整个棋盘。

2.各个方向：需要一个8*2的二维数组来存放八个方向所对应的操作数。

马踏棋盘：（八皇后+迷宫）

3.需要一个整形变量来存放踏了多少个格子；

伪代码：

horse （int x , int y）{ //起始位置

}

用C语言描述的代码：

//马踏棋盘 
#include <stdio.h>

int checher[12][12]={0};
int cnt=1;
int move[8][2]={1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2};            //下标0代表x  1代表y 
int num=1; 

void print (){
	for(int i=2;i<10;i++){
		for(int j=2;j<10;j++)
			printf("%5d",checher[i][j]);
		printf("\n");
	}
}

void horse (int x,int y){
	int new_x=0,new_y=0;
	for(int i=0;i<8;i++){
		new_x=x+move[i][0];
		new_y=y+move[i][1];
		if(checher[new_y][new_x]==0){
			checher[new_y][new_x]=++cnt;
			if(cnt==64){
				printf("这是第%d组解:\n",num);
				num++;
				print();
			}
			horse(new_x,new_y);
			checher[new_y][new_x]=0;
			--cnt;
		}
	}
}

int main (void){
	for(int i=0;i<12;i++)
		checher[0][i]=checher[1][i]=checher[i][0]=checher[i][1]=checher[11][i]=checher[10][i]=checher[i][10]=checher[i][11]=1;
	checher[2][2]=1;
	horse(2,2);
}

马踏棋盘：（八皇后+迷宫）

相关推荐