学步园

骑士巡游或叫马步遍历

问题描述：

在n*n的棋盘上，假设一个骑士按象棋中“马”的走法，从初始坐标(x1,y1)出发，要求无重复地走遍棋盘
中的每一个位置(每个点必须经过一次且只能是一次 )。请编写程序，为骑士求解巡游“路线”(或无解)。

代码：

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