马的遍历

Question

请帮帮忙,看看这个程序,怎样使马(国际象棋中的)遍历每一个格子(8*8),然后又回到起点.谢谢!
#include <stdio.h>
#include <time.h>
#include<iostream.h>#define MAX_SIZE 10
#define MAX_STEP MAX_SIZE * MAX_SIZE
typedef struct
{
long x;
long y;
} STEP;
static long TryX[]={ -2, -1, 1, 2, 2, 1, -1, -2 };
static long TryY[]={ 1, 2, 2, 1, -1, -2, -2, -1 };
static char Board[MAX_SIZE + 4][MAX_SIZE + 4]; //棋盘，比实际棋盘大4，因为有2格是边界。//边界为值为-1，空白值为0，有棋子为1。
static char ResultBoard[MAX_SIZE][MAX_SIZE]; //用于输出结果的棋盘。
static STEP Step[MAX_STEP]; //存储每一步的坐标。
static long CurStep; //当前步，第一步是0。
static long Results; //解的个数。
static long Hamilton; //能够回到起点的解的个数。
static long SIZES, STEPS; //实际的棋盘大小和步数。
void Init(void) //棋盘初始化。
{
for(long i=0; i < SIZES + 4; i++)
{
for(long j=0; j < SIZES + 4; j++)
{
Board[i][j]=0;
}
}for(long i1=0; i1 < SIZES + 4; i1++)
{
Board[i1][0]= -1;
Board[i1][SIZES + 3]= -1;
Board[0][i1]= -1;
Board[SIZES + 3][i1]= -1;
Board[i1][1]= -1;
Board[i1][SIZES + 2]= -1;
Board[1][i1]= -1;
Board[SIZES + 2][i1]= -1;
}Results=0;
Hamilton=0;
}
void Disp(void) //打印棋盘状态
{
cout<<"         *******************                 "<<endl;
for(long i=0; i < SIZES + 4; i++)for(long j=0; j < SIZES + 4; j++) cout<< Board[i][j]<<"    ";
cout<<endl;}
void Result(void) //输出结果
{
long dx, dy;
dx=Step[CurStep].x - Step[0].x; //判断最后是否回到起点。
dy=Step[CurStep].y - Step[0].y;
Results++;cout<<"---------- Results ----------"<<Results;
cout<<endl;
if(dx * dx + dy * dy == 5)
{
Hamilton++;cout<<"---------- Hamilton  ----------"<<Hamilton;
cout<<endl;
}
for(long i1=0; i1 < STEPS; i1++)      ResultBoard[Step[i1].x - 2][Step[i1].y - 2]=i1 + 1;
for(long i=0; i < SIZES; i++)for(long j=0; j < SIZES; j++)  cout<<ResultBoard[i][j]<<"   ";
cout<<endl;
}
void PutIt(void)
{
long NextX, NextY;
for(long i=0; i < 8; i++) //8个方向上尝试，
{
NextX=Step[CurStep].x + TryX[i];
NextY=Step[CurStep].y + TryY[i];
if(Board[NextX][NextY] == 0) //如果这个位置是空，
{
Board[NextX][NextY]=1; //放置一个马，
++CurStep;
Step[CurStep].x=NextX;
Step[CurStep].y=NextY; //计入步数，
if(CurStep == STEPS - 1) //如果步数达到最大步数（棋盘全满），
{
Result(); //输出结果。
}PutIt(); //再做下一次尝试。
}
}Board[Step[CurStep].x][Step[CurStep].y]=0; //如果8个方向都不为空，将这次的马拿走，
--CurStep; //并且步数倒退1步。
}/* */
int main(void)
{
long SX, SY;
cout<<"Board size ?"<<endl;
cin>>SIZES;
STEPS=SIZES * SIZES;cout<<"Start at X?"<<endl;
cin>>SX;
cout<<"Start atY ?"<<endl;
cin>> SY;Init();
Disp();
/*CurStep=0;
Step[CurStep].x=SX + 1; //第一步由输入产生。
Step[CurStep].y=SY + 1;
Board[Step[CurStep].x][Step[CurStep].y]=1; //棋盘相应位置放置一个马
PutIt(); //开始遍历。Disp();
return 0;*/

Answer 1

我这里也有一个，但是不能实现你说的回到起点
不过其实你可以遍历，算出可以回到起点的几个特殊位置（也许存在）# include < iostream.h >
# include < iomanip.h >
# include < stdlib.h >
# include < fstream.h >bool mai ( int , int  );void main( )
{
int a = 0;
while ( a != 8 ) {
int b = 0;

while ( b != 8 )
if ( mai ( a , b ) )
b++;
a++;
}
cout << "从第1格到第64格全部走完了！！！" << endl;
}/////////////////////////////////////////////////////////////////bool mai( int row , int column )
{

int Zao ( int [ ] );
void print ( int [ ] [ 8 ] , int , int , int , int , double );

// srand ( time ( NULL ) );

// int row = rand ( ) % 7;
// int column = rand ( ) % 7;

int x = 1;
static xx = 0;

int board [ 8 ] [ 8 ] = { 0 } ;  // 棋盘

int CurrentRow = row;   // 骑士初始位置，行
int CurrentColumn = column;   //  骑士初始位置，列
board [ CurrentRow ] [ CurrentColumn ] = 1;   // 走过的标记

int horizontal [ 8 ];   // 列
int vertical [ 8 ];   // 行

horizontal [ 0 ] = 2; // 8种移动方式之列
horizontal [ 1 ] = 1;
horizontal [ 2 ] = -1;
horizontal [ 3 ] = -2;
horizontal [ 4 ] = -2;
horizontal [ 5 ] = -1;
horizontal [ 6 ] = 1;
horizontal [ 7 ] = 2;

vertical [ 0 ] = -1;   // 8种移动方式之行
vertical [ 1 ] = -2;
vertical [ 2 ] = -2;
vertical [ 3 ] = -1;
vertical [ 4 ] = 1;
vertical [ 5 ] = 2;
vertical [ 6 ] = 2;
vertical [ 7 ] = 1;

int accessibility [ 8 ] [ 8 ] = { { 2,3,4,4,4,4,3,2 },
{ 3,4,6,6,6,6,4,3 } , 
{ 4,6,8,8,8,8,6,4 } , 
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } , 
{ 4,6,8,8,8,8,6,4 } ,
{ 3,4,6,6,6,6,4,3 } , 
{ 2,3,4,4,4,4,3,2 } };   // 棋盘相应点的难易值
int a = 1;

while ( x ) {

int nan [ 8 ] = { -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 };   // 保存难易值

for ( int moveNumber = 0; moveNumber < 8; moveNumber++ )

if ( CurrentRow + vertical [ moveNumber ] >= 0 &&   // 检查行，列，是否走过
CurrentRow + vertical [ moveNumber ] < 8 && 

CurrentColumn + horizontal [ moveNumber ] >= 0 &&
CurrentColumn + horizontal [ moveNumber ] < 8 &&

board [ CurrentRow + vertical [ moveNumber ] ]
[ CurrentColumn + horizontal [ moveNumber ] ] == 0 )

nan [ moveNumber ] = accessibility [ CurrentRow + vertical [ moveNumber ] ]
[ CurrentColumn + horizontal [ moveNumber ] ];// 难易值



int moveNumber1;   // 最难走的移动方式
moveNumber1 = Zao ( nan );
// print ( board , a , row , column );
if ( moveNumber1 == 9 ) {
if ( a == 64 ) {
// cout << "走完了全部的格子!!!" << endl;
x = 0;
print ( board , a , row , column , xx);
// cin.get ( );
xx++;
return true;
}
else {
// cout << "走不动了!一共走了" << a << "步" << endl;
x = 0;
xx++;
return false;
}
}
else 
{
a++;
CurrentRow += vertical [ moveNumber1 ];   // 相应移动方式移动后行的变化
CurrentColumn += horizontal [ moveNumber1 ];   // 相应移动方式移动后列的变化
board [ CurrentRow ] [ CurrentColumn ] = a;   // 走过的标记
}
}
}/////////////////////找出最难走的//////////////////////int Zao( int nan [ ] )
{
int temp = 9;
for ( int i = 0; i < 8; i++ )
if ( temp > nan [ i ] && nan [ i ] != -1 )
temp = nan [ i ];

if ( temp != 9 ) {
int temp2 [ 8 ] = { 0 };   // 纪录满足条件的元素的下标
int t = 0;   // 满足条件下标++
for ( int j = 0; j < 8; j++ )
if ( temp == nan [ j ] ) {
temp2 [ t ] = j + 1;
t++;
}   // temp2中按顺序保存了nan中满足条件的元素的下标

int temp3 = 0;   // 纪录满足条件的元素个数

for ( int jj = 0; jj < 8; jj++ )
if ( temp2 [ jj ] != 0 )
temp3++;

int temp4 = rand ( ) % temp3;    // 随机选取满座条件的下标

temp = temp2 [ temp4 ] - 1;
}
return temp;
}////////////////////输出走过的格子//////////////void print( int b [ ] [ 8 ] , int a , int r , int c , int xx)
{ ofstream outfile ("ltt.txt",ios::app);   // 输出到文件
outfile << "初始位置是: 行 " << r + 1 << " 列 " << c + 1 << " 一共走了" << xx << "回" << endl;

for ( int x = 0; x < 8; x++ )
outfile << "     " << x + 1 << "列";
outfile << endl;

for ( int i = 0; i < 8; i++ ) {
outfile << i + 1 << "行";

for ( int j = 0; j < 8; j++ ) {
outfile << setw ( 4 ) << b [ i ] [ j ] << "    ";
}
outfile << endl;
}
outfile << endl;
}