java recurison – Need help for solving backtracking Knight’s Tour

I am working on the Knight’s Tour problem. In my program the user can select a number n equal to 3 or higher. The number will determine the table’s size by n*n in a two-dimensional array. Then the knight will start it’s tour based on the starting points given by the user as long as they are higher or equal to 0.

My problem comes when the knight has come to a dead end (as of turn number 12 in the visualization table in the output). I want to somehow track it’s movements so that I can block the dead end, go back a step and try from there. I’ve figured out that I might need a three-dimensional array so that I can save all the turn numbers in each square. But then again I need an ArrayList witch isn’t static. Any suggestions will be appreciated. Here’s my code:

    package knightsTour;

    import java.util.Scanner;
    import java.util.ArrayList;

    public class KnightsTour
    {
        private static int turns = 0;
        private static ArrayList<String> moves = new ArrayList<String>();

        private static int squares;
        private static int table[][];

        private static boolean takeTour(int x, int y) {
            // Checks if all squares is used. If true, algorithm will stop
            if (checkIfFinished())
                return true;

            table[x][y] = ++turns;

            // 2 Left, 1 Down
            if (x > 1 && y < squares -1 && table[x-2][y+1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Down.  Turn: " + turns);
                if (takeTour(x-2, y+1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Left, 1 Up
            if (x > 1 && y > 0 && table[x-2][y-1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Up.    Turn: " + turns);
                if (takeTour(x-2, y-1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Up, 1 Left
            if (y > 1 && x > 0 && table[x-1][y-2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Left.    Turn: " + turns);
                if (takeTour(x-1, y-2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Up, 1 Right
            if (y > 1 && x < squares -1 && table[x+1][y-2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Right.   Turn: " + turns);
                if (takeTour(x+1, y-2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Right, 1 Up
            if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up.   Turn: " + turns);
                if (takeTour(x+2, y-1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Right, 1 Down
            if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down. Turn: " + turns);
                if (takeTour(x+2, y+1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Down, 1 Right
            if (y < squares -2 && x < squares-1 && table[x+1][y+2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Right. Turn: " + turns);
                if (takeTour(x+1, y+2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            // 2 Down, 1 Left
            if (y < squares -2 && x > 0 && table[x-1][y+2] == 0)
            {
                moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Left.  Turn: " + turns);
                if (takeTour(x-1, y+2))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
/*
            I need some code here before it gives up searching
*/  
            // If we'd tried every single paths
            // and we still end up here, there's no solution
            return false;
        }

        // Checks if all squares is used
        private static boolean checkIfFinished()
        {
            for (int i = 0; i < squares; i++)
            {
                for (int j = 0; j < squares; j++)
                {
                    if (table[i][j] == 0)
                        return false;
                }
            }
            return true;
        }

        // Made this to save code from 3 duplicates
        private static void invalidNumber()
        {
            System.out.println("Invalid number! Killing proccess");
            System.exit(0);
        }

        public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
            System.out.print("Number of squares: ");
            squares = Integer.parseInt(sc.nextLine());
            if (squares < 3 )
                invalidNumber();

            System.out.println("Note: Start values is from 0 -> n-1"
                            + "n0,0 is at top left side");
            System.out.print("X start value: ");
            int x = Integer.parseInt(sc.nextLine());
            if (x < 0 || x > squares -1)
                invalidNumber();

            System.out.print("Y start value: ");
            int y = Integer.parseInt(sc.nextLine());
            if (y < 0 || y > squares -1)
                invalidNumber();
            sc.close();

            table = new int[squares][squares];

            boolean tourComplete = takeTour(x, y);

            for (String s : moves)
            {
                System.out.println(s);
            }
            if (!tourComplete)
                System.out.println("Did not find any way to complete Knights Tour!");

            // Print the table with the move-numbers
            for (int i = 0; i < squares; i++)
            {
                for (int j = 0; j < squares; j++)
                {
                    System.out.printf("%4d", table[j][i]);
                }
                System.out.println();
            }
        }
    }

My output for a 4*4 table looks like this:

Number of squares: 4
Note: Start values is from 0 -> n-1
0,0 is at top left side
X start value: 0
Y start value: 0
X: 0, Y: 0. Moving 2 Right, 1 Down. Turn: 1
X: 2, Y: 1. Moving 2 Left, 1 Down.  Turn: 2
X: 0, Y: 2. Moving 2 Up, 1 Right.   Turn: 3
X: 1, Y: 0. Moving 2 Right, 1 Down. Turn: 4
X: 3, Y: 1. Moving 2 Left, 1 Down.  Turn: 5
X: 1, Y: 2. Moving 2 Up, 1 Right.   Turn: 6
X: 2, Y: 0. Moving 2 Left, 1 Down.  Turn: 7
X: 0, Y: 1. Moving 2 Right, 1 Down. Turn: 8
X: 2, Y: 2. Moving 2 Left, 1 Down.  Turn: 9
X: 0, Y: 3. Moving 2 Up, 1 Right.   Turn: 10
X: 1, Y: 1. Moving 2 Right, 1 Up.   Turn: 11
Did not find any way to complete Knights Tour!
   1   4   7  12
   8  11   2   5
   3   6   9   0
  10   0   0   0

Answer

When trying different possibilities on BackTracking you need to check them all in every recursion step. In the code you provide in a single step you only try one possibility and then return. Doing this you are not able to explore all the possibilities.

My suggestion is to change the function arguments to accept the current position (x,y) and a boolean array for the positions that have been previously visited. If you need to construct the path of the final valid solution, I also suggest to add the step count (the number of steps you have done) and a int array to store which position has been visited in which step.

Next I provide a solution which is not the most efficient. In fact, you can try to prune the backtracking possibilities to avoid the recurssion explosion (cpu efficiency) and you can try to avoid some copies of the matrixes (memory efficiency).

package knightsTour;

import java.util.Scanner;


public class KnightsTour {

private static final int[] MOVE_X = new int[] { -2, -2, -1, -1, +1, +1, +2, +2 };
private static final int[] MOVE_Y = new int[] { +1, -1, +2, -2, +2, -2, +1, -1 };

private final int SQUARES;
private final int INIT_X;
private final int INIT_Y;

private int[][] path;


public KnightsTour(int squares, int x, int y) {
    this.SQUARES = squares;
    this.INIT_X = x;
    this.INIT_Y = y;
}

public int[][] getPath() {
    return this.path;
}

public boolean takeTour() {
    boolean[][] visited = new boolean[this.SQUARES][this.SQUARES];
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            visited[i][j] = false;
        }
    }
    visited[this.INIT_X][this.INIT_Y] = true;

    this.path = new int[this.SQUARES][this.SQUARES];

    return takeTourBT(this.INIT_X, this.INIT_Y, 0, visited, this.path);
}

private boolean takeTourBT(int posX, int posY, int step, boolean[][] visited, int[][] path) {
    debug(step, visited);

    if (checkIfFinished(visited)) {
        return true;
    }

    // Increase the step count
    ++step;

    // Try recursively (cut when a branch success)
    boolean success = false;
    for (int i = 0; i < MOVE_X.length && !success; ++i) {
        int nextX = posX + MOVE_X[i];
        int nextY = posY + MOVE_Y[i];
        if (nextX >= 0 && nextX < this.SQUARES && nextY >= 0 && nextY < this.SQUARES && !visited[nextX][nextY]) {
            // Next position is valid and has not been visited
            // Mark position
            visited[nextX][nextY] = true;
            // Call
            boolean branchSuccess = takeTourBT(nextX, nextY, step, visited, path);
            if (branchSuccess) {
                // We are comming back from the good solution, mark the path
                path[nextX][nextY] = step;
            }
            success = success | branchSuccess;
            // Unmark the position for next try
            visited[nextX][nextY] = false;
        }
    }

    return success;
}

// Adds some verbose for debugging
private void debug(int step, boolean[][] visited) {
    System.out.println("*********************** STEP " + String.valueOf(step) + " ***********************");
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            if (visited[i][j]) {
                System.out.print("X ");
            } else {
                System.out.print(". ");
            }
        }
        System.out.println("");
    }
    System.out.println("*******************************************************");
}

// Checks if all squares is used
private boolean checkIfFinished(boolean[][] visited) {
    for (int i = 0; i < this.SQUARES; ++i) {
        for (int j = 0; j < this.SQUARES; ++j) {
            if (!visited[i][j]) {
                return false;
            }
        }
    }

    return true;
}

public static void main(String[] args) {
    // Process arguments
    int squares = 0;
    int x = 0;
    int y = 0;
    try (Scanner sc = new Scanner(System.in)) {
        System.out.print("Number of squares: ");
        squares = Integer.parseInt(sc.nextLine());
        if (squares < 3) {
            throw new Exception("[ERROR] Invalid number of squares");
        }

        System.out.println("Note: Start values is from 0 -> n-1" + "n0,0 is at top left side");
        System.out.print("X start value: ");
        x = Integer.parseInt(sc.nextLine());
        if (x < 0 || x > squares - 1) {
            throw new Exception("[ERROR] Invalid start x position");
        }

        System.out.print("Y start value: ");
        y = Integer.parseInt(sc.nextLine());
        if (y < 0 || y > squares - 1) {
            throw new Exception("[ERROR] Invalid start y position");
        }
    } catch (Exception e) {
        // Error occurred, exit
        System.err.println("Killing process");
        System.exit(1);
    }

    // Initialize the KnightsTour
    KnightsTour kt = new KnightsTour(squares, x, y);

    // Make the tour
    boolean success = kt.takeTour();

    // Post process
    if (success) {
        System.out.println("The tour was sucessfull!");
    } else {
        System.out.println("Did not find any way to complete Knights Tour!");
    }

    int[][] path = kt.getPath();
    for (int i = 0; i < path.length; ++i) {
        for (int j = 0; j < path[i].length; ++j) {
            String stepSTR = (path[i][j] < 10) ? "0" + String.valueOf(path[i][j]) : String.valueOf(path[i][j]);
            System.out.print(stepSTR + " ");
        }
        System.out.println("");
    }
}

}

Try this code with size 5 and start position (0,0).

Notice that:

• You can enable/disable the debug iteration by commenting the debug call
• I compacted the way you perform the moves with 2 arrays to avoid replications but for the sake of clarity you can unroll it again.
• On each recursion step, before going depth, we check if we can perform moves, we mark the next position and proceed. On the way back, we unmark the position, check whether the move reached a successfull step or not and reconstruct the good solution if needed.