7
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I have edited my code in my program to follow the coding convention. It does not speed up my program, however \$\endgroup\$ – DanSchneiderNA Oct 26 '14 at 1:32
  • \$\begingroup\$ Thanks for all of the info! I tried to do vnp's solution but became confused. Thanks for clearing that up! \$\endgroup\$ – DanSchneiderNA Oct 27 '14 at 13:04
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Running in a clockwise manner never ends. But anti-clockwise, is extremely fast for N=8 \$\endgroup\$ – dEmigOd Jun 10 '18 at 7:17
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I agree switching to something other than backtracking would be faster, but it is required in the assignment to use backtracking. If I initialize border cells to -2, would I eliminate bound checking by testing if the current cell was -2? I'm a little confused on how padding the border would make the solution any faster. I will check into some heuristics to possibly add to my solution. \$\endgroup\$ – DanSchneiderNA Oct 16 '14 at 21:49
  • \$\begingroup\$ Update: I checked online on ways to check for least possible combinations. As far as I can tell, all of the solutions show for ways that do not involve backtracking. I may not be understanding the solution, but I am very confused as to what they are doing. I am very confused overall. \$\endgroup\$ – DanSchneiderNA Oct 17 '14 at 6:10
1
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.