How to determine how many moves it takes a knight to get anywhere on the board in java

Question

I am trying to create a program that when given the location of a chess knight and the destination, all marked in chess notation, to return the number of moves it takes the knight to get from the location the destination. I have tried before using the algorithm to calculate every single possibility on a list, but it is very slow and kind of has problems. Here is my code:

private static int translateChessNotation(String chess) {
        int returned = 8 * (Integer.valueOf(String.valueOf(chess.charAt(1)))- 1);
        return returned + (convertAlphabet(chess.charAt(0))); // File
}

public static int knight(String start, String finish) {
    int knightPosition = translateChessNotation(start), end = translateChessNotation(finish), i = 0;
    ArrayList<Integer> currentPossibleKnightPositions = new ArrayList<>();
    currentPossibleKnightPositions.add(knightPosition);
    for (; i < 8; i++) {
        ArrayList<Integer> newList = new ArrayList<>();
        for (int position : currentPossibleKnightPositions) {
            newList.add(position + 17);
            newList.add(position + 15);
            newList.add(position + 10);
            newList.add(position + 6);
            newList.add(position - 6);
            newList.add(position - 10);
            newList.add(position - 15);
            newList.add(position - 17);
        }
        ArrayList<Integer> removed = new ArrayList<>();
        for (int j : newList) {if (j < 1 || j > 64) {removed.add(j);}}
        newList.removeAll(removed);
        currentPossibleKnightPositions.clear();
        currentPossibleKnightPositions.addAll(newList);
        for (int n : currentPossibleKnightPositions) {
            if (n == end) {return i + 1;}
        }
    }
    return -1;
}

Thanks a lot if you help!

Answer 1

I've replaced the Chessboard Array in the previous Posting with a long.
(with 64 bits, its just large enough to represent the board)

The new Version is significantly faster.

Depending on starting-coordinates, a solution takes anywhere between 1 Minute & 12 Hours...
(I've put a couple of the faster ones first)

This example is designed to show the basics. There are various Mathematical Methods (see Wikipedia) to optimise it, but they make the Solution more complex.

A couple of Takeaways:
- use Primitives (byte, short, int, long,...) if you can: they are very fast
- avoid Objects like ArrayList when using Brute-Force: they are very slow
- use recursion: it saves & restores State for you. It may cost a little, but it makes life so much easier
- use final whenever you can: it's no faster, but aids understanding

Hope you like it. :-)

I've honed this thing down now. It is massively faster than the original (which was no slouch!), uses the Warnsdorff algorithm & can solve multiple starting positions, running on all available Threads simultaneously.

Most of the work is getting the Data Structures right & Initialisation.
The recursive nextMoveToXY solver Method itself is trivially simple.

The Warnsdorff Version:

import java.time.Instant;
import java.util.Arrays;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.function.IntConsumer;
import java.util.stream.IntStream;

public class KnightsTourWarnsdorff {

    private interface IntIntConsumer {
        void accept(int t, int u);
    }

    private static final int MAX_INSTANT_TO_STRING_LENGTH = "2020-12-31T23:59:59.123456Z".length();

    private static final int SIZE_X   = 8;
    private static final int SIZE_Y   = 8;
    private static final int SIZE_X_Y = SIZE_X * SIZE_Y;
    /**/    static {   check_SIZE_X_Y_withinCapacity();}

    /**
     * Do this in a Method (we don't want to mark the Class with SuppressWarnings)
     */
    @SuppressWarnings("unused")
    private static void check_SIZE_X_Y_withinCapacity() {
        if (SIZE_X_Y > Long.SIZE) {
            throw new UnsupportedOperationException("Number of squares on board exceeds capacity of long Solution");
        }
    }

    /**
     * Returns the unique offset corresponding to a Move or our position on the Board.
     */
    private static int  getDeltaXY(final int deltaX, final int deltaY) {
        return deltaX + deltaY * SIZE_X;  /* Yes, SIZE_X ! */
    }

    /**
     * Returns a long with a single bit set, corresponding to our position on the Board.
     */
    private static long getXYmaskBit(final int x, final int y) {
        return 1L << (63 - getDeltaXY(x, y));
    }

