Shortest Knight Path in Java

The challenge

Given two different positions on a chess board, find the least number of moves it would take a knight to get from one to the other. The positions will be passed as two arguments in algebraic notation. For example, knight("a3", "b5") should return 1.

The knight is not allowed to move off the board. The board is 8×8.

For information on knight moves, see https://en.wikipedia.org/wiki/Knight_%28chess%29

For information on algebraic notation, see https://en.wikipedia.org/wiki/Algebraic_notation_%28chess%29

The solution in Java code

Option 1:

import java.util.*;

public class Chess {
    private static final int BOARD_SIZE = 8;
    private static final String ORIGIN = "a1";
    private static int[][] KNIGHT_MOVES = new int[8][];
    static {
        KNIGHT_MOVES[0] = new int[] { 1, 2 };
        KNIGHT_MOVES[1] = new int[] { KNIGHT_MOVES[0][1], KNIGHT_MOVES[0][0] };
        for (int i = 0; i < 2; i++)
            KNIGHT_MOVES[i + 2] = new int[] { -KNIGHT_MOVES[i][0], KNIGHT_MOVES[i][1] };
        for (int i = 0; i < 4; i++)
            KNIGHT_MOVES[i + 4] = new int[] { KNIGHT_MOVES[i][0], -KNIGHT_MOVES[i][1] };
    }

    private static int[] coordFromString(String s) {
        if (s.length() != 2)
            throw new IllegalArgumentException("Invalid position: " + s);
        int[] result = new int[2];
        for (int i = 0; i < 2; i++) {
            int c = s.charAt(i) - ORIGIN.charAt(i);
            if (c < 0 || c >= BOARD_SIZE)
                throw new IllegalArgumentException("Invalid position: " + s);
            result[i] = c;
        }
        return result;
    }

    public static int knight(String start, String finish) {
        int[] startPos = coordFromString(start);
        int[] finishPos = coordFromString(finish);
        if (startPos[0] == finishPos[0] && startPos[1] == finishPos[1])
            return 0;
        boolean[][] explored = new boolean[BOARD_SIZE][BOARD_SIZE];
        explored[startPos[0]][startPos[1]] = true;
        List<int[]> tier = Collections.singletonList(startPos);
        int moveCount = 0;
        while (true) {
            moveCount++;
            List<int[]> nextTier = new ArrayList<>();
            for (int[] pos : tier)
                for (int[] move : KNIGHT_MOVES) {
                    int x = pos[0] + move[0];
                    if (x < 0 || x >= BOARD_SIZE)
                        continue;
                    int y = pos[1] + move[1];
                    if (y < 0 || y >= BOARD_SIZE)
                        continue;
                    if (explored[x][y])
                        continue;
                    if (x == finishPos[0] && y == finishPos[1])
                        return moveCount;
                    explored[x][y] = true;
                    nextTier.add(new int[] { x, y });
                }
            tier = nextTier;
        }
    }
}

Option 2:

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Chess {
    private static final int[][] MOVES = {
            {-2, -1},
            {-2, 1},
            {2, -1},
            {2, 1},
            {-1, -2},
            {-1, 2},
            {1, -2},
            {1, 2}
    };
    private static final int[] MOVE_END_ROUND = {99, 99};

    public static int knight(String start, String finish) {
        final int[] s = {start.charAt(0) - 'a', Character.getNumericValue(start.charAt(1)) - 1};
        final int[] f = {finish.charAt(0) - 'a', Character.getNumericValue(finish.charAt(1)) - 1};

        final Queue<int[]> queue = new ArrayDeque<>();
        final Queue<int[]> queue2 = new ArrayDeque<>();
        queue.add(s);
        queue.add(MOVE_END_ROUND);
        int round = 0;

        while (true) {
            while (!queue.isEmpty()) {
                final int[] pos = queue.poll();
                if (Arrays.equals(pos, f)) return round;
                if (Arrays.equals(pos, MOVE_END_ROUND)) {
                    round++;
                    continue;
                }
                for (final int[] move : MOVES) {
                    if (pos[0] + move[0] >= 0 && pos[1] + move[1] >= 0 && pos[0] + move[0] < 8 && pos[1] + move[1] < 8) {
                        queue2.add(new int[]{pos[0] + move[0], pos[1] + move[1]});
                    }
                }
            }
            queue.addAll(queue2);
            queue2.clear();
            queue.add(MOVE_END_ROUND);
        }
    }
}

Option 3:

import java.util.*;

public class Chess {

    private static LinkedList<int[]> queue;

    public static int knight(String start, String finish) {
        int fromX = start.charAt(0) - 96;
        int fromY = start.charAt(1) - 48;
        int toX = finish.charAt(0) - 96;
        int toY = finish.charAt(1) - 48;
        queue = new LinkedList<>();
        addToQueue(fromX, fromY, 0);
        while (!queue.isEmpty()) {
            int[] spot = queue.remove();
            int x = spot[0];
            int y = spot[1];
            int depth = spot[2];
            if (x == toX && y == toY)
                return depth;
            depth++;
            addToQueue(x - 1, y - 2, depth);
            addToQueue(x - 2, y - 1, depth);
            addToQueue(x + 1, y - 2, depth);
            addToQueue(x + 2, y - 1, depth);
            addToQueue(x + 1, y + 2, depth);
            addToQueue(x + 2, y + 1, depth);
            addToQueue(x - 1, y + 2, depth);
            addToQueue(x - 2, y + 1, depth);
        }
        return -1;
    }

    private static void addToQueue(int x, int y, int depth) {
        if (x > 0 && y > 0 && x < 9 && y < 9) {
            queue.add(new int[]{ x, y, depth });
        }
    }

}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest {
    @Test
    public void sampleTests() {
        assertEquals("Test for (a1, c1)", 2, Chess.knight("a1", "c1"));
        assertEquals("Test for (a1, f1)", 3, Chess.knight("a1", "f1"));
        assertEquals("Test for (a1, f3)", 3, Chess.knight("a1", "f3"));
        assertEquals("Test for (a1, f4)", 4, Chess.knight("a1", "f4"));
        assertEquals("Test for (a1, f7)", 5, Chess.knight("a1", "f7"));
    }
}