knight.c

1． 我们采用了回溯法和贪婪策略来求解国际象棋中的骑士巡游问题。对于棋盘中的每个位置最多只有8个方向可以选择

#include<stdio.h>

#define WIDTH 6
#define MAX_DIR 8 //表示没有方向可选

int chessboard[WIDTH][WIDTH]={0}; //棋盘数组
int direction[WIDTH][WIDTH];
int cur_x,cur_y; //当前坐标
int step; //已走的步数
int last_direction; //上一次走的方向

// 下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化
int var_x[MAX_DIR];
int var_y[MAX_DIR];

//八个方向的坐标变化情况
void init_direction()
{
	var_x[0] = -2; var_y[0] = -1;
	var_x[1] = -1; var_y[1] = -2;
	var_x[2] = 1; var_y[2] = -2;
	var_x[3] = 2; var_y[3] = -1;
	var_x[4] = 2; var_y[4] = 1;
	var_x[5] = 1; var_y[5] = 2;
	var_x[6] = -1; var_y[6] = 2;
	var_x[7] = -2; var_y[7] = 1;
}

//设置初始状态
void init_status(int x, int y)
{
	step = 1;
	chessboard[x][y] = step;
	step ++;
	cur_x = x;
	cur_y = y;
	direction[x][y] = MAX_DIR; //每个位置都没有选择方向
	last_direction = MAX_DIR; //上一次方向也没有

	init_direction();
}

//输出巡游结果
void print()
{
	int x, y;

	printf(" +");
	for (x = 0; x < WIDTH; x++)
		printf("----+");
	printf("\n");

	for (x = 0; x < WIDTH; x++) 
	{
		printf(" |");
		for (y = 0; y < WIDTH; y++) 
			printf("%3d |",chessboard[x][y]);
		printf("\n");

		printf(" +");
		for (y = 0; y < WIDTH; y++) 
			printf("----+");
		printf("\n");
	}

}

//判断走这一步是否可行
int is_legal(int x, int y)
{
	if( x < 0 || x >= WIDTH)
		return 0;
	if( y < 0 || y >= WIDTH)
		return 0;
	if( chessboard[x][y] != 0 )
		return 0;

	return 1;
}

//判断是否遍历完成
int is_end()
{
	if( step > WIDTH * WIDTH )
		return 1;
	else
		return 0;
}

//判断是否会到起点
int is_back_to_start()
{
	if (step == 1) 
		return 1;
	else 
		return 0;
}

int select_direction()
{
	int try_x,try_y;

	if(last_direction == MAX_DIR)
		last_direction = 0;
	else
		last_direction ++;

	for( ; last_direction < MAX_DIR; last_direction ++)
	{
		try_x = cur_x + var_x[last_direction];
		try_y = cur_y + var_y[last_direction];

		if(is_legal( try_x, try_y ) == 1 )
			break;
	}

	if(last_direction == MAX_DIR)
		return 0; //没有方向可选
	else
		return 1; //有方向可选
}

void forward()
{
	cur_x += var_x[last_direction];
	cur_y += var_y[last_direction];

	chessboard[cur_x][cur_y] = step;
	step ++;

	// 这个方向被记录下一位置(这时已经为(curr_x, curr_y))的direction数组中。
	direction[cur_x][cur_y] = last_direction;

	// last_direction的值已经被记录，这时置为MAX_DIR表示当前位置为新推进的位置
	last_direction = MAX_DIR;

}

void backward()
{
	step --;
	chessboard[cur_x][cur_y] = 0;

	// 将last_direction置为上一位置到(curr_x, curr_y)所选择的方向
	last_direction = direction[cur_x][cur_y];

	// 根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从
	// last_direction+1的方向开始。参看成员函数select_direction()。
	cur_x -= var_x[last_direction];
	cur_y -= var_y[last_direction];
}

int tourist()
{
	do 
	{
		if (select_direction())
			forward();
		else
			backward();
	} 
	while (!is_back_to_start() && !is_end());
	
	if (is_back_to_start())
		return 0;
	else 
		return 1;
}

void main()
{
	int start_x = 0,start_y = 0;//起始位置坐标

	printf("棋盘的大小为：%d×%d\n",WIDTH,WIDTH);
//	printf("请输入起始位置的行列数（两者之间用逗号隔开）：");
//	scanf("%d,%d",&start_x,&start_y);

	init_status( start_x, start_y );

	if(tourist())
	{
		printf("遍历结果如下：\n");
		print();
	}
	else
		printf("找不到遍历路径!\n");
}