    private static void walkBoard(final IntIntConsumer doXY) {
        walkBoard(null, doXY, null);
    }
    private static void walkBoard(final IntConsumer doRowStart, final IntIntConsumer doXY, final Runnable doRowEnd) {

        IntStream    .range(0, SIZE_Y).forEach(y -> {if (doRowStart != null) {doRowStart.accept(  y);}
            IntStream.range(0, SIZE_X).forEach(x -> {if (doXY       != null) {doXY      .accept(x,y);}
            });                                      if (doRowEnd   != null) {doRowEnd  .run   (   );}
        });
    }

    private static String toBinary(final long value) {
        return leftPad(Long.SIZE, Long.toBinaryString(value)).replace('0', '_');
    }
    private static String leftPad (final int  paddedLength, final String value) {

        final int                          padCount = Math.max(0, paddedLength - value.length());
        final char[]                       pad      = new char[padCount]; 
        Arrays.fill                       (pad, '0');
        return              String.valueOf(pad).concat(value);
    }
    private static String rightPad (final int  paddedLength, final String value) {

        final int                          padCount = Math.max(0, paddedLength - value.length());
        final char[]                       pad      = new char[padCount]; 
        Arrays.fill                       (pad, '0');
        return value.concat(String.valueOf(pad));
    }
    private static String header () {
        return rightPad (MAX_INSTANT_TO_STRING_LENGTH, Instant.now().toString()) + " " + Thread.currentThread().getName() + " ";
    }

    /**
     * Square on Board not only knows its x/y location, but also its position as an xyMask<br>
     * (for checking whether a square is occupied & marking as occupied).<br>
     * <br>
     * It knows all possible Moves from this Square within the Board<br>
     * (thus obviating the need to check whether we're still on the Board).<br>
     * <br>
     * Each Specific Move contains a reference to the Target Square, which in turn...<br>
     * (these 2 measures speed up Navigation massively)
     */
    private static final class Square {

        private           final int    x;
        private           final int     y;
        /**
         * Used to mark the Square as occupied on the Board
         */
        private           final long   xyMask;
        /**
         * All possible Moves from this Square.<br>
         * (initially all null: filled after all Squares have been instantiated)
         */
        private           final Move[] targetMove;

        private Square(final int x, final int y) {

            this.x       =              x;
            this. y      =                 y;
            this.xyMask  = getXYmaskBit(x, y);

            this.targetMove = KNIGHT_MOVE_MAP.values().stream().filter(move -> {

                final int  newX =  x + move.deltaX;
                final int  newY =  y + move.deltaY;

                return     newX >= 0  &&  newX < SIZE_X
                        && newY >= 0  &&  newY < SIZE_Y;

            }).toArray(Move[]::new);
        }
    }

    /**
     * Either a Generic or a Specific Move
     */
    private static final class Move {

        private final int    deltaX;
        private final int    deltaY;
        private final int    deltaXY;
        private final Square target;

        /**
         * Create a Generic Move
         */
        private Move(final int deltaX, final int deltaY) {
            this.deltaX  = deltaX;
            this.deltaY  = deltaY;
            this.deltaXY = getDeltaXY(deltaX, deltaY);
            this.target  = null;
        }

        /**
         * Create a Move to a specific Target Square
         */
        private Move(final Move genericMove, final Square target) {
            this.deltaX  = genericMove.deltaX;
            this.deltaY  = genericMove.deltaY;
            this.deltaXY = genericMove.deltaXY;
            this.target  = target;
        }
    }

    @SuppressWarnings("serial")
    private static final class KnightMoveSolvedException extends RuntimeException {

        private final int[] solution;

