Minimum Step by Knight
Problem Statement
Given an N×N chessboard, a knight's starting position, and a target position, find the minimum number of moves the knight needs to reach the target.
A knight moves in an "L" shape: 2 squares in one direction and 1 square perpendicular (or vice versa), giving 8 possible moves.
Example:
- Input:
N = 6, start = (0,0), target = (5,5) - Output:
4
Noob-Friendly Explanation
Think of a chess knight — it makes an "L-shaped" jump. From any square, it can jump to up to 8 different squares. We want to find the fewest jumps to get from the start square to the target square.
It's like asking: "What's the minimum number of bus rides to get from your home to school, if the bus can only go to certain stops from each location?" BFS (level-by-level search) gives us the shortest path.
Approach 1: Brute Force (DFS — Explore All Paths)
Intuition
Use DFS to try every possible sequence of moves. Track the minimum number of moves needed to reach the target. This is inefficient because it explores many unnecessary long paths.
Algorithm
- Start DFS from the knight's position.
- Try all 8 moves recursively.
- Track the minimum moves to reach the target.
- Use visited array to avoid infinite loops.
public class KnightDFS {
static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
static int minMoves;
public static int minKnightMoves(int N, int[] start, int[] target) {
boolean[][] visited = new boolean[N][N];
minMoves = Integer.MAX_VALUE;
dfs(N, start[0], start[1], target[0], target[1], visited, 0);
return minMoves == Integer.MAX_VALUE ? -1 : minMoves;
}
static void dfs(int N, int row, int col, int targetRow, int targetCol,
boolean[][] visited, int moves) {
if (row == targetRow && col == targetCol) {
minMoves = Math.min(minMoves, moves);
return;
}
if (moves >= minMoves) return; // prune: already worse than best
visited[row][col] = true;
for (int i = 0; i < 8; i++) {
int newRow = row + dx[i];
int newCol = col + dy[i];
if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N
&& !visited[newRow][newCol]) {
dfs(N, newRow, newCol, targetRow, targetCol, visited, moves + 1);
}
}
visited[row][col] = false; // backtrack
}
public static void main(String[] args) {
int N = 6;
int[] start = {0, 0};
int[] target = {5, 5};
System.out.println(minKnightMoves(N, start, target));
}
}Complexity Analysis
- Time Complexity: O(N^N) — exponential in the worst case as we explore all paths.
- Space Complexity: O(N^2) — for the visited array and recursion stack.
Approach 2: Optimal (BFS)
Intuition
BFS explores moves level by level. Since each move has equal "cost" (1 move), the first time we reach the target is guaranteed to be the shortest path. This is the classic approach for shortest path in unweighted graphs.
Algorithm
- Start BFS from the knight's position.
- Enqueue the start with distance 0.
- For each position, try all 8 possible knight moves.
- If a move leads to the target, return the distance.
- If the new position is valid and unvisited, enqueue it.
import java.util.LinkedList;
import java.util.Queue;
public class KnightBFS {
public static int minKnightMoves(int N, int[] start, int[] target) {
int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
boolean[][] visited = new boolean[N][N];
Queue<int[]> queue = new LinkedList<>(); // {row, col, distance}
visited[start[0]][start[1]] = true;
queue.add(new int[]{start[0], start[1], 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0], col = curr[1], dist = curr[2];
if (row == target[0] && col == target[1]) {
return dist;
}
for (int i = 0; i < 8; i++) {
int newRow = row + dx[i];
int newCol = col + dy[i];
if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N
&& !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.add(new int[]{newRow, newCol, dist + 1});
}
}
}
return -1; // target unreachable
}
public static void main(String[] args) {
int N = 6;
int[] start = {0, 0};
int[] target = {5, 5};
System.out.println(minKnightMoves(N, start, target)); // 4
}
}Complexity Analysis
- Time Complexity: O(N^2) — each cell on the board is visited at most once.
- Space Complexity: O(N^2) — for the visited array and queue.