Knight's Tour with Heuristics

Question

When someone suggested that I solve Knight's Tour, I did so with heuristics and recursion.

It takes a lot of time to solve even a 8x8 board:

N-A1
N-C2
N-E1
...
N-E6
N-F4

Time used to solve: 5417011 nanoseconds

That seems quite a lot, but the most interesting part of my algorith is that it takes only six times the time for a 50x50 board:

N-A1
N-C2
N-E1
...
N-I32
N-K31

Time used to solve: 33299062 nanoseconds

Solver.java:

public class Solver {
        
    private static StringBuilder result = new StringBuilder();

    public static String getResult() {
        return result.toString();
    }

    public static boolean solve(int size) {
        KnightBoard board = new KnightBoard(size);
        Position start = new Position(1, 1);
        board.set(start, true);
        board.setKnightPosition(start);
        return solve(board);
    }

    private static boolean solve(KnightBoard board) {
        if (board.isAllBeenOn()) {
            return true;
        }
        Position[] possibleMoves = board.possibleMoves();
        if (possibleMoves.length == 0) {
            return false;
        }
        int index = 0;
        for (int i = 0; i < possibleMoves.length; i++) {
            int posMoves = board.possibleMoves(possibleMoves[i]).length;
            int indexPosMoves = board.possibleMoves(possibleMoves[index]).length;
            if (posMoves < indexPosMoves || (posMoves == indexPosMoves && board.getDegree(possibleMoves[i]) < board.getDegree(possibleMoves[index]))) {
                index = i;
            }
        }
        result.append(board.getCoord(board.getKnightLocation())).append("\n");
        board.setKnightPosition(possibleMoves[index]);
        board.set(possibleMoves[index], true);
        return solve(board);
    }

}

KnightBoard.java:

public class KnightBoard {

    private static int[][] posMoves = { { 2, 1 },
                                        { 2, -1 },
                                        { -2, 1 },
                                        { -2, -1 },
                                        { 1, 2 },
                                        { 1, -2 },
                                        { -1, 2 },
                                        { -1, -2 } };

    private int size;
    private boolean[][] beenOn;
    private Position knightPosition = new Position(1, 1);

    private int[][] degree;