        private KnightMoveSolvedException(final int moveCount, final int[] solution) {
            /*
             * Trim the solution array down to the number of moves...
             * (for those performing a partial walk)
             */
            this.solution = Arrays.stream(solution).limit(moveCount).toArray();

            synchronized (KnightMoveSolvedException.class) { // One Thread (= Solution) at a time please!
                final int  solution0   = this.solution[0];
                final Move initialMove = BOARD_MAP.get(solution0);
                final int  initialX    = initialMove.deltaX;
                final int  initialY    = initialMove.deltaY;

                System.out.println(header() + "Solution found for....: x/y: " + initialX + "/" + initialY + "  \t" + toBinary(0L) + "  \tlength=" + this.solution.length + "  \t" + solution0);
                this.printSolutionDetail();
            }
        }
        private void printSolutionDetail() {

            int  x     = 0;
            int  y     = 0;
            long board = 0;

            for (int i=0; i < this.solution.length; i++) {

                final int  positionOrMove = this.solution[i];
                final Move move           = i == 0  ?  BOARD_MAP.get(positionOrMove)  :  KNIGHT_MOVE_MAP.get(positionOrMove);
                /**/       x              = i == 0  ?  move.deltaX                    :  x + move.deltaX;
                /**/       y              = i == 0  ?  move.deltaY                    :  y + move.deltaY;

                board |= getXYmaskBit(x, y);

                System.out.println(header() + "Solution walk.........: x/y: " + x + "/" + y + "  \t" + toBinary(board) + "  \t" + move.deltaX + "\t" + move.deltaY + "\t" + positionOrMove);
            }
        }
    }

    private static final Map<Integer, Move> KNIGHT_MOVE_MAP;
    /**/    static {
        final Map<Integer, Move> Knight_Move_Map = new TreeMap<>();

        IntStream.of(2, -2).forEach(deltaX ->
        IntStream.of(1, -1).forEach(deltaY -> {
            /*
             * Mirror the 4 combinations above to get all 8 possible Knight moves...
             */
            {final Move move = new Move(deltaX, deltaY);  Knight_Move_Map.put(move.deltaXY, move);}
            {final Move move = new Move(deltaY, deltaX);  Knight_Move_Map.put(move.deltaXY, move);}
        }));
        KNIGHT_MOVE_MAP = Collections.unmodifiableMap(Knight_Move_Map);
    }

    private static final Map<Integer, Move> BOARD_MAP;
    /**/    static {
        final Map<Integer, Move> Board_Map = new TreeMap<>();

        walkBoard((x,y) -> {
            final Move move = new Move(x, y);
            Board_Map.put(move.deltaXY, move);
        });

        BOARD_MAP = Collections.unmodifiableMap(Board_Map);
    }

    private static final Square[][] BOARD = new Square[SIZE_X] [SIZE_Y];
    /**/    static {
        /*
         * Fill the Board with Squares...
         */
        walkBoard(   (x,y) -> BOARD[x][y] = new Square(x, y));

        /**/                                                       System.out.println("Onward Target Count:");
        walkBoard(   (  y) -> {                                    System.out.print  (                       y + " :  ");},
                /**/ (x,y) -> {final Square square = BOARD[x][y];  System.out.print  (square.targetMove.length +   "  ");},
                /**/ (   ) -> {                                    System.out.println()                                 ;} );
        /*
         * So far the Target Moves array is filled with nulls. We MUST fill it...
         */
        Arrays.stream(BOARD).flatMap(Arrays::stream).forEach(square -> {

            final Move[] targetsSortedByOnwardPointCount = Arrays
                    .stream(square.targetMove)
                    .sorted((moveA, moveB) -> {
                        /*
                         * We use the Warnsdorff algorithm to sort it by the number of Onward Targets...
                         */
                        final Square targetA = BOARD[square.x + moveA.deltaX] [square.y + moveA.deltaY];
                        final Square targetB = BOARD[square.x + moveB.deltaX] [square.y + moveB.deltaY];

                        return Integer.compare(
                                targetA.targetMove.length,   // number of Onward Targets
                                targetB.targetMove.length);  // number of Onward Targets
                        })
                    .map(move -> new Move(move, BOARD[square.x + move.deltaX] [square.y + move.deltaY]))
                    .toArray(Move[]::new);
            /*
             * Original & sorted arrays should be the same length if we got it right,
             * so take max. length as a precaution to force an IndexOutOfBoundsException if we didn't...
             */
            final int copyLength = Math.max(square.targetMove.length, targetsSortedByOnwardPointCount.length);
            /*
             * Overwrite the original Moves with the sorted version...
             */
            System.arraycopy(targetsSortedByOnwardPointCount, 0, square.targetMove, 0, copyLength);
        });
    }

