## 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<>();
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]});
}
}
}
queue2.clear();
}
}
}
``````

Option 3:

``````import java.util.*;

public class Chess {

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