/*******************************************************************
[问题描述]
在一个具有8*8个方格的国际象棋盘上，从棋盘的任何一个方格开始，让马
按照允许的走步规则(L形走法)走遍所有方格，每个方格至少并且只准走过一次
。试设计一个算法实现这个有趣的问题。
[基本要求]
将马随机放在棋盘的某个方格中，根据J.C.Warnsdorff提出的规则来进行遍
历。编制非递归程序，求出马的行走路线，输出所走各步的位置。
[测试数据]
由用户自选指定一个马的起始位置(i,j), 0<=i,j<=7
[实现提示]
(1)棋盘用8*8的二维数组表示.
(2)当马位于位置(i,j)时，可以走到下列8个位置之一：
(i-2,j+1), (i-1,j+2), (i+1,j+2), (i+2,j+1),(i+2,j-1),
(i+1,j-2), (i-1,j-2), (i-2,j-1)
但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为
不允许的位置。8个可能位置的位移量可以用两个一维数组imove[8]和jmove[8]
来存储。
(3)根据J.C.Warnsdorff提出的规则来设计算法。该规则是在所有可走步的
（尚示走过的）方格中，马只能走向这样一个方格：从该方格出发，马可走步
的方格数为最少，如果可走步的方格数相等，则从马的当前位置来看，方向序
号小的优先。
(4)采用J.C.Warnsdorff规则在大多数情况下能够实现遍历，但并不能确保
成功。
********************************************************************/
#include <stdio.h>
int QIPAN[8][8]={0};
int imove[8]={-2, -1, 1, 2, 2, 1, -1, -2};
int jmove[8]={1, 2, 2, 1, -1, -2, -2, -1};
int nowi, nowj;
int m,n;
int k,l;
int choices, leastchoices;
void start() {
printf("Input start position ( 0<=nowi, nowj<=7 ) ...");
printf("\nnowi : ");
scanf("%d",&nowi);
printf("nowj : ");
scanf("%d",&nowj);
if( nowi<0 || nowi >7 || nowj<0 || nowj>7) {
printf("\nWrong position!\n");
start();
}
QIPAN[nowi][nowj]=1;
printf("(%d,%d,%d)--",nowi,nowj,nowi*8+nowj+1);
}
void next() {
leastchoices=8;
for (k=0; k<=7; k++) {
choices=-1;
if( nowi+imove[k] >=0 && nowi+imove[k] <=7 && nowj+jmove[k] >=0 && nowj+jmove[k]<=7
&& QIPAN[nowi+imove[k]][nowj+jmove[k]]==0) {
choices=0;
for (l=0; l<=7; l++) {
if ( nowi+imove[k]+imove[l] >=0 && nowi+imove[k]+imove[l]<=7
&& nowj+jmove[k]+jmove[l]>=0 && nowj+jmove[k]+jmove[l]<=7
&& QIPAN[nowi+imove[k]+imove[l]][nowj+jmove[k]+jmove[l]]==0) {
choices++;
}
}
// printf("\n%d-%d",choices,leastchoices);
if(choices<leastchoices) {
leastchoices=choices;
m=nowi+imove[k];
n=nowj+jmove[k];
}
}
}
if(m==nowi && n==nowj) {
printf("end");
return;
}
else {
nowi=m;
nowj=n;
QIPAN[nowi][nowj]=1;
printf("(%d,%d,%d)--",nowi,nowj,nowi*8+nowj+1);
next();
}
}
void main() {
int a,b;
start();
next();
for (a=0; a<=7; a++)
for (b=0; b<=7; b++){
if (QIPAN[a][b]==0) {
printf("\n***********FAILED**************");
return;
}
}
printf("\n*************OK****************");
}