    private final int[] SOLUTION = new int[SIZE_X_Y];

    private        void solve(final int initialX, final int initialY) {

        final long initialBoard = getXYmaskBit(initialX, initialY);

        System.out.println(header() + "Solve starting at.....: x/y: " + initialX +"/" + initialY + "\t" + toBinary(initialBoard));

        try {
            SOLUTION    [0] =  getDeltaXY(initialX, initialY);  // First Entry contains Starting-Point
            nextMoveToXY(0,         BOARD[initialX][initialY], initialBoard);
        }
        catch (final KnightMoveSolvedException justIgnore_WereDone) {}
    }

    private        void nextMoveToXY(int moveCount, final Square square, final long board) {

        moveCount++;

        if (moveCount >= SIZE_X_Y) {
            final KnightMoveSolvedException solution = new KnightMoveSolvedException(moveCount, SOLUTION);

//          return;  // (Back up & keep looking for next solution)
            /*
             * If 1 solution is enough, just throw the Exception...
             */
            throw solution;
        }

        for (final Move move : square.targetMove) {
            /*
             * Is Target Square vacant? (i.e. Mask Bit not set)...
             */
            if ((board & move.target.xyMask) == 0) {
                /*
                 * Yes: try next move recursively with new Position & Board...
                 */
                SOLUTION    [moveCount] = move.deltaXY;

                nextMoveToXY(moveCount, move.target, board | move.target.xyMask /* Set Mask Bit on new Board */);
            }
        }
    }

    public static void main(final String[] args) throws Exception {

        final ExecutorService pool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

        /*
         * We can handle rectangular boards, but for square boards the following holds:
         * we only need to solve for 1/8 of the board (a triangle)...
         * (the remaining 7/8 are either Mirrors or Rotations of the 1/8)
         */
        IntStream    .range(0, SIZE_X / 2).forEach(x -> {
            IntStream.range(0, x + 1     ).forEach(y -> {
                pool.submit(() -> {
                    try { TimeUnit.SECONDS.sleep(1); } catch (final InterruptedException e) {}
                    /*
                     * (Sleep very briefly, so our Thread won't start before the Output below has finished)
                     */
                    new KnightsTourWarnsdorff().solve(x, y);
                });
                System.out.print("x=" + x + " y=" + y + "\t");
            });
            System.out.println();
        });
        pool.shutdown();
    }       
}

Original Version:

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

public class KnightsTour {

    @SuppressWarnings("serial")
    private static final class KnightMoveSolvedException extends RuntimeException {

        private final int[][] solution;

        private KnightMoveSolvedException(final int[][] solution) {
            this.solution = deepPrimitive2DArrayClone  (solution);
        }
    }

    private static final int      SIZE_X   = 8;
    private static final int      SIZE_Y   = 8;
    private static final int      SIZE_X_Y = SIZE_X * SIZE_Y;
    private static final int[][]  SOLUTION = new int[SIZE_X_Y][];
    private static final int      INDEX_X  = 0;
    private static final int      INDEX_Y  = 1;


