Making backtracking Knight's Tours solution more efficient

Question

This was a previous homework assignment I was required to do. While I did the assignment and turned it in for credit, I am not completely satisfied with the result I have. The rule for the assignment is it HAS to use backtracking and HAS to let the user pick a point which they want to start. It works well enough for boards less than size 8, but once it reaches 8 it takes an incredibly long time. Too long.

import java.awt.Point;

import java.util.Scanner;

/**
 * The Knight's Tour using backtracking
 *
 * @author Tyler Weaver
 */
public class TheKnigthsTour {

    private final static int BOARD_LENGTH = 8;      //The length of the board
    private static int board[][];                   //The simulated board

    //List of possible moves for the knight
    private static final Point[] MOVES = new Point[]{new Point(-2, -1),
        new Point(-2, 1), new Point(2, -1), new Point(2, 1), new Point(-1, -2),
        new Point(-1, 2), new Point(1, -2), new Point(1, 2)};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.printf("Enter starting row (0-7): ");
        int row = in.nextInt();
        System.out.printf("Enter starting column (0-7): ");
        int col = in.nextInt();

        solveTour(row, col);
    }

    /**
     * Helper method to determine if a square is safe for the knight
     *
     * @param row the row the knight is on
     * @param col the column the knight is on
     * @return true if the square is safe for the knight
     */
    private static boolean isSafe(int row, int col) {
        return ((row >= 0 && row < BOARD_LENGTH)
                && (col >= 0 && col < BOARD_LENGTH)
                && (board[row][col] == -1));
    }

    /**
     * Helper method to print the tour solution to the console
     */
    private static void printTour() {
        for (int r = 0; r < BOARD_LENGTH; r++) {
            for (int c = 0; c < BOARD_LENGTH; c++) {
                System.out.printf("%-8d", board[r][c]);
            }

            System.out.printf("%n");
        }
    }

    /**
     * Solves the knight's tour using backtracking
     *
     * @param sRow the starting row
     * @param sCol the starting column
     */
    public static void solveTour(int sRow, int sCol) {
        board = new int[BOARD_LENGTH][BOARD_LENGTH];
        //Make all of board -1 because have not visited any square
        for (int r = 0; r < BOARD_LENGTH; r++) {
            for (int c = 0; c < BOARD_LENGTH; c++) {
                board[r][c] = -1;
            }
        }

        board[sRow][sCol] = 1;

        if (solveTour(sRow, sCol, 2)) {
            printTour();
        } else {
            System.out.printf("No Solution!%n");
        }
    }

    /**
     * Helper method that solve the tour
     *
     * @param row the current row
     * @param col the current column
     * @param kthMove the current move
     * @return true if there is a solution to the knight's tour
     */
    private static boolean solveTour(int row, int col, int kthMove) {
        //Base case
        if (kthMove > BOARD_LENGTH * BOARD_LENGTH) {
            return true;
        }

        for (Point p : MOVES) {
            int nextRow = row + (int) p.x;
            int nextCol = col + (int) p.y;

            if (isSafe(nextRow, nextCol)) {
                board[nextRow][nextCol] = kthMove;

                kthMove = kthMove + 1;

                if (solveTour(nextRow, nextCol, kthMove)) {
                    return true;
                } else {
                    board[nextRow][nextCol] = -1;
                    kthMove = kthMove - 1;
                }
            }
        }

        return false;
    }
}

I have tried doing research online to find more ways to be efficient. Many of the solutions, however, use a technique other than backtracking. While I agree that backtracking is not the best recursive solution, it is one I am required to use. There is one solution that mentioned using data structures to improve time but I am unsure where to even begin with that.

Here is some sample output from the program if it is any help:

BOARD_LENGTH = 5;

Enter starting row (0-7): 2
Enter starting column (0-7): 3
No Solution!

BOARD_LENGTH = 7;

Enter starting row (0-7): 0
Enter starting column (0-7): 0
1       14      3       38      5       34      7       
12      39      10      33      8       37      26      
15      2       13      4       25      6       35      
40      11      32      9       36      27      44      
19      16      21      24      45      48      29      
22      41      18      31      28      43      46      
17      20      23      42      47      30      49

Even for board length of 7 it takes a long time to compute if the starting location is not (0, 0).

In what ways can I improve the time of computing a solution for this program?

Answer 1

Single responsibility principle

The solveTour(int sRow, int sCol) method is clearly violating the single responsibility principle, as it is

1. Initializing the board array
2. Setting the first move
3. Doing parts of the output

If you let solveTour(int sRow, int sCol) return a boolean signaling success or failure you can do the printing outside.

Extract the initialization of the board array to a separate method.

private static void initializeBoard() {
    board = new int[BOARD_LENGTH][BOARD_LENGTH];
    //Make all of board -1 because have not visited any square
    for (int r = 0; r < BOARD_LENGTH; r++) {
        for (int c = 0; c < BOARD_LENGTH; c++) {
            board[r][c] = -1;
        }
    }
}

