Correct declaration of variables in recursive knights tour (Java homework)

Question

I am having trouble finding the bug in my code for my last project of the school year (my first year as a CS student). I'm stuck on the recursion in my implementation of the knights tour problem. Here is the file in question: https://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

Specifically, my issue is with this section of code(starting at line 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;

which is the end of findTour(). This is the part of the program that tests out all of the possible moves from the current square (aka cells), returning true if the tour can be completed from the newly moved to square. If the tour can't be completed from the square, it goes into the else{ and undoes the move. This is where the problem is I think.

Right now, with the code set as it is above, the program gets trapped in an infinite recursive loop.

Take note of this part of the else{ statement:

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

This part of the code changes the square in chessBoard to -1, which means it is unvisited (1 = visited). As it is above, the new move's currentRow and currentColumn is used to set the square back to unvisited. Those values are then reset to the previous jumps values using currentRowStorage and currentColumnStorage.

If I change the code to

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

it successfully finds an incorrect tour in which the last 1/3 or so of the moves are simply jumping back and forth between a few squares. This would be expected given that it doesn't correctly handle the reset procedure.

I suspect my problem is due to where I am declaring my variables. This is my first complex recursive problem and I'm not sure if I am handling the switching between currentRow/Column and currentRow/ColumnStorage correctly. Should I be declaring them more or less locally?

Here is the page describing the project: http://cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

Here is the relevant section of the requirements:

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.

One note- I called my boolean 'tourFound' instead of 'success'.

Answer 1

As is often the case with infinite recursion, the first place to check is your condition for how you plan to get out of it. In this case, you can only escape if

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

Check your algorithm and initialization for something that would prevent currentMoveNumber from reaching numberOfMovesOnBoard.

Hint: What are your starting conditions before you enter your recursive method?