    private static final int      KNIGHT_MOVES_LENGTH = 8;
    private static final int [][] KNIGHT_MOVES        = new int[KNIGHT_MOVES_LENGTH][];
    /**/    static {
        checkLongSolutionCapacity();

        final AtomicInteger moveIndex = new AtomicInteger();

        IntStream.of(2, -2).forEach(deltaX ->
        IntStream.of(1, -1).forEach(deltaY -> {
            /*
             * Mirror the 4 combinations above to get all 8 possible Knight moves...
             */
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaX, deltaY};
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaY, deltaX};
        }));
    }

    @SuppressWarnings("unused")
    private static void checkLongSolutionCapacity() {
        if (SIZE_X_Y > Long.SIZE) {
            throw new UnsupportedOperationException("Number of squares on board exceeds capacity of long Solution");
        }
    }

    private static long getXYmaskBit(final int x, final int y) {
        return Long.MIN_VALUE >>> (x + y * SIZE_X /* Yes, SIZE-X ! */);
    }

    public  static void solve(final int initialX, final int initialY) {

        final long initialBoard = getXYmaskBit(initialX, initialY);

        System.out.println("Solve starting at X/Y.: " + initialX +"/" + initialY + "\t" + toBinary(initialBoard));

        try {
            SOLUTION    [0] =  new int[] {initialX, initialY};  // First Entry contains Starting-Point
            nextMoveToXY(0,               initialX, initialY, initialBoard);
        }
        catch (final KnightMoveSolvedException e) {
            System.out.println("One possible solution.: " + e.solution);
        }
    }
    private static void nextMoveToXY(int moveCount, final int x, final int y, final long board) {

        moveCount++;

        if (moveCount >= SIZE_X_Y) {
            System.out.println("Solved!...............: count=" + moveCount);
            /*
             * Print the answer or remember it somewhere...
             */
            final     int  initialX  = SOLUTION[0][INDEX_X];
            final     int  initialY  = SOLUTION[0][INDEX_Y];

            for(final int[] move     : SOLUTION) {
                final int  solutionX = move[INDEX_X];
                final int  solutionY = move[INDEX_Y];

                System.out.println("Move (starting at X/Y): " + initialX +"/" + initialY + "\t" + toBinary(board) + "\t" + solutionX + "\t" + solutionY);
            }
//          return;  // (Back up & keep looking for next solution)
            /*
             * If 1 solution is enough, just throw the Exception...
             */
            throw new KnightMoveSolvedException(SOLUTION);
        }

        for(final int[] move   : KNIGHT_MOVES) {
            final int   deltaX = move[INDEX_X];  final int newX = x + deltaX;  if (newX < 0 || newX >= SIZE_X) {continue;}
            final int   deltaY = move[INDEX_Y];  final int newY = y + deltaY;  if (newY < 0 || newY >= SIZE_Y) {continue;}
            /*
             * ok: Checks above mean we're on the board, so lets find the new Position Mask...
             */
            final long   newXYmaskBit = getXYmaskBit(newX, newY);
            /*
             * Is Target Square vacant (= Mask Bit not set)?...
             */
            if ((board & newXYmaskBit) == 0) {
                /*
                 * Yes: try next move recursively with new Position & Board...
                 */
                SOLUTION    [moveCount] = move;

                nextMoveToXY(moveCount, newX, newY, board | newXYmaskBit /* Set Mask Bit on new Board */);
            }
        }
    }

    public  static String toHex   (final int  value) {
        return leftPad(Integer.BYTES * 2, Integer.toHexString   (value));
    }
    public  static String toHex   (final long value) {
        return leftPad(Long   .BYTES * 2, Long   .toHexString   (value));
    }
    public  static String toBinary(final int  value) {
        return leftPad(Integer.SIZE,      Integer.toBinaryString(value));
    }
    public  static String toBinary(final long value) {
        return leftPad(Long   .SIZE,      Long   .toBinaryString(value));
    }
    private static String leftPad (final int  paddedLength, final String binaryOrHex) {

        final char[]          lead = new char[paddedLength - binaryOrHex.length()]; 
        Arrays.fill          (lead, '0');
        return String.valueOf(lead).concat(binaryOrHex).replace('0', '_');
    }

    /**
     * {@link Object#clone()} can create a Deep Clone of a 1D array of Primitives
     * but with 2D will only provide a Shallow Copy (meaning if the content of source
     * changes, the content of clone will change!!) so we have to wrap 2D by hand...
     */
    private static int[][] deepPrimitive2DArrayClone(final int[][] source) {

        final int[][] clone = new int[source.length][];
        /**/  int     cix   = 0;

        for (final int[]   col : source) {
            clone[cix++] = col.clone();  // (ok: 1D, so Deep Clone)
        }
        return clone;
    }

    public static void main(final String[] args) throws Exception {

        solve(0, 1);  // Fast!: 2 Minutes
        solve(0, 3);  // Fast!: 1 Minute

        IntStream.range(0, SIZE_X).forEach(x ->
        IntStream.range(0, SIZE_Y).forEach(y -> {
            solve(x, y);
        }));
    }
}

Answer 2

