5

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'.

false
  • 10,264
  • 13
  • 101
  • 209
Shea Gunther
  • 51
  • 3
  • 2
    Please write to the point and precise and short. – Bhavik Ambani May 11 '12 at 19:24
  • 5
    @BhavikAmbani The question seems fairly well written actually - it could use some formatting to help readability though. – Paul Bellora May 11 '12 at 19:28
  • @PaulBellora Because no one will read the whole thesis to solve your problem. – Bhavik Ambani May 11 '12 at 19:29
  • One suggestion would be to use a debugger like jGrasp to look at the variables. Good luck with CS! (I just finished my second year). It is a little long, but much better than the one-sentence questions newbies usually ask. – SomeKittens May 11 '12 at 19:31
  • My apologies for any clarity/formatting issues. I guess I am just looking for some help on where to look to fix this issue. I am having trouble following it through the recursive calls in my debugger and have no idea at this point where I am going wrong. – Shea Gunther May 11 '12 at 19:31
  • 5
    @BhavikAmbani I thought it was important to clearly lay out the details of the problem I'm having and did it as concisely as I could. – Shea Gunther May 11 '12 at 19:33
  • 3
    @BhavikAmbani The fact you thought it was my question probably shows you didn't even bother to read it carefully before commenting on it. – Paul Bellora May 11 '12 at 19:34
  • Please dont mind but no one bothers to read that much things. – Bhavik Ambani May 11 '12 at 19:35
  • Are 'currentRow' and 'currentColumn' globals? If so, you may be able to save yourself some trouble by just passing them as arguments to findTour(). – Thomas May 11 '12 at 19:37
  • @Thomas They are. I want to make sure I understand what you are suggesting—if I passed them to findTour(), then I wouldn't have to juggle them when I undo the unsuccessful move? – Shea Gunther May 11 '12 at 19:42
  • 2
    @BhavikAmbani That's not true, I read the whole thing. I think it's a very well written question. – Dan W May 11 '12 at 19:46
  • 1
    @SheaGunther Yes, they would be in scope only for that function, and would not be modified by the children calls. That said, I have no idea if this is the cause of your problem. – Thomas May 11 '12 at 19:58
  • @BhavikAmbani - **please**, take this to the [chat](http://chat.stackoverflow.com/). – Eliran Malka May 11 '12 at 20:13
  • May I suggest not to use ints to tell that a field is visited? – Behe May 11 '12 at 20:25

1 Answers1

5

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?

Thomas
  • 5,074
  • 1
  • 16
  • 12
  • I figured out that my numberOfMovesOnBoard was off by 1. I had it set to the number of squares squared. That's the right amount if the tour is to be closed-if the knight lands back on the first square he jumped to, but as my code right now is looking for an open solution, the number of moves on the board is the square of the number of squares minus 1. That hasn't solved the problem yet, but it's nice to fix. Onward and upward. – Shea Gunther May 11 '12 at 21:41
  • I don't think I've solved my issue yet, but it did just successfully find a tour for a 5x5 board. – Shea Gunther May 11 '12 at 22:08