骑士周游列国（跳马问题）C++代码实现

C++ 骑士周游列国(跳马问题) 内附报告详解设计过程

//by ngl
#include   
#include   
#include   
        
int bushu[8][8];	// bushu[i][j]表示骑士到达棋盘上位置（ij）的行走步数
int x  y ;			//记录骑士所在位置的x、y坐标
int count=0;		//记录骑士周游列国的方法数
int movexy[8][2]={{-21}  {-12}  {12}  {21} {2-1}  {1-2}  {-1-2}  {-2-1}};   //骑士在当前位置可以选择行走的8个位置

void output（）   //搜索到叶结点时，找到一种骑士周游列国的方法，输出骑士行走路径的8*8矩阵
{   
	cout<<“方法“<    for（int i = 0 ; i < 8 ; i++）					//输出骑士行走路径的8*8矩阵
    {  
		for（int j = 0 ; j < 8 ; j++）   
			printf（“%4d“  bushu[i][j]）;  
        cout<    }           
    system（“pause“）;    //由于骑士周游列国有很多种行走方法，每输出一种方法等待键盘输入再输出另一种方法，
						//这里不调用system（“pause“）结果输出很快，会看不清楚  
}   

void knight（int k）      //递归回溯法解骑士周游列国问题
{                           
	if（k == 64）		    //搜索到叶结点时，找到一种骑士周游列国的方法
	{  
		count++;		//方法数自增1
		output（）;		//输出骑士行走路径的8*8矩阵
        return;             
    }   

	//搜索子树
    for（int i = 0 ; i < 8 ; i++）    //生成当前扩展结点的8个儿子结点
    {         
		int r = x + movexy[i][0];   //骑士选择第i个位置行走
        int c = y + movexy[i][1];   
        if（r >= 0 && r < 8 && c >= 0 && c < 8 && bushu[r][c] == 0）   //当前位置可行
        {   
            x = r ; 
			y = c;   
            bushu[r][c] = k + 1;	//解空间树树中第k层结点的步数为k+1
            knight（k+1）;			//搜索子树 
            bushu[r][c] = 0;        //往上回溯时，恢复相关值
            x = r - movexy[i][0];   
            y = c - movexy[i][1];   
        }                                 
	}     
}   
        
int main（）   
{       
	for（int i = 0 ; i < 8; i++）   
		for（int j = 0 ; j < 8 ; j++）   
			bushu[i][j] = 0;   
    bushu[0][0]=1;   //以（00）为起点的周游路线。    
	
    cout<<“其实初始位置为（00）“<		<<“数字代表的是第几步:\n“<    knight（1）;		//由于骑士的初始位置已经确定了，所以回溯算法调用knight（1）

	system（“PAUSE“）;

	return 0;
}

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

     文件       2144  2010-12-15 19:17  骑士周游列国\program\骑士周游列国.cpp

     文件       3475  2010-12-15 19:19  骑士周游列国\program\骑士周游列国.dsp

     文件      33792  2010-12-15 19:19  骑士周游列国\program\骑士周游列国.ncb

     文件       1219  2010-12-15 19:19  骑士周游列国\program\骑士周游列国.plg

     文件      48640  2010-12-15 19:19  骑士周游列国\program\骑士周游列国.opt

     文件        549  2010-12-15 19:19  骑士周游列国\program\骑士周游列国.dsw

     文件    1972736  2010-12-15 19:20  骑士周游列国\骑士周游列国.doc

     目录          0  2010-12-15 19:16  骑士周游列国\program

     目录          0  2010-12-15 19:16  骑士周游列国

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

              2062555                    9