跳马.c

骑士遍历问题源代码

/*
  Name: 跳马问题 
  Copyright: 
  Author: 
  Date: 04-12-04 17:46
  Description: 
*/

#include<stdio.h>

int row[8]={1,2,2,1,-1,-2,-2,-1};/*8个方向上的x增量*/
int col[8]={-2,-1,1,2,2,1,-1,-2}; /*8个方向上的y增量*/
int h[5][5];/*记录走的路径*/
int num;/*记录方案个数*/ 

void printSolution();
void try(int,int,int); 

main()
{
	int row,col;
	/*初始化*/
	num=0;
	for(row=0;row<=4;row++)
		for(col=0;col<=4;col++)	
			h[row][col]=0;
	
	/*占据位置（0,0）*/ 
 	h[0][0]=1;
	/*从(0,0)除法，为第二步找位置*/  	 
  	try(0,0,2);
  	
  	/*输出总方案数*/ 
  	printf("总方案数为%d",num); 
  	
  	system("pause");

} 

/*从（x，y）出发，为第i步找合适位置*/ 
void try(int x,int y,int i)
{
    int dir,u,v;
    
    if (i>25) /*已经走完25步，则统计方案个数，打印方案，跳出递归*/
   	{
        num++;
        if (num<=3)/*打印前5种方案*/
            printSolution();
    }     
   	else
        for(dir=0;dir<=7;dir++) /*依次试遍8个方向*/
        {
            u=x+row[dir]; /*得到的新坐标*/ 
            v=y+col[dir];
            if ((u>=0) && (u<=4) && (v>=0) && (v<=4) && (h[u][v]==0))/*如果新坐标在棋盘上，并且这一格可以走*/
            {
                h[u][v]=i;/*占据位置[u,v]*/ 
                try(u,v,i+1); 
                h[u][v]=0;
            }
        } 
} 

/*打印方案*/
void printSolution()
{
    int row,col;
  
    for(row=0;row<=4;row++)
	{ 
		for(col=0;col<=4;col++)	
        	printf("%4d",h[row][col]);
 	    printf("\n");
    }            
    printf("\n\n");
}