首页 > 搜索 > 回溯和剪枝 > 骑士旅游问题[回溯]
2014
04-23

骑士旅游问题[回溯]

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

骑士也就是类似中国象棋中的马的走法。这个问题和典型的N皇后问题的比较类似的,都可以通过回溯法来解决。还有其它的解决方法,参考:http://en.wikipedia.org/wiki/Knight%27s_tour#Computer_algorithms

关于回溯算法的详细介绍可以参考:回溯法(1),回溯法(2),回溯法(3).

代码实现如下:

#include<stdio.h>
#include <iostream>
using namespace std;
#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 :\n");
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
            printf(" %2d ", sol[x][y]);
        printf("\n");
    }
}

//存储解决方案
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();
    return 0;
}

输出:

find one solution :
  1  60  39  34  31  18   9  64 
 38  35  32  61  10  63  30  17 
 59   2  37  40  33  28  19   8 
 36  49  42  27  62  11  16  29 
 43  58   3  50  41  24   7  20 
 48  51  46  55  26  21  12  15 
 57  44  53   4  23  14  25   6 
 52  47  56  45  54   5  22  13

参考:http://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-problem/