Table Of Contents
A knight in chess can move to any square on the standard 8x8 chess board from any other square on the board, given enough turns. Its basic move is two steps forward and one step to the side. It can face any direction. - The Odin Project.
My task is to write code that shows the simplest possible way to get from one square (source) to another square (destination).
I used the graph
data structure to represent the board as a graph where each cell (graph vertex) is connected to the possible moves that can be taken from a knight
in that cell. Atmost 8 places are possible moves from a cell by a knight.
I used adjacency list
to represent the graph
.
Then I used Breadth First Search
to find the shortest path between the given source
and the destination
. Because In an unweighted graph, BFS
always reach the destination with the minimum number of edges
(connection of vertices) from the source.
- Ruby
- What is a Graph
- Representations of a Graph
- Graph - BFS