I got this answer online. Hope this helps to the others who have the same question!

 public static int knight(String...pos) {
        int[][] ab=Stream.of(pos).map(s->new int[]{"abcdefgh".indexOf(s.charAt(0)),s.charAt(1)-48}).toArray(int[][]::new);
        int[] dxy=IntStream.range(0,2).map(i->Math.abs(ab[0][i]-ab[1][i])).sorted().toArray();
        if(dxy[0]==0&&dxy[1]==1) return 3;
        if(dxy[0]==2&&dxy[1]==2||dxy[0]==1&&dxy[1]==1&&(pos[0]+pos[1]).matches(".*?(a1|h1|a8|h8).*")) return 4;
        int delta=dxy[1]-dxy[0];
        return delta-2*(int)Math.floor(1.0*(delta-dxy[0])/(dxy[0]>delta?3:4));
    }

Answer 3

Here's a little Proggy to solve the so-called Knights-Tour problem, visiting all squares on the board starting from a particular location, so you could adapt that to set a particular to-position as your end-condition.

Its just Brute-Force, trying all possible combinations & takes about 50 minutes to find each full Knights-Tour solution.

If that helps, I'd be honoured to receive your vote.

import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

public class KnightMove {

    @SuppressWarnings("serial")
    private static final class KnightMoveSolvedException extends RuntimeException {

        private final byte[][] solution;

        private KnightMoveSolvedException(final byte[][] solution) {
            this.solution = solution;
        }
    }

    private static final int      SIZE_X       = 8;
    private static final int      SIZE_Y       = 8;
    private static final int      SIZE_X_Y     = SIZE_X * SIZE_Y; // Max 127! (=0x7F)

    private static final int [][] KNIGHT_MOVES = new int[8][];
    /**/    static {     
        final AtomicInteger moveIndex = new AtomicInteger();

        IntStream.of(2, -2).forEach(deltaX ->
        IntStream.of(1, -1).forEach(deltaY -> {
            /*
             * Mirror the 4 combinations above to get all 8 possible Knight moves...
             */
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaX, deltaY};
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaY, deltaX};  
        }));
    }

    private static void nextMoveToXY(int moveCount, final int x, final int y, final byte[][] board) {
        moveCount++;

        board[x][y] = (byte) moveCount;

        if (moveCount >= SIZE_X_Y) {

            System.out.println("Solved!.....: count=" + moveCount);

            for (    final byte[] column : board ) {
                for (final byte   square : column) {
                    System.out.print(square + "\t");
                }
                System.out.println();
            }
            return;  // (Back up & keep looking for next solution)
            /*
             * If 1 solution is enough, just throw the Exception...
             */
//          throw new KnightMoveSolvedException(board);
        }

        for (final int[] knightMove : KNIGHT_MOVES) {

            final int newX = x + knightMove[0];  if (newX < 0 || newX >= SIZE_X) {continue;}
            final int newY = y + knightMove[1];  if (newY < 0 || newY >= SIZE_Y) {continue;}

            if (board[newX][newY] == 0) {
                /*
                 * Target Square is vacant, so try this move recursively...
                 */
                nextMoveToXY(moveCount, newX, newY, deepPrimitive2DArrayClone(board));
            }
        }
    }

    /**
     * {@link Object#clone()} can create a Deep Clone of a 1D array of Primitives
     * but will <b>not</b> deliver the desired result with 2D,
     * so we have to wrap the rest by hand...
     */
    private static byte[][] deepPrimitive2DArrayClone(final byte[][] source) {

        final byte[][] clone = new byte[source.length][];
        /**/  int      cix   = 0;

        for (final byte[]  col : source) {
            clone[cix++] = col.clone();
        }
        return clone;
    }

    public static void main(final String[] args) throws Exception {

        IntStream.range(0, SIZE_X).forEach(x ->
        IntStream.range(0, SIZE_Y).forEach(y -> {
            try {
                System.out.println("Solve starting at X/Y.: " + x +"/" + y);

                nextMoveToXY(0, x, y, new byte[SIZE_X][SIZE_Y]);
            }
            catch (final KnightMoveSolvedException e) {
                System.out.println(e.solution);
            }
        }));
    }
}