CODEWITHSUNDEEP
algorithmdata-structuresgraphbreadth-first-searchknights-tour
Mahideep
Mahideep

Reputation: 41

How BFS gives Minimum steps to reach target by a Knight in Infinite chess board

There is a problem in which we should find out the minimum number of moves required by a Knight to reach its destination in an Infinite Chessboard. BFS solves this in finding that by making one move to one of its all 8 adjacent reachable vertices. I am not able to understand how does BFS algorithm is able to achieve that. Can any please explain that how does BFS work here.

Upvotes: 1

Views: 1708

Answers (1)

Marco Zamboni
Marco Zamboni

Reputation: 224

As I understand this is a Brute Force approach, you try every possible move until you reach the destination.

You can see the chessboard as a graph where every cell is a node and the edges are the knight moves (the L shaped one), so for example (0,0), (1,0), (2,1) are nodes and there is an edge between (0,0) and (2,1); but not between (0,0) and (1,0)

With BFS you explore in this way: first you look to all the cells you can reach in 1 move, then you look to all ones you can reach in 2 moves, then 3 moves etc... In this way any time you reach a new cell you can be sure that it can't be reached in less moves than your current level (otherwise it must have been already reached); this obviously works for the destination cell, too; so while exploring with the BFS you stop when you reach the destination and return the current level (that is the minimum number of moves)

Upvotes: 0

Related Questions