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): 2Enter starting column (0-7): 3No Solution!BOARD_LENGTH = 7;Enter starting row (0-7): 0Enter starting column (0-7): 01       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      49Even 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?
Making backtracking Knight's Tours solution more efficient
java;optimization;algorithm
Single responsibility principleThe solveTour(int sRow, int sCol) method is clearly violating the single responsibility principle, as it is Initializing the board arraySetting 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  000000000000000000001111100001111100001111100001111100001111100000000000000000000Until 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