Now solveTour(int,int) can be refactored to

public static boolean solveTour(int sRow, int sCol) {
    initializeBoard();

    board[sRow][sCol] = 1;

    return solveTour(sRow, sCol, 2);
}  

Cast only if necessary

As a Point's x and y already are int's the casts are not necessary.

int nextRow = row + (int) p.x;
int nextCol = col + (int) p.y;  

should be

 int nextRow = row + p.x;
 int nextCol = col + p.y;  

Nitpicking

You have

private final static int BOARD_LENGTH = 8;

but you missed to have

private final static int MAX_MOVES = 64;  

In this way you could refactor

private static boolean solveTour(int row, int col, int kthMove) {
    //Base case
    if (kthMove > BOARD_LENGTH * BOARD_LENGTH) {
        return true;
    }
....  

to

private static boolean solveTour(int row, int col, int kthMove) {
    //Base case
    if (kthMove > MAX_MOVES) {
        return true;
    }
    ....

EDIT (Based on the question about faster execution in the comments)

Speed

Border

To make your application solving the problem faster, vnp already gave you a great answer.
To show it in greater detail, assume you have a 5x5 board which is initialized with 1(for formatting only) with a border of 2 initialized with 0

000000000
000000000
001111100
001111100
001111100
001111100
001111100
000000000
000000000

Until now you checked in the isSafe() method

 return ((row >= 0 && row < BOARD_LENGTH)
                && (col >= 0 && col < BOARD_LENGTH)
                && (board[row][col] == -1));

because checking directly for board[row][col] == -1) could result in an IndexOutOfBound exception. By adding the border the first four checks can be safely removed, because the checking of a position inside of the border will always return false, so it won't be taken as a valid position, so the move will be reverted.

As long as you don't initialize the border neither with a valid move (>0) nor with the initialization value (-1) this will work.

The isSafe() method will be reduced to

private static boolean isSafe(int row, int col) {
    return (board[row][col] == -1));
}

Flattening

Another additional posibility, also I don't think this will make a big difference here, will be the flattening of your jagged array.

Preevaluation

The next big speed improvement could be the preevaluation of possible moves.
As of the nature of the board, you can use the knight, on some positions only limited.
E.g in the corners the knight has only 2 possible moves. So if you preevaluate these moves at initialization stage, you need to check for less moves and therefor speed up your algorithm.

See also a nice picture here: http://en.wikipedia.org/wiki/Knight%27s_tour

Answer 2

I came across the same problem. Everything runs smoothly till n=7 and suddenly it takes forever to calculate for n=8.

The problem lies with the order in which you are checking for the moves. You are using :

xMove[8] = { -2, -2, 2, 2, -1, -1, 1, 1}

yMove[8] = { -1, 1, -1, 1, -2, 2, -2, 2}

If you plot these vectors in the 2D plane, they are haphazardly placed. In other words, they are not ordered in either a clockwise or an anti-clockwise manner. However, by using this instead :

xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }

yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }

If you plot these vectors, they are neatly arranged in an anticlockwise circle. Somehow this causes the recursion to run much quickly for large values of n. Mind you, it still takes forever to calculate for n=9 onwards.

Answer 3

Backtracking doesn't mean blind. You still can exercise some heuristics: which order to inspect moves, for example (it is recommended to look for a move with the least possible continuations).

An isSafe method could be simplified with a certain gain of performance if you surround the board with a thick border. Initialize the border cells to -2, and eliminate bound checking of row, col.

Another possible speedup would be to switch to iterative solution. You'd need to maintain the stack of moves manually.

Answer 4

Backtracking algorithms (in which the knight is allowed to move as far as possible until it comes to a blind alley, at which point it backs up some number of steps and then tries a different path) can be used to find knight's tours, but such methods can be very slow.

Reason for that is, even for 8x8 board there are huge number of unique length 64 sequences, but only few result in Hamilton path. You can imagine the problem as graph:

To get better result faster you basically need to find a way to do less work. A way to do less work would be to make better decisions usually it is called choosing a heuristic function.

Warnsdorff (1823) proposed an algorithm that finds a path without any backtracking by computing ratings for "successor" steps at each position. Here, successors of a position are those squares that have not yet been visited and can be reached by a single move from the given position. The rating is highest for the successor whose number of successors is least. Here is C++ example implementation

If you want to do even better, then take a look at more optimized version. For 8x8 board starting at position 1;1 following would be an answer:

As a bonus, I generated answers for few more board sizes (up to 200 in dimension): https://www.dropbox.com/sh/wkmcsnb0j7k1f0o/AACDbdLFveOVG1717LY3fX9la?dl=0

Solutions are found in under 1 s.