中国象棋马的遍历问题
这个问题我想是个有趣的问题，能否解答？ 问题点数：0、回复次数：11Top
1 楼ghtsao（月之暗面）回复于 2003-05-04 04:58:27 得分 0
分来Top
2 楼manonroad（唧唧嘎嘎）回复于 2003-05-04 06:03:46 得分 0
具体点？
Top
3 楼shishiXP（诗人XP）回复于 2003-05-04 08:51:54 得分 0
我只知道马走日。
其他不懂。Top
4 楼wshcdr（dd）回复于 2003-05-04 14:10:45 得分 0
GZTop
5 楼wshcdr（dd）回复于 2003-05-04 14:17:04 得分 0
MARKTop
6 楼justaseeker（MS）回复于 2003-05-04 14:23:19 得分 0
我写的你参考一下吧:
# include < iostream.h >
# include < iomanip.h >
# include < time.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 ) {
clock_t tick;
tick = clock ( );
double t = ( double ) tick / CLK_TCK;
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 , t );
// 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 , double t ) {
double tt = 0;
tt += t;
ofstream outfile ( "ltt.txt" , ios::app ); // 输出到文件
struct tm *ltt;
time_t ltt2;
time ( <t2 );
ltt = localtime ( <t2 ); // 输出日期
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 << "走了" << tt << "秒" << endl;
outfile << asctime ( ltt );
outfile << endl;
}
Top
7 楼Skt32（荒城之月）回复于 2003-07-02 16:46:42 得分 0
[ 原创文档 本文适合中级读者 已阅读651次 ]
马走日棋盘算法
作者：哈达
下载本文示例源代码
问题描述
在给定大小的方格状棋盘上, 将棋子”马”放在指定的起始位置 , 棋子”马” 的走子的规则为必须在棋盘上走”日”字; 从棋子”马”的起始位置开始, 搜索出一条可行的路径, 使得棋子”马”能走遍棋盘上的所有落子点, 而且每个落子点只能走一次;
例如: 棋盘大小为5*5 , 棋子马放的起始落子点为 ( 3 , 3 ) ; 算法需要搜索一条从位置( 3 , 3 ) 开始的一条包括从( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) … ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 3 ) , ( 5 , 4 ) , ( 5 , 5 ) 总共25个可以落子的全部位置;
问题分析
通过上面的问题描述,我们对问题的内容有了正确的理解,接下来我们开始对问题进行具体细致的分析,以求找到解决问题的正确的可行的合理的方法;
首先我们需要在程序中用合适的数据结构表示在问题中出现的棋盘 , 棋子 , 棋子的走子过程 ; 接下来我们需要对核心问题进行分析, 即如何搜索一条可行的路径 , 搜索采取何种策略 , 搜索的过程如何表示 ;
对于一个大小为n*m大小的棋盘 , 棋子从当前位置( x , y ) 出发,可以到达的下一个位置( x’ , y’ ):
(1) ( x +1 , y +2 )
(2) ( x +1 , y –2 )
(3) ( x – 1, y +2 )
(4) ( x – 1, y – 2 )
(5) ( x +2, y +1)
(6) ( x +2, y – 1)
(7) ( x -2, y + 1)
(8) ( x -2, y – 1 )
限制条件:
1. 1 <= x’ <= n , 1 <= y’ <= m; ( n : 棋盘的高度 , m: 棋盘的宽度 );
2. ( x’ , y’ ) 必须是棋子记录表中没有包括的新位置;
3. 棋子走子过程记录表中没有包括棋盘上的所有可以落子的位置;
对这个过程不停迭代的过程也就是对解空间搜索的过程, 搜索直到棋子走子记录表中包括棋盘上的所有可以落子的位置 , 就搜索到了一条可行的路径,路径包括棋盘上的所有落子点;或者搜索完整个解空间,仍然找不到一条可行的解,则搜索失败;
下面我们举例来说明搜索的过程;
棋盘大小 : 5 * 5
棋子起始位置 : ( 3 , 3 )
搜索过程 :
(1) 从当前位置( 3 , 3 )出发可以有8个新的位置选择; 首先选择新位置1 , 将新位置1
作为当前棋子位置 , 开始新的搜索;
如果搜索不成功, 则搜索回退, 选择新位置2 ,以此类推,就可以搜索完整个解空间,只要从该问题有解 , 则可以保证一定可以搜索到;
2) 从新位置1 开始新的搜索,可以选择的新位置有两个,先选择位置1 , 从位置1开始新的搜索;
(3) 下图是经过18步搜索之后的状态, 从位置18出发, 已经没有没走过的新位置可以选择, 则搜索失败;
搜索回退到17步, 从位置17开始搜索除了18之外的新位置, 从图上可以看出已经没有新位置可以选择,继续回退到16步, 搜索除了17的新位置; 以此类推.知道搜索完整个解空间 , 或者搜索到一个可行解;
(4) 下图展示了搜索成功的整个搜索过程;
系统设计
一. 用例图
二. 类设计
三. 顺序图
四. 核心算法设计
通过上面的分析, 我们现在可以将算法的大概框架写出来了 , 具体的代码请参考本文章后面的源程序;
下面我们先列出了经典回溯算法的框架; 由于考虑到程序实现的方便性 , 所以本文中采用的回溯算法对经典算法进行了适当的修改;
经典算法:
void BackTrack( int t )
{
if ( t > n ) OutPut( x );
else
for( int I = f( n , k ) ; i <= g( n , k ) ; i ++ )
{
x[ t ] = h ( i );
if ( ConsTraint( t ) && Bound( k ) )
BackTrack( k + 1 );
}
}
本文采用的算法: bool Search( Location curLoc )//开始计算;
{
m_complex++;
//修改棋盘标志;
m_chessTable[ curLoc.x-1 ][ curLoc.y-1 ] = 1;
//是否搜索成功结束标志;
if( isSuccess() )
return true;
//还有未走到的棋盘点,从当前位置开始搜索;
else
{
//递归搜索未走过的棋盘点;
for( int i = 0 ; i < 8 ; i++ )
{
Location newLocation = GetSubTreeNode( curLoc , i ) ;
if( isValide( newLocation ) &&
m_chessTable[newLocation.x-1][newLocation.y-1] == 0 )
{
if( Search( newLocation ) == true )
{
//填写记录表;
MarkInTable( newLocation, curLoc );
return true;
}
}
}
}
//搜索失败,恢复棋盘标志;
m_chessTable[curLoc.x-1][curLoc.y-1] = 0;
return false;
}
测试数据和测试结果
(1). 测试数据1 :
棋盘大小
棋子起始位置 ( 1 , 1) ( 4 , 4 ) ( 2 , 3 ) 略…
搜索到的可行解 无 无 无 无
搜索解空间大小 2223 2223 501 略…
结论: 对于4 * 4 和小于 4*4的棋盘,此问题无可行解;
(2). 测试数据2:
棋盘大小 : 5 * 5
棋子起始位置 : ( 1 , 1 )
搜索解空间大小 : 76497
搜索结果图示 :
棋子起始位置 : ( 3 , 3 )
搜索解空间大小 : 11077
搜索结果图示 :
结论: 对于5*5 的棋盘 ,此问题有可行解,搜索解空间大小随棋子的起始位置不同而不同,从某些位置起始搜索 , 此问题可能没有可行解;
(3). 测试数据3 :
棋盘大小 : 6 * 6
棋子起始位置 : ( 4 , 2 )
搜索到的可行解 : 2029720
结果图示 :
(4). 测试数据4:
棋盘大小 : 7 * 7
棋子起始位置 : ( 3 , 3 )
搜索解空间大小 : 12799463
结果图示 :
结论
通过多组数据的测试,我们发现当棋盘的高度 height <= 5 , 宽度 width <= 5 的时候, 该棋盘问题的解空间比较小,本文采用的算法可以在很短的时间内搜索完整个解空间 ;
当棋盘为5*5 大小 , 整个解空间大小为1829421 = 2 (21) ; 由于棋盘和棋子的一些特点 ( 如: 棋子从当前位置出发只能到达棋盘上的某些特殊点, 而且这些点必须不包含在走子记录表中), 这就给分析棋盘算法的时间复杂度带来了一些困难, 我们只能通过不同大小棋盘的特点来大概分析算法的时间复杂度, 通过实际的测试(在棋盘大小为5*5 ), 估算的时间复杂度与实际的复杂度基本在一个数量级;
上图是一个5*5大小的棋盘 , 方框所在的位置 ( 3 , 3 )出发可以到达的点有8个, 而下次从8个新的搜索点出发平均能到达的有2个点 , 还有25 – 1 – 8 = 16 个点 , 16个点中除去4个点就剩一般的点没有走过, 从这4个点出发, 可以到达的新的搜索点平均有2个, 当棋盘上的一半以上的点全都走过,则从剩余的12个点出发可以到达的新的搜索点平均只有1;
通过上面的分析 , 我们可以得出 Space( 5*5 ) = 8 * pow( 2, 8 ) * pow( 2 , 4 ) * 12 = pow( 2 , 20 );
同理,我们可以对棋盘大小为8*8 的解空间大小进行估算; 当然估算当中的一些特殊点的选择是需要一些技巧和实际经验的, 虽然最终结果可能不准确 , 但是能够保证基本在一个数量级上;
Space( 8 * 8 ) = pow( 4 , 8 ) * pow( 4 , 4 ) * pow( 2 , 20 ) * pow( 2 , 32 );
可以看出,解空间是相当大的, 我们假设计算机每分种搜索300万步 , 对于棋子”马”给定一个起始位置, 要想证明此问题无解 , 则需要搜索的时间为 ( 下面数字均为估计值 ) :
Time( 8 * 8 ) = Space ( 8 * 8 ) / 300万 = pow( 2 , 76 ) / 300万 = pow( 2 , 62 )分钟 =
pow( 2 , 56 )天 = pow ( 2 , 47 )年 = 128亿年
注: pow( x , y ) 代表x的y次方;
可见要搜索完一个大小为8*8 棋盘问题的全部解空间是根本不可能的;
算法的时间复杂度为pow( 2 , n ) , 是个NP难解问题;
具体算法实现请参考本文配套源代码。
Top
8 楼Skt32（荒城之月）回复于 2003-07-02 16:48:13 得分 0
http://www.vckbase.com/document/viewdoc.asp?id=735
http://www.vckbase.com/code/downcode.asp?id=2007Top
9 楼NowCan（城市浪人）回复于 2003-07-02 17:57:22 得分 0
厉害。Top
