我的騎士的遊覽算法可能在無限循環上運行

Question

下面是我寫的代碼。

#include "genlib.h" 
#include <iostream> 
#include <math.h> 
#include "vector.h" 

struct square 
{ 
    int x; 
    int y; 

}; 


bool knighttour(square start,int &counter,int cb[][8]); 
Vector <square> generatemoves (square start); 
void Marksquare(int &cb,int ctr); 
void Unmarksquare(int &cb); 
bool IsLegal(square a,int cb[][8]); 




int main() 
{ 
    int chessboard[8][8]; 

    for (int i=0;i<8;i++) 
     for (int j=0;j<8;j++) 
      chessboard[i][j]=-1; 

    int counter=1; 

    for (int i=0;i<8;i++){ 
     for (int j=0;j<8;j++){ 
      square temp; 
      temp.x=i; 
      temp.y=j; 
      if (knighttour(temp,counter,chessboard)) 
      { 
       for (int k=0;k<8;k++){ 
        cout<<chessboard[k][0]<<chessboard[k][1]<<chessboard[k][2]<<chessboard[k][3]<<chessboard[k][4]<<chessboard[k][5]; 
        cout<<chessboard[k][6]<<chessboard[k][7]<<endl;} 


      } 

     } 
    } 


    return 0; 
} 


bool knighttour(square pt,int &counter,int cb[][8]) 
{ 

    Marksquare(cb[pt.x][pt.y],counter); 
    if (counter==64) 
     return true; 

    counter++; 

    Vector <square> temp = generatemoves(pt); 

    for (int i=0;i<temp.size();i++) 
    { 
     if (IsLegal(temp[i],cb)) 
      knighttour(temp[i],counter,cb); 
    } 

    Unmarksquare(cb[pt.x][pt.y]); 
    counter--; 
    return false; 

} 



Vector <square> generatemoves (square start) 
{ 
    Vector <square> temp; 
    Vector <square> temp2; 

     square mv1; 
     mv1.x=start.x+2; 
     mv1.y=start.y+1; 
     temp.add(mv1); 

     square mv2; 
     mv2.x=mv1.x; 
     mv2.y=start.y-1; 
     temp.add(mv2); 


     square mv3; 
     mv3.y=start.y+2; 
     mv3.x=start.x+1; 
     temp.add(mv3); 

     square mv4; 
     mv4.y=start.y+2; 
     mv4.x=start.x-1; 
     temp.add(mv4); 

     square mv5; 
     mv5.x=start.x-2; 
     mv5.y=start.y+1; 
     temp.add(mv5); 

     square mv6; 
     mv6.x=start.x-2; 
     mv6.y=start.y-1; 
     temp.add(mv6); 

     square mv7; 
     mv7.y=start.y-2; 
     mv7.x=start.x-1; 
     temp.add(mv7); 

     square mv8; 
     mv8.y=start.y-2; 
     mv8.x=start.x+1; 
     temp.add(mv8); 


     for (int i=0;i<temp.size();i++) 
      if (temp[i].x>=0 && temp[i].x<=7 && temp[i].y>=0 && temp[i].y<=7) 
       temp2.add(temp[i]); 




     return temp2; 
} 



void Marksquare(int &a,int ctr) 
{ 
    a=ctr; 

} 



void Unmarksquare(int &a) 
{ 
    a=-1; 
} 


bool IsLegal(square a,int cb[][8]) 
{ 
    if (cb[a.x][a.y]==-1) 
     return true; 
    else 
     return false; 
} 

有點解釋。我使用int [8] [8]來表示棋盤，最初我在棋盤的每個方格中放入了-1。

隨着騎士的移動，它會標記他與櫃檯（int counter）訪問的方塊，並從那裏（以及騎士可以採取的所有合法移動）進行遞歸調用以找到路徑（目標是訪問每個方格恰好一次）。

一旦計數器達到64，函數bool knighttour(square start,int &counter,int cb[][8]) 必須返回true，然後主程序將在[8] [8]棋盤上顯示「騎士之旅」。

我相信我提供的上述代碼在無限循環上運行。我讓它運行3分鐘。

Answer 1

Theory says：

...要注意，重要的是一個詳盡的強力方法（其中一個通過所有可能的舉動序列迭代）不能被應用到騎士旅行問題（除了非常小板尺寸）。對於一個普通的8x8棋盤，大約有4×1051個可能的移動序列，[9]並且需要花費大量的時間來迭代這麼多的移動。

所以爲了確保您的程序正常工作，請嘗試使用較小的紙板尺寸（比如4x4）。

爲了確保您的程序在合理的時間內適用於8x8，您必須更改算法。除了那些列出的here還有很多。

- 編輯 -

還要保證你的程序是做什麼的，它總是要添加一些痕跡，而你還在發展，是一個好主意。

E.g.

bool knighttour(square pt,int &counter,int cb[][8]) { 

printf("\r%d ", counter); // <<<--- 
Marksquare(cb[pt.x][pt.y],counter); 
if (counter==64) 
    return true; 

counter++; 

Vector <square> temp = generatemoves(pt); 

for (int i=0;i<temp.size();i++) 
{ 
    if (IsLegal(temp[i],cb)) 
     knighttour(temp[i],counter,cb); 
} 

Unmarksquare(cb[pt.x][pt.y]); 
counter--; 
return false; 

} 

Answer 2

一兩件事，我看到的是，雖然你return true時counter==64在knighttour，不得到傳播，函數調用它會返回false ..所以你永遠不會在主注意到它（）。

也就是說，即使您修復了算法，也可能無法在您的一生中完成。

Answer 3

此代碼可能會嘗試在騎士團遊中查找所有可能的路線，並將返回最後找到的路線。

而不是

for (int i=0;i<temp.size();i++) 
{ 
    if (IsLegal(temp[i],cb)) 
     knighttour(temp[i],counter,cb); 
} 

嘗試

for (int i=0;i<temp.size();i++) 
{ 
    if (IsLegal(temp[i],cb)) 
    { 
     if(knighttour(temp[i],counter,cb)) 
     { 
      return true; 
     } 
    } 

}