Minimum Knight Moves on a Chessboard

Given an rows × cols chessboard, a knight's starting square, and a target square (both 1-indexed), return the minimum number of moves the knight needs to reach the target, or -1 if it can't. The knight can't leave the board.

Example

Text

6 × 6 board, from (1, 1) to (4, 5)  ->  3   ((1, 1) -> (3, 2) -> (5, 3) -> (4, 5))
3 × 3 board, from (1, 1) to (2, 2)  ->  -1  (the centre is unreachable)

A knight moves two squares in one direction and one in the other, giving up to 8 moves. Each move is a {row change, column change} pair in an int[][]:

Java

public class Main {
    static final int[][] MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    public static void main(String[] args) {
        System.out.println(MOVES.length);
    }
}

Output

Brute force: try longer and longer move sequences

Search every sequence of exactly d moves, for d = 0, 1, 2, ..., and return the first d that reaches the target. Revisiting a square never helps a shortest path, so a sequence longer than rows · cols - 1 moves can stop the search.

Java

public class Main {
    static final int[][] MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    static boolean reaches(int rows, int cols, int r, int c, int tr, int tc, int movesLeft) {
        if (r == tr && c == tc) {
            return true;
        }
        if (movesLeft == 0) {
            return false;
        }
        for (int[] m : MOVES) {
            int nr = r + m[0], nc = c + m[1];
            if (nr >= 1 && nr <= rows && nc >= 1 && nc <= cols
                    && reaches(rows, cols, nr, nc, tr, tc, movesLeft - 1)) {
                return true;
            }
        }
        return false;
    }

    static int knight(int rows, int cols, int sr, int sc, int tr, int tc) {
        int max = rows * cols;
        for (int d = 0; d < max; d++) {
            if (reaches(rows, cols, sr, sc, tr, tc, d)) {
                return d;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(knight(6, 6, 1, 1, 4, 5) + " " + knight(3, 3, 1, 1, 2, 2));
    }
}

Output

3 -1

Time: O(8ᵈ) for an answer of d moves, and far worse when the target is unreachable. Space: O(d) for the recursion (the recursion depth is at most the rows * cols limit, so large boards need the BFS version).

Optimal: BFS over squares

Squares are vertices and knight moves are edges, all of the same length, so the fewest moves is a shortest path found by breadth-first search. Each square is visited at most once. The queue is an ArrayDeque of int[]{row, col} pairs.

Java

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

public class Main {
    static final int[][] MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    static int knight(int rows, int cols, int sr, int sc, int tr, int tc) {
        int[] dist = new int[rows * cols];
        Arrays.fill(dist, -1);
        dist[(sr - 1) * cols + (sc - 1)] = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{sr, sc});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            if (r == tr && c == tc) {
                break;
            }
            for (int[] m : MOVES) {
                int nr = r + m[0], nc = c + m[1];
                if (nr >= 1 && nr <= rows && nc >= 1 && nc <= cols && dist[(nr - 1) * cols + (nc - 1)] == -1) {
                    dist[(nr - 1) * cols + (nc - 1)] = dist[(r - 1) * cols + (c - 1)] + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        return dist[(tr - 1) * cols + (tc - 1)];
    }

    public static void main(String[] args) {
        System.out.println(knight(6, 6, 1, 1, 4, 5) + " " + knight(3, 3, 1, 1, 2, 2));
        System.out.println(knight(8, 8, 1, 1, 8, 8) + " " + knight(1, 5, 1, 1, 1, 1));
    }
}

Output

3 -1
6 0

Time: O(rows · cols). Space: O(rows · cols).

dist is an int[] indexed by (row - 1) * cols + (col - 1). It doubles as the visited set: -1 means not reached yet. If the queue runs out first, the target keeps -1, which is exactly the required answer.

Edge cases

Start equals target: 0.
Boards narrower than 3 in both directions: most squares have no moves at all.
Very large boards: BFS from both ends, or a formula for the infinite board (LeetCode 1197), avoid visiting every square.