Making backtracking Knight's Tours solution more efficient

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 = 0 && col 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, kt

Single responsibility principle

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

• Initializing the board array

• Setting the first move

• 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 = 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

StackExchange Code Review Q#66888, answer score: 5