国际象棋跳马程序（自编码研究）

本文主要是介绍国际象棋跳马程序（自编码研究），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把马随机放到8*8的一个棋盘里，按照马的行走规则，每个方格进入一次，走遍64个方格，将数字依次填入8*8个方格内，使用递归，思路很明显，但是怎么选择递归的走路问题，按照如下走，大约需要8^64  <> 6.2*10^57 计算机根本搞不定！！！！

我的算法：

int hourse_run(Node tmp)
{
        if ( hourse_run(Node(tmp.x+1,tmp.y+2)) )
            goto L;
        if ( hourse_run(Node(tmp.x+1,tmp.y-2)) )
            goto L;
        if ( hourse_run(Node(tmp.x-1,tmp.y+2)) )
            goto L;
        if ( hourse_run(Node(tmp.x-1,tmp.y-2)) )
            goto L;
        if ( hourse_run(Node(tmp.x+2,tmp.y+1)) )
            goto L;
        if ( hourse_run(Node(tmp.x-2,tmp.y+1)) )
            goto L;
        if ( hourse_run(Node(tmp.x+2,tmp.y-1)) )
            goto L;
        if ( hourse_run(Node(tmp.x-2,tmp.y-1)) )
            goto L;

网上搜的算法：

board[x][y]=step;
  int i,j; info dir[8];
  for(i=j=0;i<8;++i)
   if(x+dx[i]<0||y+dy[i]<0||x+dx[i]>=R||y+dy[i]>=C||board[x+dx[i]][y+dy[i]]) continue;
   else
   {
    dir[j].x=x+dx[i];dir[j].y=y+dy[i];
    dir[j].out=outlet(dir[j].x,dir[j].y);
    sort(dir,++j);
   }
  for(i=0;i<j;++i)
   if(search(dir[i].x,dir[i].y,step+1)) return true;
  board[x][y]=0;
  return false;

算法的精妙在于，让马优先按照边走，即优先让棋子的下一条的路最少的路走！！！！证明过程没有看懂：http://faculty.olin.edu/~sadams/DM/ktpaper.pdf；有看懂证明过程的可以给我留言

这篇关于国际象棋跳马程序（自编码研究）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---