I'm trying to write a program for a university project. It should count all possible open tours (i.e. the start and end fields are not the same) recursively on a chessboard depending on board size and starting field (as per assignment). If the size is less than 6x6, all of the solutions should be displayed in chess notation. It's actually working quite well for sizes smaller than 6. But 6x6 takes way too long (about 30 minutes or more). Could anyone help me with optimizing my code?

Knight's tour explained in a video suggested by BKSpurgeon: https://www.youtube.com/watch?v=ab_dY3dZFHM

Update: The program should display all solutions in chess notation starting from a specified field for board sizes between 1x1 and 5x5. So not all of the possible tours are required e.g. all tours starting from "a1". For example, there are 1728 open tours on a 5x5 board, but only 304 possible ones starting from an angle("a1" etc.). For the size of 6x6 only the number of tours should be displayed.

Update 2: Made a seperate method for the bigger board which is identical except String manipulation. Starting at "a1", I found 524486 solutions for about 572 seconds. Might try a profiler with better performance in mind.

import java.util.ArrayList;
import java.util.List;

public class Classic {

private Field[][] chessboard;
private List<String> solutions;
private int counterSolutions;
private int length;
private static String[] letters = {"a","b","c","d","e","f"}; //only 6 letters, as my assignment requires solutions for boards no larger than 6x6
private int[] rowMoves = {2, 1, -1, -2, -2, -1, 1, 2}; //possible Moves in 2 arrays
private int[] colMoves = {1, 2, 2, 1, -1, -2, -2, -1};     

public Classic(int length, String startingpos){
    this.length = length;
    this.chessboard = new Field[length][length];
    this.solutions = new ArrayList<String>();
    for(int i = length; i > 0; i--){
        for(int j = 0; j < length; j++){
            chessboard[i-1][j] = new Field(i-1, j, letters[j].concat(new Integer(i).toString()));
            for(int l = 0; l < 8; l++){
                if((((i-1 + rowMoves[l]) >= 0 && (i-1 + rowMoves[l]) < length) && ((j + colMoves[l]) >= 0 && (j + colMoves[l]) < length))){
                    chessboard[i-1][j].addMove(rowMoves[l], colMoves[l]);
                }
    //calculating moves, so that the knights stays on the board
            }
        }
    }
    switch(startingpos.charAt(0)){
    case 'a':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][0], 0, "");
        break;
    case 'b':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][1], 0, "");
        break;
    case 'c':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][2], 0, "");
        break;
    case 'd':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][3], 0, "");
        break;
    case 'e':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][4], 0, "");
        break;
    case 'f':
        tour(chessboard[Character.getNumericValue(startingpos.charAt(1))-1][5], 0, "");
        break;
    default:
        System.out.println("False input. Please enter the starting field in following form: a1");
        break;
    }

    printSolutions();
}

public void printSolutions(){
    if(this.length <= 5){
        for(String temp : this.solutions){
            System.out.println(temp);
        }
    }else{
        System.out.println("Solutions for boards bigger than 5x5 are not printed out");
    }

    if(this.counterSolutions == 0){
        System.out.println("No possible solutions exist");
    }else{
        System.out.println("Number of solutions: " + this.counterSolutions);
    }

}

public boolean tour(Field currentfield, int movecount, String way){

    String solution = way + " " + currentfield.getPos(); //saving the exact fields reached until now in a String

    if(movecount == (this.length*this.length) - 1 ){
        //Solution is found, because the knight has made the maximum number of moves
        solutions.add(solution);  //add solution to array list of solutions
        this.counterSolutions++; //increase solution number
        currentfield.reset();  //the field gets reset
        return true;
    }else{
        int temp = 0; //temporary variable for resetting the field, if all solutions fail
        for(Field field : currentfield.getMoves()){
            if((chessboard[currentfield.getX() + field.getX()][currentfield.getY() + field.getY()].isReached() == false)){
                currentfield.reach(); //if the field hasn't been reached yet, call the method recursively
                if(tour(chessboard[currentfield.getX() + field.getX()][currentfield.getY() + field.getY()], movecount + 1, solution)){
                    temp++;
                    currentfield.reset();
                }

            }
        }
        if(temp == 0){
            currentfield.reset(); //as described above
        }

    }

    return false;
}
}

