horse 问题

/*******************************************************************
    [问题描述]
    在一个具有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****************");
}

本文地址：http://com.8s8s.com/it/it874.htm