Min Steps by Knight

Problem Overview

Every knight move costs the same, so the fewest moves is a shortest path in an unweighted graph whose nodes are the board squares.

Intuition

Every knight move costs the same, so the fewest moves is a shortest path in an unweighted graph whose nodes are the board squares. A breadth first search from the knight reaches squares in order of distance, one level per move. The first time a move lands on the target, that level is the answer. The board edges and corners change distances, so a formula for an unbounded board does not work here.

Algorithm

1Convert both positions from 1 indexed to 0 indexed. If they are the same square, return 0.
2Store each square as one number, row times n plus column, in a flat array queue. Mark the starting square as seen.
3Process the queue one level at a time. For each square, try the eight knight moves and skip any that leave the board.
4If a move lands on the target, return the current level. Otherwise queue unseen squares and mark them as seen.
5If the queue empties first, the target cannot be reached, so return -1.

Example Walkthrough

Input: knightPos = [4,5], targetPos = [1,1], n = 6

1. The first move reaches squares such as (2,4).
2. The second move reaches (3,2) from (2,4).
3. The third move goes from (3,2) to (1,1), which is the target.

Output: 3

Common Pitfalls

• The input positions are 1 indexed. Subtract one before using them as indexes.
• Some squares on tiny boards are unreachable, such as the center of a 3 by 3 board. The search must return -1 there.
• Mark squares as seen when they are queued. Marking them only when they are removed can add the same square many times.
• Creating a new object for every square slows the search. One number per square in an array is enough.

Min Steps by Knight.java

Java

// Approach: Breadth first search from the knight over board squares. Each
// square is one int (row * n + col) in a flat array queue, so no objects are
// allocated. Levels are processed as a block, and the first time a move lands
// on the target, the current level + 1 is the minimum. If the queue empties
// first, the target is unreachable (small boards like n = 3 have such squares).
// Complexity: O(n^2) time, O(n^2) extra space.
class Solution {
    private static final int[] DX = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private static final int[] DY = { 2, 1, -1, -2, -2, -1, 1, 2 };

    public int minStepToReachTarget(int knightPos[], int targetPos[], int n) {
        int kx = knightPos[0] - 1;
        int ky = knightPos[1] - 1;
        int tx = targetPos[0] - 1;
        int ty = targetPos[1] - 1;
        if (kx == tx && ky == ty)
            return 0;

        boolean[] seen = new boolean[n * n];
        int[] queue = new int[n * n];
        int head = 0;
        int tail = 0;
        queue[tail++] = kx * n + ky;
        seen[kx * n + ky] = true;

        for (int steps = 1; head < tail; steps++) {
            int levelEnd = tail;
            while (head < levelEnd) {
                int cell = queue[head++];
                int cx = cell / n;
                int cy = cell % n;
                for (int d = 0; d < 8; d++) {
                    int nx = cx + DX[d];
                    int ny = cy + DY[d];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                        continue;
                    if (nx == tx && ny == ty)
                        return steps;
                    int id = nx * n + ny;
                    if (!seen[id]) {
                        seen[id] = true;
                        queue[tail++] = id;
                    }
                }
            }
        }
        return -1;
    }
}

Was this solution helpful?