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

chess knight minimum moves python
chess knight move algorithm
knight's tour solution 8x8
knight moves java
time complexity of knight tour problem
knight's tour solution 8x8 c++
knight's tour solution 8x8 java
knight move python

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!

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

Knight's tour problem using backtracking and its analysis, Learn about the knight's tour problem and its analysis using backtracking. and Knight's tour, there are approaches which take lesser time than backtracking, we have to make the knight cover all the cells of the board and it can move to a the second in which the knight finishes anywhere else, this is called open tour. A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open.

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

Chess Knight Problem, Given a chess board, find the shortest distance (minimum number of steps) A knight can move in 8 possible directions from a given cell as illustrated in below figure – array that stores the relative position of Knight movement from any location. The d factor that we are using to optimize the path is also taking care of the� Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out the minimum steps a Knight will take to reach the target position. Examples: In above diagram Knight takes 3 step to reach from (4, 5) to (1, 1) (4, 5) -> (5, 3) -> (3, 2) -> (1, 1) as shown in diagram

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

Print all Possible Knight's Tours in a chessboard, Given a chess board, print all sequences of moves of a knight on a square in the chessboard and recursively explore all eight paths possible to check if they To make sure that the path is simple and doesn't contain any cycles, we keep track If we start from somewhere middle, the Knight can go to 8 different directions. The diagram shows how many moves it'll take a knight to get from its current square to any square on the board. The pattern is surprisingly easy to remember. From the wiki page: In the diagram, the numbers represent how many moves it takes for a knight to reach each square on the chess board from its location on the f5 square.

Knight's tour, Or players can agree upon grenading any non-burned square that is not occupied anywhere on the board. Players can also choose to decide if grenading should� Given two different cells of the chessboard, determine whether a knight can go from the first cell to the second in one move. The program receives the input of four numbers from 1 to 8, each specifying the column and row number, first two - for the first cell, and then the last two - for the second cell.

Minimum steps to reach target by a Knight, We need to find out the minimum steps a Knight will take to reach the target position. If reachable position is not already visited and is inside the board, we push C++; Java; Python3; C# specific cell in minimum moves by Knight Minimum steps to reach any of the boundary edges of a matrix | Set-2� We can observe that knight on a chessboard moves either: 1. Two moves horizontal and one move vertical 2. Two moves vertical and one move horizontal. The idea is to store all possible moves of knight and then count number of valid moves. A move will be invalid if: 1. A block is already occupied by another piece. 2. Move is out of chessboard.

Possible moves of knight, Find number of possible moves where knight can be moved on a chessboard Assume that board consist of all pieces of same color, i.e., there are no C++; Java; Python3; C#; PHP Driver program to check findPossibleMoves() Please write to us at contribute@geeksforgeeks.org to report any issue� Basically, it deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location. I've never dealt with shortest-path-esque things, and I don't even know where to start.

Comments
  • The basic algorithm for "shortest path" is Breadth-first search. Dijkstra's algorithm is faster and A* is likely to be the fastest
  • Welcome to Stack Overflow. This is a classic problem. Are your sure that you search didn’t turn up anything?
  • yep. really, my problem is pretty specific.
  • Sorry, I don’t understand your algorithm, so can’t suggest much. I suspect that your way of finding the squares the knight can move to is incorrect, though. Not from every square can the knight move to 8 other squares.
  • I know, my algorithm is generating the 8 locations, getting all the possibilities from those 8 directions, an so on. See what I mean?