knight.cpp

解国际象棋骑士巡游问题的C++源代码

#include <iostream.h>
#include <iomanip.h>
#include <conio.h>

#define ROW 8         //行数，可变
#define LINE 8        //列数，可变
#define NUM ROW*LINE   //总格数

int board[ROW][LINE];

//两个数组存储对应的偏移量
int stepRow[8]  = {-1,-2,-2,-1,1,2,2,1};
int stepLine[8] = {-2,-1,1,2,2,1,-1,-2};

//求 (i,j) 的出口数，各个出口对应的号存在 a[] 中。
//s 表示顺序选择法的开始
int exitn(int i ,int j ,int s ,int a[]){
 int i1,j1,k,count;
 for( count = k = 0 ; k < 8 ; k++ ){
  i1 = i + stepRow[( s + k )% 8];
  j1 = j + stepLine[( s + k )% 8];
  if( i1 >= 0 && i1 < ROW && j1 >= 0 && j1 < LINE
   && board[i1][j1] == 0 ){
   a[count++] = ( s + k )% 8;
  }
 }
 return count;
}

//判断选择下个出口，s 是顺序选择法的开始序号
int next(int i ,int j ,int s){
 int m, kk,a[8] ,b[8] ,temp;
 m = exitn( i ,j ,s ,a);
 if( m == 0 )  return -1;   //没有出口的情况
 for(int  min = 9 , k = 0 ; k < m ; k++ ){  //逐个考虑取下一步最少的出口的出口
  temp = exitn( i+stepRow[a[k]] , j+stepLine[a[k]] , s , b);
  if( temp < min ){
   min = temp ;
   kk = a[k];
  }
 }
 return kk;
}

int main()
{
 int i ,j , step ,no ,start ;
 char choose;
 int sx,sy;//起始位置
 cout<<"默认起始位为第21格（第3行，第5列），是否采用默认起始位？";
 cin>>choose;
 if(choose=='y'&&'Y')
 {sx=3;
 sy=5;
 }
 else
 {cout<<"请输入起始位置:"<<endl;
 cout<<"x=";
 cin>>sx;
 cout<<"y=";
 cin>>sy;
 cout<<"巡游路径为:"<<endl;}
   start = 0;
   sx--;
   sy--;
   do{
    for( i = 0 ; i < ROW ; i++ )
     for( j = 0 ; j < LINE ; j++ )
      board[i][j] = 0;
    board[sx][sy] = 1;
    i = sx; j = sy;
    for(step = 2 ; step <= NUM ; step++ ){
     if((no = next(i,j,start)) == -1)
      break;
     i += stepRow[no];
     j += stepLine[no];
     board[i][j] = step;
    }
    if( step > NUM || no == -1)
     break;
    start++;
   }while( step <= NUM );
   if( no != -1 ){
    //cout<<"任意键打印下个结果："<<endl;
    //getch();
   for( i = 0 ; i < ROW ; i++ ){
    for( j = 0 ; j < LINE ; j++ )
     cout<<setw(4)<<board[i][j]; //打印
    cout<<endl;
   }
   }
  
  return 0;
}