    public KnightBoard(int size) {
        this.size = size;
        beenOn = new boolean[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                beenOn[i][j] = false;
            }
        }
        setDegree();
    }

    private void setDegree() {
        degree = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if ((i == 0 && j == 0) || (i == 0 && j == size - 1)
                        || (i == size - 1 && j == size - 1)
                        || (i == size - 1 && j == 0)) {
                    degree[i][j] = 2;
                } else if ((i == 1 && j == 0) || (i == 1 && j == size - 1)
                        || (i == size - 2 && j == size - 1)
                        || (i == size - 2 && j == 0) || (i == 0 && j == 1)
                        || (i == 0 && j == size - 2)
                        || (i == size - 1 && j == size - 2)
                        || (i == size - 1 && j == 1)) {
                    degree[i][j] = 3;
                } else if ((i == 1 && j == 1) || (i == 1 && j == size - 2)
                        || (i == size - 2 && j == size - 2)
                        || (i == size - 2 && j == 1)
                        || (i == 0 && (j >= 2 && j < 6))
                        || ((i >= 2 && i < 6) && j == 0)
                        || (i == size - 1 && (j >= 2 && j < 6))
                        || ((i >= 2 && i < 6) && j == size - 1)) {
                    degree[i][j] = 4;
                } else if ((i == 1 && (j >= 2 && j < 6))
                        || ((i >= 2 && i < 6) && j == 1)
                        || (i == size - 2 && (j >= 2 && j < 6))
                        || ((i >= 2 && i < 6) && j == size - 2)) {
                    degree[i][j] = 6;
                } else {
                    degree[i][j] = 8;
                }
            }
        }
    }
    
    public int getDegree(Position pos) {
        return degree[pos.getX() - 1][pos.getY() - 1];
    }

    public int getSize() {
        return size;
    }

    public void set(Position p, boolean beenOn) {
        this.beenOn[p.getX() - 1][p.getY() - 1] = beenOn;
    }

    public boolean get(Position p) {
        return this.beenOn[p.getX() - 1][p.getY() - 1];
    }

    public void setKnightPosition(Position p) {
        this.knightPosition = p;
    }

    public Position getKnightLocation() {
        return knightPosition;
    }

    public boolean isAllBeenOn() {
        for (boolean[] bool : beenOn) {
            for (boolean wasOn : bool) {
                if (!wasOn) {
                    return false;
                }
            }
        }
        return true;
    }

    public String getCoord(Position p) {
        return "N-" + toChar(p.getX()) + p.getY();
    }

    private String toChar(int x) {
        String result = "";
        while (true) {
            if (x > 26) {
                result += (char) ((x % 26) + 64);
                x /= 26;
            } else {
                result += (char) (x + 64);
                return result;
            }
        }
    }

    public Position[] possibleMoves() {
        List<Position> result = new LinkedList<Position>();
        for (int[] posMove : posMoves) {
            int x = knightPosition.getX() + posMove[0];
            int y = knightPosition.getY() + posMove[1];
            if (x > 0 && y > 0 && x <= size && y <= size) {
                Position possiblePos = new Position(x, y);
                if (!get(possiblePos)) {
                    result.add(possiblePos);
                }
            }
        }
        return result.toArray(new Position[result.size()]);
    }

    public Position[] possibleMoves(Position position) {
        List<Position> result = new LinkedList<Position>();
        for (int[] posMove : posMoves) {
            int x = position.getX() + posMove[0];
            int y = position.getY() + posMove[1];
            if (x > 0 && y > 0 && x <= size && y <= size) {
                Position possiblePos = new Position(x, y);
                if (!get(possiblePos)) {
                    result.add(possiblePos);
                }
            }
        }
        return result.toArray(new Position[result.size()]);
    }

}

Position.java:

public class Position {
    private int x;
    private int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

Main.java:

public class Main {
    public static void main(String[] args) {
        long time = System.nanoTime();
        int solve = 50;
        solve(solve);
        System.out.println(getResult() + "\nTime used to solve: "
                + (System.nanoTime() - time) + " nanoseconds\n");
    }
}

1. Is there a way to make this more efficient with smaller boards?
2. Can someone explain why the time required to solve are so close?

Any other general comments welcome.

Answer 1

Analysis

You've implemented a greedy algorithm using Warnsdorff's Rule. One consequence of using a greedy algorithm is that it takes \$O(n^2)\$ time for an \$n \times n\$ board. A second consequence is that recursion is unnecessary; just a loop will do. Recursion would fail to scale beyond a 100 × 100 board. (Note that solving the closed-loop knight's tour is quite a different problem.)

Somewhat surprisingly, the computation itself is fast enough that just printing the results takes a significant portion of the time. It would be more informative to exclude the printing routine from the benchmark. The test should also indicate whether a solution was found.

Since the computation is so "fast", it is worthwhile to forgo some performance optimizations in favour of readability and maintainability, which is what I'll do below.

Bugs

The output omits the last move, due to the way you call setKnightPosition(…) after the call to result.append(…).

The initialization done by KnightBoard.setDegree() is wrong (see below).

Position class

One-based coordinates are unnatural in a language in which array indexes start at 0.

The KnightBoard.getCoord(Position) method should be Position.toString() instead. (In place of the magic number 64, you should write 'A' - 1.)

Position objects should be immutable. You should also implement .equals() and .hashCode(), for reasons that will become apparent.

public class Position {
    private final int x;
    private final int y;

    /**
     * Position(0, 0) represents "A1"; Position(28, 33) is "AC34".
     */
    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public int hashCode() {
        return x ^ (y << 16);
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Position)) {
            return false;
        }
        Position p = (Position)other;
        return this.x == p.x && this.y == p.y;
    }

