C++使用递归进行骑士之旅

我创建了一个专门为此目的处理2D矢量的类板。我正在努力解决骑士之旅。我想在完成时打印出来。使用递归voyagingKnight（）函数，我发现它不做任何事情，不打印结果。看来，我想增加递归调用的步数，但这是行不通的。C++使用递归进行骑士之旅

矢量自变量incs是用于移动骑士的增量矢量的第2个矢量，每行中第一列移动一行，第二列移动列移动。

有没有人有任何建议，我在这里的推理缺陷？相关的代码

bool voyaging_knight(Board &board, int i, int j, int steps ,vector< vector<int> > &increments) 
    { 
     if(!newplace(theboard, i, j)) return false; 
     board.setval(i,j,step); 

     if(gone_everywhere(board, steps)) 
     { 
     cout <<"DONE" << endl; 
     board.showgrid(); 
     return true; 
     } 

     int n; 
     int in, jn; 
     for(n=0; n<8; n++) 
     { 
      in = i + increments[n][0]; 
      jn = j + increments[n][1]; 

      if(inboard(board, i, j)&& newplace(board,i,j)) 
      { 

      voyaging_knight(board, in, jn, steps+1 ,increments); 

      return true; 
      } 
     } 


     theboard.setval(i,j,-1); 

    }

来源

2014-03-05 user37460

这将是一个正常的棋盘上64个电话非常深的递归。你确定你不想只使用循环？ – lapk

是的，改变这种：

voyagingKnight(theboard, inext, jnext, step+1 ,incs); 
return true;

要这样：

return voyagingKnight(theboard, inext, jnext, step+1 ,incs);

此外，看来你需要在返回的东西（可能false）函数结束。

顺便说一下，我假设你已经将theboard中的所有条目初始化为-1。

来源

2014-03-05 09:01:43

我猜你想要一个连续的路径由一个（回合）棋盘上的马运动所发现的回溯。在这种情况下，你必须通过价值传递董事会，所以你采取的每条路径都有自己的实例来填充。通过参考传递，每条路径都会填充同一块电路板，因此您无法采取所有步骤。

此外，您应该通过值传递一个结果并填充它所访问的位置并从递归函数返回它，因此每个路径都有它自己的结果位置实例，并通过返回它，最终得到最终结果。

您不应该通过inc，因为这只是一个不会更改的辅助容器。

来源

2014-03-05 09:13:55 stefaanv

我更新了我的答案，因为我误解了传递的公式作为结果。在达到最后位置时显示结果（完成完成的棋盘），但对于回溯，理想情况下，将返回递归函数的结果。 – stefaanv

使板子成为一个全局变量，并在全局变量中建立一系列访问过的正方形。确保在撤消每个暂定步骤时撤销任何更改（方形访问，序列的最后一步）。打电话给骑士的导游功能，如果到达最后就返回成功，并在完成后做任何输出。

将整个shebang包装在一个文件或一个类中，以便不泄露私人细节以窥探。

来源

2014-03-08 16:35:36 vonbrand

C++使用递归进行骑士之旅

回答

相关问题