Knight's tour recursive approach Java

Question

I'm trying to implement the knight's tour recursively.. below is my code. I chose the board to be 5x5 for simplicity. My goal is to print out the correct knight placements and possibly show backtracking at the same time with print statements.

class Knight
{
public boolean[][] board = new boolean[5][5];

public final int SQUARES = 5*5-1;

public Knight()
{

    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            board[i][j] = false;

}

public boolean tour(int x, int y, int visitedX, int visitedY,int n)// x,y coords, just visited x,y and counter n
{

    if(x>=5||y>=5||x<0||y<0){ //out of bounds
        System.out.println("Visited "+x+", "+y+" Out of bounds");
        System.out.println("Back to "+visitedX+", "+visitedY);
        return false;
    }
    else{
        if(board[x][y] == true)
        {return false;}
        if(board[x][y]!=true){
            boolean result = false;
            board[x][y]=true;
            System.out.println("Visited "+x+", "+y);
            result = tour(x+2,y+1,x,y,n+1); 
            result = tour(x+2,y-1,x,y,n+1); 
            result = tour(x+1,y-2,x,y,n+1); 
            result = tour(x-1,y-2,x,y,n+1); 
            result = tour(x+1,y+2,x,y,n+1); 
            result = tour(x-1,y+2,x,y,n+1);
            result = tour(x-2,y-1,x,y,n+1); 
            result = tour(x-2,y+1,x,y,n+1); 

        }
    }
    return false;
}
}
public class KnightTApp {

public static void main(String[] args) {
    Knight k = new Knight();
    k.tour(0,0,0,0,0);

}

}

part of print output

Visited 4, 0
Visited 6, 1 Out of bounds
Back to 4, 0
Visited 6, -1 Out of bounds
Back to 4, 0
Visited 5, -2 Out of bounds
Back to 4, 0
Visited 3, -2 Out of bounds
Back to 4, 0
Visited 5, 2 Out of bounds
Back to 4, 0
Visited 2, -1 Out of bounds
Back to 4, 0
Visited 2, 0

My problem is in the middle of the process, I run into a dead end situation(where not all squares are covered yet there are no legal moves I can make) at index 4,0. And Since I have not included any lines for backtracking. It just jumps to index 2,0 which is not even a legal knight move.

My question is how do I express a Dead end situation with an if statement? I think I should set the recursion to some kind of boolean and go from there but I have no idea how to do it.

And also is using recursion same as using DFS(depth first search) because they basically have the same idea?

Thank you in advance.

Answer 1

You need to get clear of whether you are trying to identify all possible tours or just to find a single valid tour.

To get complete backtracking you would need to mark the board field free again at the end of tour when returning to the caller.

Second, you would need to check the outcome of each recursive call on tour(). if true you found a valid constellation and you can return true back also. Otherwise try the next possible move. if no move left return false.

Finally you are missing a proper termination condition: "What is success?" In your case, if you have 5x5 successful moves, all fields have been visited and you may just return true signalling that success.

You might also want to track the sequence of moves for having a chance to output a successful tour.

The above is targetting identifying a single successful tour.
With tracking the sequence of moves you may keep track of all successful tours and instead of just returning true on the deepest recursion check known tours and return true if it is a new one.

For reference a modified version of your code addresing the "find any" part:

class Knight {
    public final static int SIZE = 5;

    public boolean[][] board = new boolean[SIZE][SIZE];
    public String[] moves = new String[SIZE * SIZE];

    public Knight() {

        for (int i = 0; i < 5; i++ ) {
            for (int j = 0; j < 5; j++ ) {
                board[i][j] = false;
            }
        }

    }

    public boolean tour(final int x, final int y, final int n)
    {
        if (n >= SIZE * SIZE) {
            return true;
        } else if (x >= 5 || y >= 5 || x < 0 || y < 0) { // out of bounds
            return false;
        } else if (board[x][y]) {
            return false;
        } else {
            // System.out.println("Checking " + n + ": " + x + "," + y);
            board[x][y] = true;
            moves[n] = x + "-" + y;
            if (tour(x + 2, y + 1, n + 1)) {
                return true;
            }
            if (tour(x + 2, y - 1, n + 1)) {
                return true;
            }
            if (tour(x + 1, y - 2, n + 1)) {
                return true;
            }
            if (tour(x - 1, y - 2, n + 1)) {
                return true;
            }
            if (tour(x + 1, y + 2, n + 1)) {
                return true;
            }
            if (tour(x - 1, y + 2, n + 1)) {
                return true;
            }
            if (tour(x - 2, y - 1, n + 1)) {
                return true;
            }
            if (tour(x - 2, y + 1, n + 1)) {
                return true;
            }
            board[x][y] = false;
            moves[n] = null;
            return false;
        }
    }

    public static void main(final String[] args) {
        final Knight k = new Knight();

        for (int i = 0; i < SIZE; i++ ) {
            System.out.println("Starting at " + i + " 0");

            if (k.tour(i, 0, 0)) {
                k.printTour(true);
                break;
            }
            k.printTour(true);
        }
    }

    /**
     * @param result
     */
    private void printTour(final boolean result) {
        System.out.println("Found tour: " + result);
        int i = 0;
        if (result) {
            for (final String m : moves) {
                System.out.println("M-" + i + ": " + moves[i]);
                i++ ;
            }
        }
    }
}

Answer 2

You might want to use a Stack data structure and with each move evaluate all possible valid moves, pushing each onto the stack. When you make a valid move, pop it off the stack.

A dead-end situation would be when your evaluate method returns 0 possible moves.