Hamilton周游路线问题的描述可以参见分治法解马的hamilton周游路线问题。因为在使用递归算法直接求解6x6,6x8等子问题的时候,发现当子问题的规模是8x8的时候,不论程序运行多久,都无法出来结果。查了维基百科之后发现,这个问题如果要解出来,对于一个8x8的子问题,需要遍历大约4*10^51次。holy sh1t!这已经远远超出我的预算范围了。so,只能用一些别的方法得到这些子问题的解,然而我又懒得去一个一个把数字输入到程序里面去。所以我就准备重新找一些方法来解这个问题。于是就找到了Warnsdorff规则这个神一样的东西。

起初准备用这个方法来解hamilton的问题,然而,使用后发现,使用warnsdorff找出来的路线,他并不是闭合的,so,如果你是想用warnsdorff来解决hamilton周游路线问题,你就可以出门左转了(可以参考分治法解马的hamilton周游路线问题)。但如果你只是想要实现遍历整个期盼的问题,那你还是来对地方了!!

Warnsdorff规则指在所有可走且未经过的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数最少;如果可跳的方格数相等,则从当前位置看,方格序号小的优先。依照这一规则往往可以找到一条路径但是并不一定能够成功。(来源维基百科)

第一个条件好说,比如说接下来我可以走A,B或者C三个格子,那么我会挑其中可走路线最多的格子走;问题在第二个条件,序号最小是指什么呢?在这里我使用的是按照从左到右,依次数到换行的记述方法。

代码如下:

int dir[8][2]=\{\{-1,-2\},\{1,-2\},\{-2,-1\},\{2,-1\},\{-2,1\},\{2,1\},\{-1,2\},\{1,2\}\};
int m88[8][8];
bool chkX(int x,int w)
\{
  if(x>=0 && x<w)
  \{
    return true;
  \}else
  \{
    return false;
  \}
\}
void printMat()
\{
  for(int i=0;i<8;i++)
  \{
    for(int j=0;j<8;j++)
    \{
      cout<<m88[i][j]+1<<'\t';
    \}
    cout<<endl<<endl;
  \}
\}
bool chkPt(int x,int y,int w,int h)
\{
  return chkX(x,w)&&chkX(y,h);
\}

int cntStep(int x,int y)
\{
  int cnt=0;
  for(int i=0;i<8;i++)
  \{
    int xn=x+dir[i][0];
    int yn=y+dir[i][1];
    if(chkPt(xn,yn,8,8)&&m88[xn][yn]==-1)
    \{
      cnt++;
    \}
  \}
  return cnt;
\}
void init_m88()
\{
  for(int i=0;i<8;i++)
  \{
    for(int j=0;j<8;j++)
    \{
      m88[i][j]=-1;
    \}
  \}
  int curStep=0;
  int xc=0,yc=0;
  cout<<cntStep(xc,yc)<<endl;
  while(cntStep(xc,yc)!=0)
  \{
    m88[xc][yc]=curStep;
    printMat();
    int minStep=100;
    int iMinStep=curStep;
    for(int i=0;i<8;i++)
    \{
      int xn=xc+dir[i][1];
      int yn=yc+dir[i][0];
      if(chkPt(xn,yn,8,8)&&m88[xn][yn]==-1)
      \{
        int cStep=cntStep(xn,yn);
        if(cStep<minStep)
        \{
          minStep=cStep;
          iMinStep=i;
        \}
      \}
    \}
    xc=xc+dir[iMinStep][1];
    yc=yc+dir[iMinStep][0];
    curStep++;
  \}
  m88[xc][yc]=curStep;
\}

得到的结果:

1	16	31	40	3	18	21	56	
30	39	2	17	42	55	4	19	
15	32	41	46	53	20	57	22	
38	29	48	43	58	45	54	5	
33	14	37	52	47	60	23	62	
28	49	34	59	44	63	6	9	
13	36	51	26	11	8	61	24	
50	27	12	35	64	25	10	7	

可以看到,它确实是遍历了一遍,但不是一个回路。如果要得到一个是回路的解,还是参考分治法解马的hamilton周游路线问题吧。