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++递归回溯骑士游

回答

相关问题