## 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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 `````` ``````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 tier = Collections.singletonList(startPos); int moveCount = 0; while (true) { moveCount++; List 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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 `````` ``````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 queue = new ArrayDeque<>(); final Queue 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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 `````` ``````import java.util.*; public class Chess { private static LinkedList 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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````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")); } } ``````