马的Hamilton周游路线问题国际象棋

马的Hamilton周游路线问题，8*8 的国际象棋棋盘上的一只马，恰好走过除起点外的其它63 个位置各一次，最后回 到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m*n 的国际象棋棋盘，m和n均为大于5 的偶数，且|m-n|≤2，该算法找出一条马的Hamilton周游路线。-

#include 
#include 
/**//**/
//棋盘行数
const int N = 6;
int step[N * N] = {-1}; //保存每一步做出的选择
int chess[N][N] = {0}; //棋盘
int Jump[8][2] = {{-2 1} {-1 2} {1 2} {2 1} {2 -1} {1 -2} {-1 -2} {-2 -1}};
int p = 0;//对解的个数计数
//判断是否合法
char s[20];
int canJump（int x int y）
{
    if （x >= 0 && x < N && y >= 0 && y < N && chess[x][y] == 0）
        return 1;
    return 0;
}
//求权值
int weightStep（int x int y）
{
    int count = 0;
    for （int i = 0; i < 8; ++i）
    {
        if （canJump（x + Jump[i][0] y + Jump[i][1]））
            count++;
    }
    return count;
}
//权值排序
void inssort（int a[] int b[] int n）
{
    if （n <= 0） return;
    for （int i = 0; i < n; ++i）
    {
        for （int j = i; j > 0; --j）
        {
            if （a[j] < a[j - 1]）
            {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
                
                temp = b[j - 1];
                b[j - 1] = b[j];
                b[j] = temp;
            }
        }
    }
}


//输出结果
void OutPutChess（）
{
	FILE *fp;
	if（（fp=fopen（s“w“））==NULL）
	{
		printf（“cannot open file“）;
		exit（0）;
	}

    int ijkl=0;
    for （i = 1; i <= N * N - 1; ++i）
        {
            printf（“%d “ step[i]）;
        }
    printf（“\n“）;
    for（i=0;i    {
        for（int j=0;j            fprintf（fp“%3d “chess[i][j]）;
        fprintf（fp“\n“）;
    }

	fprintf（fp“\n坐标表示结果：\n“）;

	for（i=1;i<=N*N;i++）
	{
		for（j=0;j		{
			for（k=0;k			{
				if（chess[j][k]==i）
				{
					fprintf（fp“（%d%d）   “jk）;
				}
			}
		}
		l++;
		if（l%6==0）
			fprintf（fp“\n“）;
	}
	fclose（fp）;
}

//回溯算法
void BackTrace（int t int x int y）
{
    if （t >= N * N）
    {
        p++;
        OutPutChess（）;//输出结果
        exit（1）;   //求得一个解时退出程序
        //return ;  //求得所有解
    }
    else
    {
        int i;
        int count[8] possibleSteps[8];
        int k = 0;
        for （i = 0; i < 8; ++i）
        {
            if （canJump（x + Jump[i][0] y + Jump[i][1]））
            {
                count[k] = weightStep（x + Jump[i][0] y + Jump[i][1]）; //求权值
                possibleSteps[k++] = i;   //保存下一个结点的序号
            }
        }
        
        inssort（count possibleSteps k）;//排序
        for （i = 0; i < k; ++i）
        {
            int d = possibleSteps[i];
            //跳向下一个结点
            x += Jump[d][0];
            y += Jump[d][1];
            chess[x][y] = t + 1;
            step[t] = d;
            BackTrace（t + 1 x y）;  //递归调用
            //回溯
            chess[x][y] = 0;
            x -= Jump[d][0];
            y -= Jump[d][1];
            
        }
    }
}

int main（）
{
    
    int x = 0;
    int y = 0;
    chess[x][y] = 1;
	sprintf（s“result.txt“）;
    BackTrace（1 x y）;
	system（“pause“）;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3045  2010-05-06 22:02  Hamilton.cpp

----------- ---------  ---------- -----  ----

                 3045                    1