Knight's Tour with Heuristics

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

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.

StackExchange Code Review Q#75585, answer score: 4