骑士巡游问题（马步问题），用回溯法实现的

【问题描述】 骑士巡游问题:从国际象棋棋盘上任意给定的方格开始移动骑士，相继地到达所有的64个方格，进入每个方格一次且仅进入一次。

#include   
#include   
using namespace std;  
const int n = 8;    //n*n的棋盘  
int a[n+1][n+1];    //二维数组表示棋盘，不使用0行0列  
int move[9][3];     //移动偏移量（增量）。为方便起见，只使用其中1-8行、1-2列（不用0行0列）  
bool possible;      //是否摆放成功  
void go（int i int j int k bool &possible）  
{  
    /*从（ij）点出发，做第k至第n*n次的移动 
      若成功则通过引用参数q返回true*/  
    int v = 0gh;  //v（取值1-8）表示方向，（gh）表示从当前点（ij）沿v方向移动后到达点的坐标  
    do  
    {  
        v++;  
        possible = false;  
        g = i + move[v][1];  
        h = j + move[v][2];  
        if （g >= 1 && g <= n && h >= 1 && h <= n && a[g][h] == 0）   //（gh）处于棋盘内，且尚未放过棋子  
        {  
            a[g][h] = k;    //将第k步棋子放在（gh）点  
            if （k < n * n）  //尚未放满整个棋盘  
            {  
                go（ghk+1possible）;   //递归调用  
                if（!possible）  //如果找不到解，利用回溯法把数组都赋0值
                    a[g][h] = 0;  
            }  
            else    //放满整个棋盘，possible返回true  
                possible = true;  
        }  
    }  
    while（!possible && （v != 8））; //循环的条件是possible为false（因为没有找到最后解之前possible都为false），并且v不为8表示没有遍历所有方向 
}  
int main（）  
{  
    //初始化move数组  
    move[1][1] = 2;     move[1][2] = 1;   
    move[2][1] = 1;     move[2][2] = 2;  
    move[3][1] = -1;    move[3][2] = 2;  
    move[4][1] = -2;    move[4][2] = 1;  
    move[5][1] = -2;    move[5][2] = -1;  
    move[6][1] = -1;    move[6][2] = -2;  
    move[7][1] = 1;     move[7][2] = -2;  
    move[8][1] = 2;     move[8][2] = -1;  
    cout << “Please input the first position:“ << endl;  
    int x1y1;  
    cin >> x1 >> y1;    //输入初始坐标  
    a[x1][y1] = 1;      //在棋盘（x1y1）处放下棋子（第1步棋）  
    go（x1 y1 2 possible）;    //从（x1y1）出发，做第2至第25次的移动，若成功possible返回true  
    //若摆放成功，输出棋盘（移动过程）  
    if （possible）  
        for （int i = 1; i <= n; i++）  
        {  
            for （int j = 1; j <= n; j++）  
                cout << setw（4） << a[i][j];  
            cout << endl;  
        }  
    else    //摆放不成功  
        cout << “Impossible!“ << endl;  
	system（“pause“）;
    return 0;  
}  

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

     文件      38912  2010-12-09 15:51  Knight\Debug\Knight.exe

     文件     394952  2010-12-09 15:51  Knight\Debug\Knight.ilk

     文件     584704  2010-12-09 15:51  Knight\Debug\Knight.pdb

     文件       7120  2010-12-09 15:51  Knight\Knight\Debug\BuildLog.htm

     文件        663  2010-12-09 15:07  Knight\Knight\Debug\Knight.exe.embed.manifest

     文件        728  2010-12-09 15:07  Knight\Knight\Debug\Knight.exe.embed.manifest.res

     文件        621  2010-12-09 15:51  Knight\Knight\Debug\Knight.exe.intermediate.manifest

     文件      41010  2010-12-09 15:51  Knight\Knight\Debug\Knight.obj

     文件         69  2010-12-09 15:51  Knight\Knight\Debug\mt.dep

     文件     166912  2010-12-09 15:51  Knight\Knight\Debug\vc90.idb

     文件     217088  2010-12-09 15:51  Knight\Knight\Debug\vc90.pdb

     文件       2357  2010-12-09 15:51  Knight\Knight\Knight.cpp

     文件       3934  2010-12-09 15:06  Knight\Knight\Knight.vcproj

     文件       1417  2010-12-09 15:58  Knight\Knight\Knight.vcproj.CHENGXIONG.Administrator.user

     文件    1166336  2010-12-09 15:58  Knight\Knight.ncb

     文件        884  2010-12-09 15:06  Knight\Knight.sln

    ..A..H.      8192  2010-12-09 15:58  Knight\Knight.suo

     目录          0  2010-12-09 15:51  Knight\Knight\Debug

     目录          0  2010-12-09 15:09  Knight\Debug

     目录          0  2010-12-09 15:51  Knight\Knight

     目录          0  2010-12-09 15:07  Knight

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

              2635899                    21