//         骑士旅行之迷宫算法
//程序马骑士旅行路线想像成一个迷宫,利用堆栈存储一条正确路线。
//结合游戏玩家的无敌玩法,即打胜了存档,打输了调档,最终自然是只赢不输。
//本程序也一样,走对存档,走错了调档,最终自然是会找到正确路线。

#include"iostream.h"
#include"stdio.h"
#define STP 55         //骑士旅行步数,一般取50到58步之间,取64步调试时间太长

//定义点变量类形
typedef struct
{
int x;
int y;
int z;
} NONCE;

//函数原数
int startpd(NONCE [8][8],NONCE);    //起点判断
NONCE next(NONCE);     //试探下一步函数
void save(NONCE [8][8],NONCE [100],int);  //存档
void load(NONCE [8][8],NONCE [100],int);  //读档
int bjpd(NONCE);             //边界判断
int hfpd(NONCE [8][8],NONCE); //合法点判断

//程序入口
int main()
{
NONCE chess[8][8];   //定义棋盘,行列表示格子,成员x表示棋盘步数,成员z表示下一步将要试探的地方
                     //由于骑士最多只能走八个方向,故z值只能取 0 ~ 7  
int i,j,k;
NONCE start;
   for(i=0;i<8;i++)
     for(j=0;j<8;j++)
      {
 start.x=i;start.y=j;start.z=0;
 if(startpd(chess,start))goto endfor;    //起点判断,如果该点可以为起点则返回1
                                                //否则返回0
      }
endfor:
   //输出
    for(i=0;i<8;i++)
     {
       for(j=0;j<8;j++)
  {
    if(chess[i][j].x==-1)         //骑士没有走的地方显示 "@"
     cout << "@    ";
    else
     printf("%2d   ",chess[i][j].x);  //骑士走过的地方显示所走的是第几步
  }
      cout << endl << endl;
     }
return 0;
} //end main

//起点判断,如果该点可以为起点则返回1
//否则返回0
int startpd(NONCE chess[8][8],NONCE start)
{
NONCE  stack[100];  //定义堆栈
NONCE  nexttmp;
int point;
int i,j,k;

//将棋盘清空
    for(i=0;i<8;i++)
      for(j=0;j<8;j++)
       {
 chess[i][j].x=-1;
 chess[i][j].y=0;
 chess[i][j].z=0;
       }

//将堆栈清空
    for(i=0;i<100;i++)
      {
       stack[i].x=0;
       stack[i].y=0;
       stack[i].z=0;
      }

//将起点赋值给栈底
  point=0;
    stack[point].x=start.x;
    stack[point].y=start.y;
    stack[point].z=start.z;

  do{
    nexttmp=next(stack[point]);   //试探下一步
      if(hfpd(chess,nexttmp))     //判断试探的下一步是否合法
  {
    point++;               //如果合法,则存档 
    stack[point]=nexttmp;
    save(chess,stack,point);  //存档
  }
      else if(stack[point].z<7)   //如果不合法,则判断8种走法是否走完
  {                        //如果没走完,则继续试探下一种走法 
    stack[point].z++;
  }
      else
  {
    point--;               //如果8种走法都走完还是没有出路,则已表示该点
                                  //为死点,退回到上一步继续试探,即像游戏玩家那调档
    load(chess,stack,point);  //读档
    stack[point].z++;
  }

       if(stack[0].z>=8)return 0;   //如果栈底的8种走都已走完,则表示该点不能作为起点,函数返回0
       cout << "  " << point << endl;
    }while(point<=STP);             //如果已走完指定的步数,退出试探,函数返回1
return 1;
}  //end startpd

//存档函数
void save(NONCE chess[8][8],NONCE  stack[100],int point)
{
int i,j,k;

  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
  for(k=0;k<=point;k++)
    {
      chess[stack[k].x][stack[k].y].x=k;
      chess[stack[k].x][stack[k].y].y=0;
      chess[stack[k].x][stack[k].y].z=stack[k].z;
    }
}  //end save

//读档函数
void load(NONCE chess[8][8],NONCE stack[100],int point)
{
int i,j,k;
  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
  for(k=0;k<=point;k++)
    {
      chess[stack[k].x][stack[k].y].x=k;
      chess[stack[k].x][stack[k].y].y=0;
      chess[stack[k].x][stack[k].y].z=stack[k].z;
    }
}//end load

//试探下一步点函数
NONCE  next(NONCE  non)
{
NONCE  nex;
begin:
 if(non.z==0)
   {
   nex.x=non.x+2;
   nex.y=non.y-1;
   }
 else if(non.z==1)
   {
   nex.x=non.x+1;
   nex.y=non.y-2;
   }
 else if(non.z==2)
   {
   nex.x=non.x-1;
   nex.y=non.y-2;
   }
 else if(non.z==3)
   {
   nex.x=non.x-2;
   nex.y=non.y-1;
   }
 else if(non.z==4)
   {
   nex.x=non.x-2;
   nex.y=non.y+1;
   }
 else if(non.z==5)
   {
   nex.x=non.x-1;
   nex.y=non.y+2;
   }
 else if(non.z==6)
   {
   nex.x=non.x+1;
   nex.y=non.y+2;
   }
 else if(non.z==7)
   {
   nex.x=non.x+2;
   nex.y=non.y+1;
   }
 nex.z=0;
 if(bjpd(nex))
  {
    non.z++;
    goto begin;
  }
return nex;
} // end   nextpd

//边界判断函数
int bjpd(NONCE nex)
{
if(nex.x<0||nex.x>7||nex.y<0||nex.y>7)
    return 1;
else
    return 0;
}//end bjpd

//合法点判断函数
int hfpd(NONCE chess[8][8],NONCE non)
{
if(chess[non.x][non.y].x==-1)
   return 1;
else
   return 0;
} // end nextpd