Resolving a chess knight shortest path problem with BFS (Breadth-first search) algorithm in Swift.
In order to understand this solution you need to know:
Problem:
A chessboard is composed of 8×8 squares. In a chess game, knight is a piece that is allowed to move two squares horizontally and one square vertically or one square horizontally and two squares vertically.
Find a minimum number of steps required to reach destination square from the source square. Source and destination square origins are provided below as input values.
Input:
Source = (0,0)
Destination = (7,0)
Output:
Minimum number of steps required is 5.
Solution:
- In this case, chessboard is a graph where each square is a node or a vertex and each knight move is an edge or a link. Create a matrix which represents all possible knight’s moves.
- For each square or a node create an adjacency list based on knight’s moves matrix.
- Transverse tree in a BFS fashion and find a shortest path to destination square or node or a vertex.
