马走日棋盘算法

核心提示：四. 核心算法设计通过上面的分析, 我们现在可以将算法的大概框架写出来了 , 具体的代码请参考本文章后面的源程序;下面我们先列出了经典回溯算法的框架; 由于考虑到程序实现的方便性 , 所以本文中采用的回溯算法对经典算法进行了适当的修改;经典算法:void BackTrack(intt ){if ( t> n )O

四. 核心算法设计

通过上面的分析, 我们现在可以将算法的大概框架写出来了 , 具体的代码请参考本文章后面的源程序;

下面我们先列出了经典回溯算法的框架; 由于考虑到程序实现的方便性 , 所以本文中采用的回溯算法对经典算法进行了适当的修改;

经典算法:

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