knight.c

经典的骑士漫游问题的算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define SIZE 8
int move(int[][SIZE],int[][SIZE],int*,int*);

main()
{
	int times=1,x,y,counter;
	srand(time(NULL));
	do{
		printf("输入起始位置(x,y):");
		scanf("%d,%d",&x,&y);
	}while(x>7 || y>7 || x<0 ||y<0);
	do{
		int board[SIZE][SIZE]={0},
			accessibility[SIZE][SIZE]={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}},
			row=x,column=y,flag=1;
		counter=1;
		printf("第%d次尝试\n",times);
		do{
			board[row][column]=1;
			printf("(%d,%d)\t",row,column);
			flag=move(board,accessibility,&row,&column);
			counter++;
		}while(counter<=64 && flag==1);
		if(counter<=64)
			printf("\n失败!!!\n\n");
		times++;
	}while(counter!=65);
	printf("\n成功!!!\n\n");
	return 0;
}

int move(int board[][SIZE],int accessibility[][SIZE],int *row,int *column)
{
	int choice[SIZE]={0,1,2,3,4,5,6,7},
		kind[SIZE][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}},
		accessRow,accessColumn,temp,i,n,a,b,
		min=9,flag=0;
	
	for(i=0;i<=SIZE-1;i++){		//随机排列移动种类
		n=1+rand()%7;
		temp=choice[n];
		choice[n]=choice[i];
		choice[i]=temp;
	}

	for(i=1;i<=SIZE-1;i++){
		accessRow=*row+kind[choice[i]][0];
		accessColumn=*column+kind[choice[i]][1];
		if(accessRow>=0 && accessRow<=SIZE-1
			&& accessColumn>=0 && accessColumn<=SIZE-1
			&& board[accessRow][accessColumn]==0){		//判断是否越界
			accessibility[accessRow][accessColumn]--;		//削减未访问方块的可访问能力值
			if(min>accessibility[accessRow][accessColumn]){		//选择最低访问能力值方块
				min=accessibility[accessRow][accessColumn];
				a=accessRow;
				b=accessColumn;
				flag=1;
			}
		}
	}

	*row=a;		//移动至最低访问能力值方块
	*column=b;
	return flag;
}