    @Override
    public String toString() {
        int x = this.x + 1;
        StringBuilder result = new StringBuilder();
        do {
            result.append((char)('A' + (--x % 26)));
            x /= 26;
        } while (x != 0);
        return result.append(this.y + 1).toString();
    }
}

Solver class

Solver is a poorly implemented singleton, in a situation where a singleton is inappropriate in the first place. The static result variable is essentially global state. That prevents you from elegantly solving multiple knight's tour problems in the same program, for example.

Accumulating the results in a StringBuilder is poor practice, as it degrades the data into stringified form. Reasonable interfaces would allow the caller to enumerate a sequence of Position — either as a Position[] array, a List<Position>, an Iterator<Position>, or Stream<Position>. I prefer Iterator<Position>.

KnightBoard class

I know what a "Knight" is, and what a "ChessBoard" is, but it's not clear to me what a "KnightBoard" is. If it's just a place to put code for solving the knight's tour problem, I would just combine it with Solver and call it KnightTour.

Iterating over all squares for isAllBeenOn() is cumbersome. I suggest using a Set<Position> to keep track of all visited positions. (Hence the need for Position to implement .equals() and .hashCode().)

.setDegree() and .getDegree() are awkwardly named — especially since the former sounds like it operates on a scalar quantity. More appropriate names would be .initDegreesOfFreedom() and .getDegreesOfFreedom().

The conditions in setDegree() look nasty. In fact, it's wrong, because you hard-coded 6 as a magic number instead of varying it according to the board size. There are a number of ways to fix that, the most elegant being to reuse the possibleMoves() routine. I think that this bug demonstrates the wisdom of preferring maintainability over performance — and the performance impact is minimal anyway.

Algorithm

This line in Solver.solve() looks particularly nasty:

