Optimizing Recursion in Knight's Tour

Question

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;
}

}

Answer 1

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();
    }
}