骑士巡回问题

Question

在N . N 的方格点上， 有个骑士希望从某个方格点开始走“ 日” 字形遍历所有方 
格点， 而且每次不能走到已经到达过的方格点上。N的值和骑士的初始位置由用户 
输入给定， 请用一定的启发式策略在尽量短的时间完成骑士巡回问题的求解， 如 
果不存在可行解， 输出相应信息； 如果存在可行解， 请将解的方案保存到一个结 
果文件中。下图中给出了巡回过程中的一段可行巡回方案， 初始位置在1， 巡回路 
线1 → 2 → 3 → 4 → 5。 即箸名的“马踏棋盘”，他肯定知道。但他要注意必须是“启发式策略”。

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;
}