Now, if you were constructing an Adjacency List for this graph…. Whenever you reach block, you are directly jumping to block 27, you don’t stay there. Now, “logically” speaking, the block 6 does not exists in our graph…! Think about the statement for a while. So is for block 2 when you roll out 4, or, block 3 when you roll out 3 and so on. If you roll 5 from block 1 you will jump directly to block 27. Now, let us push up the complexity a bit by adding a ladder to our above sketch in block 6, think what would happen to the edges…? Dice Roll for Block 1 – 5 Now, there is a very important point to be noted here… Remember, this is Directed Graph…! Because, once you roll 5 and go to block 6, there’s no way to come back. Same would be the case for block 2, or, block 3, and so on. It should look somewhat similar to what is in the picture below – Dice Roll from Block 1Īs you see we would have six ways to leave block 1, depending on the dice roll. For now, forget about the ladders and the snakes, just draw the graph for a small portion of the board. If you ponder upon this, it is very easy to tell that the numbered blocks on the game board will be our Vertices, then, what will be the Edges…? This depends on how you can go from one block to another on rolling the dice. Now, think of how you can represent the game board in terms of a Graph, by Graph I mean in terms of Vertices and Edges.ĭon’t be too hard on yourself… Just take the first 7 blocks and try working out on paper what would be the Edge and what would be the Vertices. You can see we can reach the finish block by an number of ways, but how do you find out the best…? More importantly, how do you put it as code…? That’s what we are going to do. Have a good look at the Snakes and Ladder board below, we will be using it as an example throughout this post. I will explain you, how by using Graphs and BFS we can find the Shortest Path to win the game, and, we will state that path and the number of moves of dice it takes too.
![snake game in c language snake game in c language](https://www.codeboks.com/wp-content/uploads/2020/04/Snake-game-in-C.jpg)
We all must have played it in our childhood. And to show you this and to set an example on how the BFS is actually put into action, I am taking up the example of the very popular game, Snakes and Ladders. Now, Graph Theory has many applications and I love working with things that have real-world applications, well, off course the other data structures too have their uses, but the speciality of Graph Theory is its applications have the closest association with our day-to-day activities.
![snake game in c language snake game in c language](https://0.academia-photos.com/attachment_thumbnails/37784898/mini_magick20180815-12935-kgtq4i.png)
If you don’t know the algorithm, I suggest you read my post on Breadth First Search Algorithm. Hello people…! In this post, we will discuss about the Snakes and Ladders Game Code, where we find the shortest path to win the Snakes and Ladders game by using the Breadth First Search (BFS) Algorithm.