Steps by Knight(Graph problem)

Steps by Knight(Graph problem)

The Famous And Simple Problem In Graph Ds-Algo Steps By Knight

In This Blog, I’ve Explaining One Of The Famous Question Of Graph (Min Steps By Knight)

You Must Have Solve Knight Problem In Backtracking Before ,But This One Is Bit Different .

Till now we had given fix set Chess board like 6x6 ,8x8 …

but in this problem ,its length of board is dynamic .

Okay Lets Take Look At Problem Statement

Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.

Note:
The initial and the target position co-ordinates of Knight have been given accoring to 1-base indexing.

Over This We Had Current Location Of Knight And We Have To Find Shortest Require Steps That Lead To Targeted Location

First Lets See brute force approach

Using brute force approach , we can look for each and every possible way which lead us to solution .

but we already know that N x N board is going to be dynamic ,so using brute force might lead us to target position but it will not give us optimal solution

Another Approach That Comes In Mind Is -

BackTracking

Backtracking is just improved version of brute approach

will backtracking lead us to optimal solution ?

Well Yes , At Some Extend Backtracking could do better then brute force but exception is if we consider our board length (1≥N≤1000) then it might not be the optimal one.

At this point we could look for Graph (BFS)/-

We Use Graph To Store And Find Shortest Path In Nodes (with BFS)

We Already Know Knight Moves In 8 Different Direction

This Are The Possible Way Knight Can Move And We Have To Consider This.

Then We Will Need Boolean Array To Track At Which Location We Already Visited And Yet To Be Visit.

Here We Define Our Graph In Form Of Queue Of Array List (You Can Build Graph In Any Form) ,Then Within That Queue We Maintain Array List Of Integer (Which Contains X,Y, No Of Steps Till Now).

And We Mark Very First Location True.

Then We Flow With This Loop ,I Know There To Much Chuck In This Loop

So Lets Break It!

Over Here We Took Last Steps Taken By Knight ,As You Must Reminder We Store List Of X,Y, Steps.

We Will Use Last Location To Make Next Move .

Here We Just Checking Weather We Reach Our Target Or Not .

IF YES RETURN STEPS ELSE CONTINUE;

Before Moving Forward We Check Weather We Are Going In Limits Or Not.

Then We Will Go With Each 8 Direction And We Will Keep Going Till We Found Target And We Marked All Location True That We Already Visited Also We Increase Steps+1 Each Time We Move To Next Step.

If We Don’t Found Any Solution ,Then We Simply Print -1.

Full Code

class Solution
{
boolean isValid(int x, int y, int N){
return (x >=0 && x < N && y >=0 && y < N);
}

public int minStepToReachTarget(int KnightPos[], int TargetPos[], int N)
{
KnightPos[0] — ;
KnightPos[1] — ;
TargetPos[0] — ;
TargetPos[1] — ;

// x and y direction, where a knight can move
int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

boolean vis[][] = new boolean[N][N];

Queue<ArrayList<Integer>> q = new LinkedList<>();
ArrayList<Integer> temp = new ArrayList<>();
temp.add(KnightPos[0]);
temp.add(KnightPos[1]);
temp.add(0);
q.add(temp);

vis[KnightPos[0]][KnightPos[1]] = true;

while(!q.isEmpty())
{
ArrayList<Integer> temp2 = q.poll();
int x = temp2.get(0);
int y = temp2.get(1);
int steps = temp2.get(2);

if(x == TargetPos[0] && y == TargetPos[1])
return steps;

for(int i=0; i<8; i++)
{
int n_x = x + dx[i];
int n_y = y + dy[i];
if(isValid(n_x, n_y, N) && !vis[n_x][n_y])
{
ArrayList<Integer> temp1 = new ArrayList<>();
temp1.add(n_x);
temp1.add(n_y);
temp1.add(steps+1);
q.add(temp1);
vis[n_x][n_y] = true;
}
}
}
return -1;
}
}