Minimum Step by Knight

The problem, simply

You have an N by N chessboard, a knight on one square, and a target square. A knight moves in an L shape: two squares one way, then one square to the side. From the middle of the board it can land on 8 squares. Near the edge it has fewer choices.

Give back the smallest number of hops that takes the knight from its square to the target. If the target can never be reached, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every possible trip, like a mouse that runs down every hallway and comes back.

1. From the current square, try each of the 8 hops that stays on the board and does not step on a square already on this trip.
2. If you land on the target, remember the number of hops if it beats the best so far.
3. Stop a trip early when it already uses as many hops as the best answer.
4. When you come back from a square, take it off the trip so other trips may use it.

class KnightDFS {
    static final int[] DR = {-2, -2, -1, -1, 1, 1, 2, 2};
    static final int[] DC = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int best;

    public static int minKnightMoves(int n, int[] start, int[] target) {
        best = Integer.MAX_VALUE;
        boolean[][] onTrip = new boolean[n][n];
        dfs(n, start[0], start[1], target, onTrip, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    static void dfs(int n, int r, int c, int[] target, boolean[][] onTrip, int hops) {
        if (hops >= best) return;                      // already worse than the best trip
        if (r == target[0] && c == target[1]) { best = hops; return; }
        onTrip[r][c] = true;
        for (int k = 0; k < 8; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !onTrip[nr][nc]) {
                dfs(n, nr, nc, target, onTrip, hops + 1);
            }
        }
        onTrip[r][c] = false;                          // step back so other trips can use it
    }
}

How long it takes: the number of different trips explodes. In the worst case it is up to 8 choices for each of the N^2 squares, O(8^(N^2)). Extra room: the trip marks and the recursion are at most one entry per square, O(N^2).

Way 2: the clever way

Spread out in rings, like the pond. This is breadth first search: every hop costs the same, so the first time you reach a square you reached it with the fewest hops.

1. Write 0 on the start square and put it in a waiting line (a queue).
2. Take the square at the front of the line. For each of its 8 hops that stays on the board and lands on a blank square, write that square's number as one more than the current square, and put it at the back of the line.
3. The moment you write a number on the target, that number is the answer.
4. If the line runs empty first, the target cannot be reached.

class KnightBFS {
    public static int minKnightMoves(int n, int[] start, int[] target) {
        if (start[0] == target[0] && start[1] == target[1]) return 0;
        int[] dr = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dc = {-1, 1, -2, 2, -2, 2, -1, 1};

        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);   // -1 means still blank
        dist[start[0]][start[1]] = 0;

        Queue<int[]> line = new ArrayDeque<>();
        line.add(start);
        while (!line.isEmpty()) {
            int[] cur = line.poll();
            for (int k = 0; k < 8; k++) {
                int r = cur[0] + dr[k], c = cur[1] + dc[k];
                if (r < 0 || r >= n || c < 0 || c >= n || dist[r][c] != -1) continue;
                dist[r][c] = dist[cur[0]][cur[1]] + 1;  // one ring further out
                if (r == target[0] && c == target[1]) return dist[r][c];
                line.add(new int[]{r, c});
            }
        }
        return -1;                                     // the rings never touched the target
    }
}

How long it takes: every square joins the line at most once and checks 8 hops, O(N^2). Extra room: the number grid and the line, O(N^2).

Watch out for

• Off by one positions. Many judges give squares as 1 to N. Subtract 1 from each coordinate first, or check bounds with 1..N.
• Start equals target. Return 0 before the loop.
• Unreachable squares. Small boards (like 3 by 3, or 2 by 2) have squares no knight can reach, so return -1 when the line empties.
• Depth first search does not give the shortest trip on its own. It finds a trip, not the best one.

What interviewers ask next

• What if the board has no edges (infinite board)? Use symmetry: work with |x| and |y|, allow a small margin past the target (like 2 squares below 0), and run the same search. A closed formula also exists.
• Can you make it faster on a huge board? Search from both ends at once (bidirectional search) and stop when the two rings meet. Each side only needs about half the depth.
• How do you print the trip, not just its length? Store who wrote each square (a parent grid), then walk back from the target.
• Some squares are blocked. Treat them as already seen, and the same search works.
• Can the knight visit every square exactly once? That is the knight's tour, a backtracking problem, not a shortest path.

Remember this

Grown-up words: the squares are nodes of an unweighted graph, the hops are edges, the rings are BFS levels, the waiting line is a queue, and the numbers on the board are shortest distances.