Firstly, I create a String which gets longer each time a next move is possible. When the number of moves reaches length*length - 1 the String is added to an ArrayList of Strings in order for it to be stored for output. After that I've initialised a temporary integer to reset the field in case all attempts fail. If a possible way is found, the current field is marked as "reached" with reach(). If the recursive method returns true, it means that the solution has already been counted and the field is reset to enable any future calculations (the boolean reached becomes false).

This is the field class for reference:

import java.util.List;
import java.util.ArrayList;

public class Field {

private String position;
private boolean reached;
private int x,y;

private List<Field> moves;

public Field(int x, int y, String position){
    this.x = x;
    this.y = y;
    this.position = position;
    this.reached = false;
    this.moves = new ArrayList<Field>();
}

public void reach(){
    this.reached = true;
}

public boolean isReached(){
    return this.reached;
}

public void reset(){
    this.reached = false;
}

public String getPos(){
    return this.position;
}

public int getX(){
    return this.x;
}

public int getY(){
    return this.y;
}

public void addMove(int x, int y){
    this.moves.add(new Field(x, y, ""));
}

public List<Field> getMoves(){
    return this.moves;
}

}
  • 1
    I would advise to write all your code in English. Now you have a strange mix addZug, currentFeld etc. This makes it harder for non-german reviewers. – RobAu May 30 '17 at 11:25
  • @RobAu you're absolutely right, I've edited my post and everything should be in English now. Sorry for not considering that and thanks for the tip. – Alexander Ivanov May 30 '17 at 12:25
  • @AlexanderIvanov You do realise that execution times that high tend to indicate an algorithmic problem? No matter how much you optimize your current code, if you don't change the algorithm you're using, you are going to run into the same problem one or two steps further: even if you are able to solve 6x6 in a reasonable amount of time, 7x7 or 8x8 will still take a huge amount of time. – Ben Steffan May 30 '17 at 13:05
  • @AlexanderIvanov Citing from Wikipedia: "A brute-force search for a knight's tour is impractical on all but the smallest boards; for example, on an 8 × 8 board there are approximately 4×10^51 possible move sequences, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set." – Ben Steffan May 30 '17 at 13:07
  • @AlexanderIvanov youtube.com/watch?v=ab_dY3dZFHM for those who want a visual explanation of what's going on. btw yes BenStaffan is right 6 x6 is a LOT of squares. – BKSpurgeon May 30 '17 at 13:21
up vote 3 down vote accepted

Good to see it all in English :D

Observations

String manipulation

First of all, you do a lot of String manipulation, which is very slow, and unneeded. Always try to stay away from that. If you need a list, use a List. If you need a stack, use a Deque. Better even if you don't need it at all :D

Readability

You have a lot of nested code which looks very dense to me (a lot of text without white-space), and this makes it less readable.

Preprocessing the moves

In order to speed up the process, selecting to which field you have to jump first makes a huge difference in total performance. If you jump to the field which has the least options, you can speed up the total process by orders of magnitude. This is known as Warnsdorff’s algorithm.

Proof:

 0 15 38 31  2 17 48 21 
39 30  1 16 49 20  3 18 
14 37 50 55 32 61 22 47 
29 40 63 60 51 54 19  4 
36 13 56 53 62 33 46 23 
41 28 59 34 57 52  5  8 
12 35 26 43 10  7 24 45 
27 42 11 58 25 44  9  6 

On my laptop this takes around a second.

Some remarks:

Encoding the board and solution

You can use one board and encode the solution directly on the board. You don't need to keep a list, because all the information to mark a field as occupied (and release it if the path fails) is in the recursive method.

This prevents all the list/string keeping of the solution.

I reused the Point class from java.awt because that saves me some coding.

I use a special value to encode the no-used state, and put that in a static variable so the intent of the code becomes more clear, without having to add additional documentation.

The recursion

Setting up recursion is about these steps:

  • Check the current state
  • If illegal, backtrack
  • If done, finish/return
  • Call the recursive function again for all possible options

In my solution you can find this in findTour.

Basically, I run through the KingsTour.DIRECTIONS and calculate the new locations. I check if they are on the board, and if so, recurse into them.

Small optimizations

There is an optimization that I took for knowing that we are done. This however, uses an additional argument in the recursive call. What I do to determine that I'm done is to check if I made 64-levels of recursion without entering an invalid state. Of course, you could also check if the entire board is used.

Proposed solution