if (posMoves < indexPosMoves || (posMoves == indexPosMoves && board.getDegree(possibleMoves[i]) < board.getDegree(possibleMoves[index]))) {

I think it pays to reformulate the loop in a way that maximizes clarity. What you want to do is favour possible moves with fewer exit paths, so the code should express that.

KnightBoard.possibleMoves() constructs a List<Position>, then converts its result to a Position[] array. If you've already paid the price for constructing a List, then it makes little sense to degrade the object into a "dumber" array.

Suggested implementation

import java.util.*;

public class KnightTour implements Iterable<Position> {
    /**
     * Comparator that puts positions with fewer exits first, breaking ties in
     * favor of smaller degree of freedom first.
     */
    private Comparator<Position> hardestPositionsFirstWithLookahead1 = new Comparator<Position>() {
        @Override
        public int compare(Position a, Position b) {
            int aPossibleMoves = KnightTour.this.possibleMoves(a).size();
            int bPossibleMoves = KnightTour.this.possibleMoves(b).size();
            if (aPossibleMoves != bPossibleMoves) {
                return aPossibleMoves - bPossibleMoves;
            } else {
                return KnightTour.this.getDegreesOfFreedom(a) - KnightTour.this.getDegreesOfFreedom(b);
            }
        }
    };

    private static final int[][] KNIGHT_MOVES = {
        { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 },
        { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }
    };
    private final int[][] degreesOfFreedom;
    private Set<Position> path;         // LinkedHashSet preserves insertion order

    /**
     * Knight's tour for an 8x8 board starting at A1.
     */
    public KnightTour() {
        this(8);
    }

    /**
     * Knight's tour starting at A1.
     */
    public KnightTour(int boardSize) {
        this(boardSize, new Position(0, 0));
    }

    public KnightTour(int boardSize, Position start) {
        this.degreesOfFreedom = initDegreesOfFreedom(boardSize);
        this.path = new LinkedHashSet<Position>(boardSize * boardSize);
        if (this.solve(start)) {
            // Prevent Iterator.remove()
            this.path = Collections.unmodifiableSet(this.path);
        } else {
            // Indicate that no moves are possible
            this.path.clear();
        }
    }

    @Override
    public Iterator<Position> iterator() {
        return this.path.iterator();
    }

    public int getSize() {
        return this.degreesOfFreedom.length;
    }

    private int getDegreesOfFreedom(Position p) {
        return this.degreesOfFreedom[p.getX()][p.getY()];
    }

    private static int[][] initDegreesOfFreedom(int boardSize) {
        int[][] board = new int[boardSize][boardSize];
        // Most squares allow full freedom of motion
        for (int[] row : board) {
            Arrays.fill(row, KNIGHT_MOVES.length);
        }
        // Reduced freedom of motion in the two ranks and files near the edges
        for (int x = 0; x < board.length; x++) {
            for (int y : new int[] { 0, 1, board.length - 2, board.length - 1 }) {
                board[x][y] = board[y][x] =
                    possibleMoves(new Position(x, y), boardSize, Collections.<Position>emptySet()).size();
            }
        }
        return board;
    }

    private boolean solve(Position p) {
        this.path.add(p);
        while (this.path.size() < this.getSize() * this.getSize()) {
            List<Position> possibleMoves = possibleMoves(p);
            if (possibleMoves.isEmpty()) {
                return false;
            }
            Collections.sort(possibleMoves, this.hardestPositionsFirstWithLookahead1);
            this.path.add(p = possibleMoves.get(0));
        }
        return true;
    }

    private List<Position> possibleMoves(Position position) {
        return possibleMoves(position, this.getSize(), this.path);
    }

    private static List<Position> possibleMoves(Position position, int boardSize, Set<Position> prohibited) {
        List<Position> result = new ArrayList<Position>(KNIGHT_MOVES.length);
        for (int[] posMove : KNIGHT_MOVES) {
            int x = position.getX() + posMove[0];
            int y = position.getY() + posMove[1];
            if (x >= 0 && y >= 0 && x < boardSize && y < boardSize) {
                Position possiblePos = new Position(x, y);
                if (!prohibited.contains(possiblePos)) {
                    result.add(possiblePos);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        long time = System.nanoTime();
        StringBuilder sb = new StringBuilder();
        for (Position p : new KnightTour(Integer.parseInt(args[0]))) {
            sb.append("N-").append(p).append('\n');
        }
        System.out.print(sb);
        System.err.printf("\nTime used to solve: %d nanoseconds\n", System.nanoTime() - time);
    }
}

Answer 2

the most interesting part of my algorith is that it takes only six times the time for a 50x50 board

This is a mistiming; you're forgetting that Java has a JIT. JITing the code swamps the algorithm's cost. Allowing the JVM to warm up by running

for (int i = 0; i < 100; i++) {
    Solver.solve(solve);
}

gives me timings of 144700ns for and 8x8 and 5636751ns for a 50x50. That's a factor of ~39, which is about what you'd expect.

More strictly on the code review side of things, the first thing that grated at me was the use of the static result global; there's no need for it. solve(KnightBoard) can just pass a StringBuilder down using its arguments, which can get initialized in solve(int). If you really want to use a global-esque variable, use a nonstatic member variable.

But solve is trivially recursive so you can just make it into a loop. This simplifies setup.

Your

if (posMoves < indexPosMoves || (posMoves == indexPosMoves && board.getDegree(possibleMoves[i]) < board.getDegree(possibleMoves[index]))) {

should be wrapped; the line is too long.

It's very strange you build the result with StringBuilder; normally I'd expect one to return a List of some kind representing the path: a list of Positions perhaps? It doesn't seem very general to do it any other way.

You call KnightBoard.possibleMoves a lot; surely the simpler way than generating all of them again is to have the board represented as a graph which is pruned as it is traversed. Each cell in the grid would be a count of how many of its surrounding positions can be moved to, or -1 if it itself cannot be moved to. Since you only need to store up to a small maximum for each cell, this wouldn't even need to cost more memory.

Comments about what getDegree does would be advisable; as it stands it's completely opaque to someone like me.