Can someone help me with this knight's tour code?

Question

The code seems fine to me, but the output is too short and the answer is no when it should be yes (starting at a,0, the knight should be able to tour the entire board)

By the way, the reason my positionsVisted array is [9][9] is because I wanted the values to be 1-8, to match the output.

public class KnightChessRiddle {
static // given a chess board and a 0,0 starting point, can a knight pass through
// all the the squares without passing
// a square twice

int[][] positionsVisited = new int[9][9];
static int positionX = 1;
static int positionY = 1;
boolean stop = false;
static boolean continUe = false;
static int moveCounter = -1;

public static void main(String[] args) {
    if (recursive(1, 1, 0)) {
        System.out.println("yes");
    }
    else System.out.println("no");
}

public static boolean recursive(int x, int y, int moveType){


    if (x>8||x<=0||y>8||y<=0) return false;
    if (positionsVisited[x][y]==1) {
        return false;
    }
    positionX = x;
    positionY = y;
    positionsVisited[positionX][positionY]++;

    char c;
    c='a';
    switch (positionX) {
    case 1:
        c='a';
        break;
    case 2:
        c='b';
        break;
    case 3:
        c='c';
        break;
    case 4:
        c='d';
        break;
    case 5:
        c='e';
        break;
    case 6:
        c='f';
        break;
    case 7:
        c='g';
        break;
    case 8:
        c='h';
        break;

    default: 
        break;
    }
    moveCounter++;
    System.out.println("doing move "+moveType+" move count: "+moveCounter);
    System.out.println("Knight is in "+ c +","+positionY);

    try {
        Thread.sleep(100);
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    if (recursive(positionX+2, positionY+1, 1)) {
        return true;
    }
    else if (recursive(positionX+1, positionY+2, 2) ) {
        return true;
    }
    else if (recursive(positionX+2, positionY-1, 3) ) {
        return true;
    }
    else if (recursive(positionX+1, positionY-2, 4)) {
        return true;
    }
    else if (recursive(positionX-2, positionY+1, 5)) {
        return true;
    }
    else if (recursive(positionX-1, positionY+2, 6)) {
        return true;
    }
    else if (recursive(positionX-2, positionY-1, 7)) {
        return true;
    }
    else if (recursive(positionX-1, positionY-2, 8)) {
        return true;
    }
    else return false;
}

This is the output of the program:

doing move 0 move count: 0
Knight is in a,1
doing move 1 move count: 1
Knight is in c,2
doing move 1 move count: 2
Knight is in e,3
doing move 1 move count: 3
Knight is in g,4
doing move 2 move count: 4
Knight is in h,6
doing move 5 move count: 5
Knight is in f,7
doing move 1 move count: 6
Knight is in h,8
doing move 8 move count: 7
Knight is in g,6
doing move 4 move count: 8
Knight is in h,4
doing move 5 move count: 9
Knight is in f,5
doing move 2 move count: 10
Knight is in g,7
doing move 4 move count: 11
Knight is in h,5
doing move 5 move count: 12
Knight is in f,6
doing move 1 move count: 13
Knight is in h,7
doing move 5 move count: 14
Knight is in f,8
doing move 7 move count: 15
Knight is in d,7
doing move 4 move count: 16
Knight is in e,5
doing move 4 move count: 17
Knight is in f,3
doing move 2 move count: 18
Knight is in g,5
doing move 4 move count: 19
Knight is in h,3
doing move 5 move count: 20
Knight is in f,4
doing move 4 move count: 21
Knight is in g,2
doing move 7 move count: 22
Knight is in e,1
doing move 6 move count: 23
Knight is in d,3
doing move 3 move count: 24
Knight is in f,2
doing move 3 move count: 25
Knight is in h,1
doing move 6 move count: 26
Knight is in g,3
doing move 5 move count: 27
Knight is in e,4
doing move 5 move count: 28
Knight is in c,5
doing move 1 move count: 29
Knight is in e,6
doing move 5 move count: 30
Knight is in c,7
doing move 1 move count: 31
Knight is in e,8
doing move 8 move count: 32
Knight is in d,6
doing move 5 move count: 33
Knight is in b,7
doing move 1 move count: 34
Knight is in d,8
doing move 8 move count: 35
Knight is in c,6
doing move 1 move count: 36
Knight is in e,7
doing move 1 move count: 37
Knight is in g,8
no

Answer 1

Except problem with "all is visited" check I see at least one more problem, which is in class fields. When algorithm passes one branch of recursion, it marks some squares as visited, and since this information is class field, when it fails current branch and starts another, it sees all invalid information from previous attempts.

What if you try to pass positionsVisited, positionX and positionY as method arguments and remove it from class fields, so each method call will have it's own actual copy?

---

Final version

public class KnightChessRiddle {

    private final static Map<Integer, Character> letters = new HashMap<>();

    static {
        letters.put(0, 'a');
        letters.put(1, 'b');
        letters.put(2, 'c');
        letters.put(3, 'd');
        letters.put(4, 'e');
        letters.put(5, 'f');
    }

    public static void main(String[] args) {
        if (recursive(0, 0, 0, new boolean[6][6], 1, "")) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }

    private static boolean allVisited(boolean[][] positionsVisited) {
        for (int i = 0; i < positionsVisited.length; i++) {
            for (int j = 0; j < positionsVisited.length; j++) {
                if (!positionsVisited[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean recursive(int positionX, int positionY, int moveType,
            boolean[][] positionsVisited, int moveCounter, String currentMoves) {

        // checks
        if (allVisited(positionsVisited)) {
            System.out.println(currentMoves);
            return true;
        }

        if (positionX > 5 || positionX < 0 || positionY > 5 || positionY < 0) {
            return false;
        }

        if (positionsVisited[positionX][positionY]) {
            return false;
        }

        // make move
        positionsVisited[positionX][positionY] = true;

        char c = letters.get(positionX);
        currentMoves += "" + c + (positionY + 1) + " (move type: " + (moveType + 1) + ")\r\n";

        if (recursive(positionX + 2, positionY + 1, 1, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX + 1, positionY + 2, 2, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX + 2, positionY - 1, 3, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX + 1, positionY - 2, 4, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX - 2, positionY + 1, 5, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX - 1, positionY + 2, 6, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX - 2, positionY - 1, 7, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else if (recursive(positionX - 1, positionY - 2, 8, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
            return true;
        } else {
            return false;
        }

    }

    private static boolean[][] cloneArray(boolean[][] src) {
        boolean[][] newPositions = new boolean[src.length][src.length];
        for (int i = 0; i < src.length; i++) {
            System.arraycopy(src[i], 0, newPositions[i], 0, src[0].length);
        }
        return newPositions;
    } 
}

Here is the working variation with 6x6 board. With 8x8 board calculations take too much time on my machine. Maybe it can be faster if you randomize move selection.

Answer 2

The algorithm you have implemented is the following:

Order the possible knight's moves from a square as follows:

On each move, choose the lowest numbered move that is still allowed.

(A) If you cover all the squares, return true.

(B) If you can no longer make a move, return false.

There are two problems with your code. The first, which has been pointed out already, is that you miss out the check (A). The second, more serious, problem is that this algorithm does not work. In fact, you end up with the following:

In this picture, the black knights represent the start and end squares, while the white knights are all the other squares covered. If you follow your algorithm, you eventually end up in a square where you can't get to any other squares that haven't been covered already. That doesn't mean that you can't do a knight's tour on a chessboard, just that your algorithm doesn't work.

---

If that really is the algorithm you want to implement, then there is no reason to use recursion, as a for loop will work just as well. Your function recursive returns true when there exists a valid knight's move from the square we are currently on. There are two reasons that this is not actually a recursive algorithm:

1. The recursive function is not idempotent - it has a side effect, which is to fill in a square of the positionsVisited array.
2. The recursive function calls on a global variable - positionsVisited (I say 'global variable', rather than 'private field', because what you have written is essentially procedural code).

Instead, the function recursive should tell you a much more general piece of information: given a particular square on the chess board, and a particular set of squares which we are not allowed to visit, is there a knight's tour of the remaining squares? (Of course, calling that function with the square a1 and an empty array of visited positions will tell you whether there is a knight's tour at all.) The function can also return a string which will tell you what the knight's tour is.

The structure of the recursive function should then be something like the following:

private boolean isKnightsTour(Square currentSquare,
                              int[9][9] visitedSquares,
                              KnightsTour tour)
{
  // Append the current square to the array of visited squares.
  int[9][9] newVisitedSquares = visitedSquares;
  newVisitedSquares[currentSquare.getX()][currentSquare.getY()] = 1;

  // If we have visited all the squares, there is a knight's tour.  
  // Add some code here to check for that.
  if (allSquaresVisited()) {
    tour = new KnightsTour(currentSquare);
    return true;
  }

  // Test all squares a knight's move away.  If you get a knight's tour, 
  // append the current square to the start and return that.  
  KnightsTour newTour;
  if (isKnightsTour(currentSquare.doMove1(), newVisitedSquares, newTour) {
    newTour.appendStart(currentSquare);
    tour = newTour;
    return true;
  }

  // Repeat for the other knight's moves.

  else {
    tour = null;
    return false;
  }
}

Or, in words:

Recursively check all the squares a knight's move away from the current square, passing in both the new square and a new array of visited squares formed by adding the current square. If there is a knight's tour from one of those squares, append the current square to the beginning of it to get a knight's tour from the current square.

Rather than what you've written which is:

Recursively build up a knight's tour by starting at a square and (fairly arbitrarily) choosing a legal knight's move at each step. If we get to a position where we can't do any more knight's moves, return false.

Can you see why the first (admittedly more complicated) recursive algorithm works and yours doesn't?