import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class KnightsTour
{
    int[][] board;

    List<Point>[][] possibleMoves; 

    final static int UNUSED = -1;

    final static Point[] DIRECTIONS = new Point[] { new Point( -1, -2 ), new Point( 1, -2 ), new Point( 2, -1 ), new Point( 2, 1 ), new Point( 1, 2 ),
        new Point( -1, 2 ), new Point( -2, 1 ), new Point( -2, -1 ) };

    int size;

    public KnightsTour( int n )
    {
        size = n;
        board = new int[n][n];
        possibleMoves = new List[n][n];
        for ( int y = 0; y < n; y++ )
        {
            for ( int x = 0; x < n; x++ )
            {
                board[x][y] = UNUSED;
                possibleMoves[x][y] = new ArrayList<>();
                for ( Point d : DIRECTIONS )
                {
                    //calculate the new position
                    int nx = x + d.x;
                    int ny = y + d.y;

                    //only process valid moves
                    if ( ( nx >= 0 && nx < size ) && ( ny >= 0 && ny < size ) )
                    {
                        possibleMoves[x][y].add( new Point(nx,ny) );
                    }
                }
            }
        }
        //we need to sort the possiblemoves, so that the first move is the one that has the least possiblemoves
        preprocessPossibleMoves( );
    }

    /**
     * I sort the possiblemoves so that it first goes to a field with as little as possible options.
     * <BR>
     * This is known as Warnsdorff’s algorithm
     */
    private void preprocessPossibleMoves()
    {
        for ( int y = 0; y < size; y++ )
        {
            for ( int x = 0; x < size; x++ )
            {
                List<Point> moves = possibleMoves[x][y];

                moves.sort( new Comparator<Point>()
                {

                    @Override
                    public int compare( Point o1, Point o2 )
                    {
                        int o1Moves = possibleMoves[o1.x][o1.y].size();
                        int o2Moves = possibleMoves[o2.x][o2.y].size();
                        return o1Moves - o2Moves;
                    }
                });
            }
        }
    }

    private void printBoard()
    {
        for ( int y = 0; y < size; y++ )
        {
            for ( int x = 0; x < size; x++ )
            {
                System.out.printf( "%2d ", board[x][y] );
            }
            System.out.println();
        }
        System.out.println();

    }

    private KnightsTour solve()
    {
        int x = 0;
        int y = 0;
        int current = 0;

        findTour( x, y, current );
        return this;
    }

    private boolean findTour( int x, int y, int current )
    {
        if ( board[x][y] != UNUSED )
        {
            return false;
        }

        //Mark current positoin as 'current'
        board[x][y] = current;

        if ( current == size * size - 1 )
        {
            //done :)
            return true;
        }

        for ( Point d : possibleMoves[x][y])
        {
            if ( findTour( d.x, d.y, current + 1 ) )
            {
                return true;
            }
        }

        //if we are here, all our options ran out :(
        //reset the current cell and return false
        board[x][y] = UNUSED;

        return false;
    }

    public static void main( String[] args )
    {
        new KnightsTour( 8 ).solve().printBoard();
    }
}
  • Re-reading out quesion, I saw you needed to count all possible tours. There are many! See math.stackexchange.com/a/820362/53495 . I guess my solution for 6x6 will take about 6637920 seconds :/ – RobAu May 30 '17 at 15:39
  • Thank you for all of the information! I am quite the beginner actually, and as a result my code is not always so readable :D. Regarding String manipulation: The thing is that my assignment requires also all of the possible tours to be dispalyed in chess notation(sorry for not clearing that up) for chessboards smaller than 6x6. For the latter only the number of tours should be displayed. Maybe I should create a separate method for bigger boards? – Alexander Ivanov May 30 '17 at 16:20
  • You are welcome :) You only need to be able to convert an int[][] board that contains a valid solution to a String representation (opposite to string manipulation in each recursion step, which happens many many times more). This would be a nice exercise for the astute reader :) – RobAu May 30 '17 at 16:35
  • That's a good idea, I might try that later on. I decided to make a seperate method for the bigger board. It's basically the same without the Strings. Starting at "a1" I found 524486 solutions for about 572 seconds. Do you think there's any room for improvement, bearing in mind I must solve this recursively? – Alexander Ivanov May 30 '17 at 18:41
  • 1
    There is not that much to gain (performance wise at least) anymore I think. You might want to attach a profiler and check where most time is spent, maybe I am overlooking something. It is worthwhile knowing how to work with a profiler (for example visualvm) – RobAu May 30 '17 at 18:54

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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