java - 递归骑士之旅中变量的正确声明(Java作业)

Question

我在本学年的最后一个项目(我作为 CS 学生的第一年)的代码中找不到错误。我在实现骑士巡回赛问题时坚持递归。这是有问题的文件:https://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

具体来说，我的问题在于这部分代码(从第 265 行开始):

   else{
   for(int i = 0; i < numberOfPossibleNextMoves; i++){
      Cell nextCellToMoveTo = candidateNextMoves.get(i);

      int currentRowStorage = currentRow;
      int currentColumnStorage = currentColumn;
      currentRow = nextCellToMoveTo.row;
      currentColumn = nextCellToMoveTo.column;

      listOfMoves.add(nextCellToMoveTo);
      chessBoard[currentRow][currentColumn] = 1;
      currentMoveNumber++;

      boolean tourFound = findTour();

      if(tourFound){
         return true;
            }
            else{ // Undo the last move just made
               backtrackCount++;
               chessBoard[currentRow][currentColumn] = -1;
               currentRow = currentRowStorage;
               currentColumn = currentColumnStorage;                           
               listOfMoves.remove(nextCellToMoveTo);
               currentMoveNumber--;         
            }
         }
         return false;

这是 findTour() 的结尾。这是程序的一部分，用于测试从当前方格(也称为单元格)开始的所有可能移动，如果可以从新移动到的方格完成游览，则返回 true。如果不能从广场完成游览，它会进入 else{ 并撤消移动。这就是我认为的问题所在。

现在，按照上面的代码集，程序陷入了无限递归循环。

注意 else{ 语句的这一部分:

chessBoard[currentRow][currentColumn] = -1;
currentRow = currentRowStorage;
currentColumn = currentColumnStorage;

这部分代码将 chessBoard 中的正方形更改为 -1，这意味着它未被访问(1 = 已访问)。如上所述，新移动的 currentRow 和 currentColumn 用于将方 block 设置回未访问状态。然后使用 currentRowStorage 和 currentColumnStorage 将这些值重置为之前的跳跃值。

如果我把代码改成

currentRow = currentRowStorage;
currentColumn = currentColumnStorage;
chessBoard[currentRow][currentColumn] = -1;

它成功地找到了一个错误的路线，其中最后 1/3 左右的 Action 只是在几个方格之间来回跳跃。这是意料之中的，因为它没有正确处理重置过程。

我怀疑我的问题出在我声明变量的位置。这是我的第一个复杂的递归问题，我不确定我是否正确处理了 currentRow/Column 和 currentRow/ColumnStorage 之间的切换。我应该在本地或多或少地声明它们吗？

这是描述项目的页面:http://cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

这是要求的相关部分:

If the tour is not completed, then findTour determines the (possibly empty) list of vacant cells that are reachable from the knight's current cell, and stores this list in a locally declared list variable, candidateNextMoves. It is critical that this list variable be declared local to the method. If this list is empty, then there is no way to extend the current partial tour, so findTour should return false. If the list is not empty, then findTour tries extending the tour by each move on the list as follows. It iterates over the list, and for each cell of the list it makes the next move to that cell, updating all of L (the list of moves in the tour), B (the 2D array of the state of the board (visited, not visted)), currRow, and currCol to reflect this move. It then recursively calls itself, assigning the result of the call to a locally declared boolean variable, which you might name "success". If success is assigned true, findTour returns true. If success is false, findTour undoes the move it just made, or "backtracks", and tries the next move of candidateNextMoves. You will maintain a static int variable, backtrackCount, which is initialized to 0, and incremented for each undo of a move.

请注意 - 我将我的 boolean 值称为“tourFound”而不是“成功”。

Answer 1

与无限递归的情况一样，首先要检查的是您打算如何摆脱它的条件。在这种情况下，只有在

if(currentMoveNumber == numberOfMovesOnBoard){
     return true;
  }

检查您的算法和初始化是否存在阻止 currentMoveNumber 达到 numberOfMovesOnBoard 的内容。

提示:在进入递归方法之前，您的起始条件是什么？