C++遞歸回溯騎士遊

所以，總之我正在研究一個騎士的旅程。如果你不知道那是什麼，那麼騎士會被放在棋盤上，你必須將它移動到棋盤上的每一處。我正在使用遞歸函數，但無法讓我的回溯工作。我可以在5x5板上達到22個步驟，但該程序不會備份並嘗試不同的路徑。我發佈的只是我的代碼的遞歸部分（對不起有點長）任何見解都會非常有幫助。非常感謝！C++遞歸回溯騎士遊

`bool findPath (int board[][boardSize + 4], int &currRow, int &currCol, int &currMove,int boardSize) 
{ 
    int i, j; 
    bool foundSpot; 

    board[currRow][currCol] = currMove; 

    if (currMove == boardSize * boardSize) 
     return true; 

    for (i = 0; i < boardSize + 4; i++) 
    { 
     for (j = 0; j < boardSize + 4; j++) 
      cout << setw (3) << board[i][j]; 
     cout<<endl; 
    } 
    cout << endl; 

    if (board[currRow - 2][currCol - 1] == 0) 
    { 
     currMove += 1; 
     board[currRow - 2][currCol - 1] = currMove; 
     currRow -= 2; 
     currCol -= 1; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow - 2][currCol + 1] == 0) 
    { 
     currMove += 1; 
     board[currRow - 2][currCol + 1] = currMove ; 
     currRow -= 2; 
     currCol += 1; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow - 1][currCol + 2] == 0) 
    { 
     currMove += 1; 
     board[currRow - 1][currCol + 2] = currMove ; 
     currRow -= 1; 
     currCol += 2; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow + 1][currCol + 2] == 0) 
    {  
     currMove += 1; 
     board[currRow + 1][currCol + 2] = currMove ; 
     currRow += 1; 
     currCol += 2; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow + 2][currCol + 1] == 0) 
    { 
     currMove += 1; 
     board[currRow + 2][currCol + 1] = currMove ; 
     currRow += 2; 
     currCol += 1; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow + 2][currCol - 1] == 0) 
    { 
     currMove += 1; 
     board[currRow + 2][currCol - 1] = currMove ; 
     currRow += 2; 
     currCol -= 1; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow + 1][currCol - 2] == 0) 
    {  
     currMove += 1; 
     board[currRow + 1][currCol - 2] = currMove ; 
     currRow += 1; 
     currCol -= 2; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 

    if (board[currRow - 1][currCol - 2] == 0) 
    {  
     currMove += 1; 
     board[currRow - 1][currCol - 2] = currMove ;   
     currRow -= 1; 
     currCol -= 2; 
     if (findPath(board, currRow, currCol, currMove, boardSize)) 
      return true; 
    } 
    board[currRow][currCol] = 0; 
    currMove -= 2; 
    return false; 
}`

來源

2013-04-09 user2259683

歡迎來到Stack Overflow！要求人們發現代碼中的錯誤並不是特別有效。您應該使用調試器（或者添加打印語句）來分析問題，追蹤程序的進度，並將其與預期發生的情況進行比較。只要兩者發生分歧，那麼你就發現了你的問題。（然後如果有必要，你應該構造一個[最小測試用例]（http://sscce.org）。） – 2013-04-09 00:12:35

我不認爲在每個遞歸塊中改變currRow和currCol是一個好主意 - 它意味着下一個遞歸塊將從錯誤的方塊開始，並且你的'board [currRow] [currCol] = 0;'將清除最後一個遞歸，而不是你在這個級別的步驟（設置在最上面）。你爲什麼要設置開發板並在每個'if'中更改行和列變量？該遞歸電話不應該照顧那個嗎？我不認爲你希望你的行，列，移動輸入是引用 - 而不是傳值！ – Rup 2013-04-09 00:16:32

而且你還需要範圍檢查每個'if（board [] [] == 0）'測試以確保兩個座標都在界限內。爲了避免重複自己，您可能需要構建一個移動排列的數組並循環遍歷它們。 – Rup 2013-04-09 00:21:48

我制定了以下實施的C++騎士之旅：

#include<cstdio> 
#include<iostream> 
#define MAX 10 

using namespace std; 
int tour=1; 
int board[MAX][MAX]; 

bool is_travelled(int,int); 
bool knights_tour(int,int,int,int); 
void initialize(int); 
void display(int); 

int main(int argc,char** argv){ 
    int n; 
    scanf("%d",&n); 
    for(int i=0;i<10;i++){ 
     for(int j=0;j<10;j++){ 
      board[i][j]=-1; 
     } 
    } 
    initialize(n); 
    display(n); 
    return 0; 
} 

bool is_travelled(int x,int y){ 
    if(x<0 || y<0)return true; 
    if(board[x][y]==-1)return false; 
    return true; 
} 

bool knights_tour(int i,int j,int n,int k){ // k=number of places remained , n=side of chess_board; 
    int x,y; 
    if(k==0)return true; 
    // hard-coded cases; 
    // reordering of the cases have significant effect on the execution time 
    x=i+2;y=j+1; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i+1;y=j+2; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i-1;y=j+2; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i-2;y=j+1; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i-2;y=j-1; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i-1;y=j-2; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i+1;y=j-2; 
    if((!is_travelled(x,y))&&x+y<n&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    x=i+2;y=j-1; 
    if((!is_travelled(x,y))&&x<n&&y<n){ 
     board[x][y]=tour; 
     tour+=1; 
     if(knights_tour(x,y,n,k-1))return true; 
     board[x][y]=-1; 
     tour-=1; 
    } 
    return false; 
} 
void initialize(int n){ 
    for(int i=0;i<n;i++){ 
     for(int j=0;j<n;j++){ 
      board[i][j]=0; 
      int r=knights_tour(i,j,n,n*n-1); 
      if(r==1)return; 
      board[i][j]=-1; 
     } 
    } 
} 

void display(int n){ 
    for(int i=0;i<n;i++){ 
     for(int j=0;j<n;j++){ 
      printf("%2d ",board[i][j]); 
     } 
     printf("\n"); 
    } 
    cout<<endl; 
}

希望這有助於。快樂編碼！

來源

2017-02-12 20:24:24 Tarptaeya

C++遞歸回溯騎士遊

回答

相關問題