骑士旅游问题(回溯算法)

--write by zhuwx 2019-06-24 20:58:05 +0800 CST

点击量:26

问题描述:在一个N*N 格子的棋盘上,有一只国际象棋的骑士在棋盘的左下角,骑士只能根据象棋的规则进行移动,要么横向跳动一格纵向跳动两格,要么纵向跳动一格横向跳动两格。骑士从第一个格子出发,每个格子只能访问一次,能否访问完所有的格子, 请找到一个解决方案。

#include <iostream>
using namespace std;
 
/************************************************************************/
/*
	问题描述:在一个N*N 格子的棋盘上,有一只国际象棋的骑士在棋盘的左下角,骑士只能根据象棋的规则进行移动,
	要么横向跳动一格纵向跳动两格,要么纵向跳动一格横向跳动两格。骑士从第一个格子出发,每个格子只能访问
	一次,能否访问完所有的格子, 请找到一个解决方案。
*/
/************************************************************************/
#define N 8
 
bool backtracking(int x, int y, int cnt);
 
int isSafe(int x, int y, int solution[N][N])
{
	if (x >= 0 && x < N && y >= 0 && y < N && solution[x][y] == -1)
		return 1;
	return 0;
}
 
/* 打印数组sol */
void printSolution(int sol[N][N])
{
	printf('find one solution :
');
	for (int x = 0; x < N; x++)
	{
		for (int y = 0; y < N; y++)
			printf(' %2d ', sol[x][y]);
		printf('
');
	}
}
 
//存储解决方案
int solution[N][N];
 
//马跳八方,共有8中走法
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
bool KnightTour()
{
	/* 初始化 */
	for (int x = 0; x < N; x++)
		for (int y = 0; y < N; y++)
			solution[x][y] = -1;
 
	if (backtracking(0, 0, 1) == false)
	{
		printf('Solution does not exist');
		return false;
	}
	else
		printSolution(solution);
 
	return true;
}
 
bool backtracking(int x, int y, int cnt){
	//存储访问记录
	solution[x][y] = cnt;
 
	//访问完所有的格子
	if (cnt == N*N){
		return true;
	}
	int next_x, next_y;
	//一次尝试所有可以移动的格子
	for (int i = 0; i < 8; i++){
		next_x = x + xMove[i];
		next_y = y + yMove[i];
 
		//判断该格子是否可以访问
		if (isSafe(next_x, next_y, solution)){
 
			//找到解决方案 就直接返回
			if (backtracking(next_x, next_y, cnt + 1) == true) return true;
		}
	}
	solution[x][y] = -1; //回溯操作. 未找到解决方案
	return false;
}
 
int main()
{
	KnightTour();
	system('pause');
	return 0;
}