Minimum Steps to Reach Target (Knight's Tour BFS)
Problem link: https://www.geeksforgeeks.org/problems/steps-by-knight5927/1
Problem Statement
Given a square chessboard of size N x N and the initial position of a Knight and a target position. Find the minimum number of steps the Knight needs to reach the target position. The knight moves in an 'L' shape: two squares in one cardinal direction and then one square perpendicular to that.
Input
N: Size of the board.knightPos[]: Initial position {x, y}.targetPos[]: Target position {x, y}.
Output
Integer representing the minimum moves.
Example
Input: N = 6, knightPos = {4, 5}, targetPos = {1, 1} Output: 3
Explanation
The knight can follow the path (4,5) -> (3,3) -> (2,1) -> (1,1) in 3 steps.
Brute Force
Intuition
Explore all possible paths using Depth First Search (DFS).
Approach
Recursively try all 8 possible moves from the current position. However, this is highly inefficient as it leads to redundant calculations and potential infinite loops without strict path tracking.
Dry Run
Starting at (4,5), try (2,6), (2,4), (6,6), (6,4), etc., keeping track of visited nodes to avoid cycles.
Code (Java)
class Solution {
public int minStepToReachTarget(int knightPos[], int targetPos[], int n) {
// Brute force DFS usually results in TLE
return -1;
}
}
Complexity Analysis
Exponential time complexity due to exploring all branching paths.
Optimal Solution
Intuition
Since the problem asks for the shortest path in an unweighted grid, BFS is the most efficient choice.
Approach
- Use a Queue to store coordinates and a 2D array to avoid cycles.
- Start BFS from knightPos.
- For each level, explore all 8 L-shaped moves.
- If a move matches targetPos, return steps.
- Ensure moves stay within boundaries [1, N].
Dry Run
Level 0: {4,5} Level 1: Moves from {4,5} Level 2: Moves from Level 1...
Code (Java)
class Solution {
private int bfs(int knightPos[], int targetPos[], int n, int[][] nghPos) {
// 1. Immediate match check
if (knightPos[0] == targetPos[0] && knightPos[1] == targetPos[1]) return 0;
Queue<int[]> q = new LinkedList<>();
// 2. Use n + 1 size to avoid OutOfBounds if coordinates are 1 to N
int[][] visited = new int[n + 1][n + 1];
q.offer(new int[]{knightPos[0], knightPos[1]});
visited[knightPos[0]][knightPos[1]] = 1;
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
steps++; // Increment steps for this level of movement
while (size > 0) {
int[] current = q.poll();
for (int i = 0; i < nghPos.length; i++) {
int nx = current[0] + nghPos[i][0];
int ny = current[1] + nghPos[i][1];
// 3. Check if we found the target
if (nx == targetPos[0] && ny == targetPos[1]) return steps;
// 4. Boundary Check (1 to N)
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && visited[nx][ny] == 0) {
visited[nx][ny] = 1;
q.offer(new int[]{nx, ny});
}
}
size--;
}
}
return -1;
}
public int minStepToReachTarget(int knightPos[], int targetPos[], int n) {
int[][] nghPos = {
{-2, 1}, {-2, -1}, {2, -1}, {2, 1},
{-1, 2}, {1, 2}, {-1, -2}, {1, -2}
};
// If the problem uses 1-based indexing, just use the coordinates directly
// and adjust the 'visited' array size and boundary checks to match.
return bfs(knightPos, targetPos, n, nghPos);
}
}
Complexity Analysis
Every cell is visited at most once.
Quick Revision (Brute Force)
- DFS explores all paths.
- Inefficient for shortest path.
Quick Revision (Optimal)
- BFS for shortest distance.
- Visited array prevents OOM.
- Check boundaries (1 to N).