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. If you don’t know the algorithm, I suggest you read my post on Breadth First Search Algorithm.

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. 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.

This game needs no introduction. We all must have played it in our childhood. 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. Have a good look at the Snakes and Ladder board below, we will be using it as an example throughout this post.

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. 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.

Don’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. 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. For now, forget about the ladders and the snakes, just draw the graph for a small portion of the board. It should look somewhat similar to what is in the picture below –

As you see we would have six ways to leave block 1, depending on the dice roll. Same would be the case for block 2, or, block 3, and so on. 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. So, the directions are important. 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…?

If you roll 5 from block 1 you will jump directly to block 27. So is for block 2 when you roll out 4, or, block 3 when you roll out 3 and so on. Now, “logically” speaking, the block 6 does not exists in our graph…! Think about the statement for a while. Whenever you reach block, you are directly jumping to block 27, you don’t stay there. Now, if you were constructing an Adjacency List for this graph…. In the list of adjacent vertices for Vertex 1, would you have Vertex 6 in the list, or Vertex 27…? Vertex 27 of course…! Being at Vertex 6 means being at Vertex 27…!

That is why, our edge arrow did not end at Vertex 6… See it…? One more thing, in your Adjacency List, in the list of adjacent vertices for Vertex 6, what would you have…? Nothing…! Because you cannot come to a situation where you would have to stay on Vertex 6 and roll the dice. So the adjacent nodes list corresponding to Vertex 6 should be empty. These two things are very important, when you implement the Adjacency List for the Snake and Ladder board.

Same would be the case, if a snake was there at a block. Logically that block will not exist as a vertex in our adjacency list, and the corresponding edges must be removed. The only difference being that, the edge created due to a snake can lead you to a block of lower value.

Just to get a better idea of the scenario of a ladder and snake, I have depicted what the Adjacency List would look like for the above two examples shown in the pictures.

That pic should really clarify all the confusion about the graph. If you still don’t get it, feel free to comment your query…! Now, what do we do once we have the Adjacency List ready…? We just call the Breadth First Search method on that list…! Wait… Really…?! That’s it…? Yes…!

You see the hardest part here in solving the Snakes and Ladder by graphs is correctly determining what your Vertices and Edges are. Once you get that, all you have to do is the Breadth First Search in the resultant graph. Then you can get the shortest path from Vertex 1 to Vertex 100. Now, try getting the Adjacency Lit correct and simply call the BFS method. I’m sure you will succeed if you put in a little dedication. But for those who tried and failed. I have put my code below. Before you look at my code, there are a few logics I have used –

- In the beginning of the program, I added all the edges as though the Game Board had no snakes or ladders at all (these number of edges is what I printed), then, I removed the respective edges concerning the snakes and ladders one-by-one.
- When a Vertex ‘n’ has a ladder or a snake, we are supposed to replace the corresponding edges as I depicted in the pictures above, for that, I replaced the Vertex
**n**‘s edge with the new value, in Vertices (n – 1), (n – 2), (n – 3), (n – 4), (n – 5), (n – 6). Because it is only in these vertices that you can find an edge of vertex n. - I put all this replacing stuff in a function replace() which takes the Linked List and searches for a value ‘oldVertex’ and replaces it with the value ‘newVertex’ when it finds it.
- I used an extra element in my array to make them 1 – index based.
- The number of moves to complete the shortest path would be the level of the last vertex, Vertex 100. Why…?! Think about it for a minute and you’ll get it…!
- I have added a recursive function, printShortestPath() which recursively looks at the parent of each vertex until the start vertex is reached. It keeps printing vertices as the recursion stack keeps popping out, thus we get the path in a reverse order. Think about this for a while… Trust me… It is easy…! 😉

` `

If you can solve this problem, then you can solve Snakes and Ladders: The Quickest Way Up problem of HackerRank. You can think of extending this to a 20 ✗ 20 Snakes and Ladder board or an **n** ✗ **n** board. You just have to add **n ^{2}** edges to the graph. Solving puzzles by Graph Theory is real fun. I hope this post helped you. If you have any doubts, feel free to comment them. Keep practicing… and… Happy Coding…! 🙂

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution{

public static void bfs(int ver,LinkedList adj[],int s)

{

boolean visited[] = new boolean[ver+1];

int count=0;

int max=0;

// Create a queue for BFS

LinkedList queue = new LinkedList();

// Mark the current node as visited and enqueue it

visited[s]=true;

queue.add(s);

while (queue.size() != 0)

{

s = queue.poll();

count=0;

Iterator i = adj[s].listIterator();

while (i.hasNext())

{

int n = i.next();

if(n==100)

break;

if (!visited[n])

{

visited[n] = true;

queue.add(n);

count++;

}

}

if(count>max)

max=count;

}

System.out.println(max);

}

public static void main(String args[])

{

int t;

Scanner sc=new Scanner(System.in);

t=sc.nextInt();

int ver=100;

LinkedList adj[];

adj=new LinkedList[ver+1];

while(t!=0)

{

int snaknum;

int laddnum;

snaknum=sc.nextInt();

laddnum=sc.nextInt();

int snak[][]=new int[snaknum][2];

int ladd[][]=new int[laddnum][2];

for(int i=0;i<=ver;i++)

adj[i]=new LinkedList();

for(int i=1;i<=ver;i++)

{

for(int j=1;j<=6&&i+j<=100;j++)

adj[i].add(i+j);

}

for(int i=0;i<laddnum;i++)

{

ladd[i][0]=sc.nextInt();

ladd[i][1]=sc.nextInt();

int j=ladd[i][0]-6;

if(j<=0)

j=1;

for(;j<ladd[i][0]&&;j++)

adj[j].set(ladd[i][0],ladd[i][1]);

}

for(int i=0;i<snaknum;i++)

{

snak[i][0]=sc.nextInt();

snak[i][1]=sc.nextInt();

int j=snak[i][0]-6;

if(j<=0)

j=1;

for(;j<snak[i][0];j++)

adj[j].set(snak[i][0],snak[i][1]);

}

for(int i=0;i<=ver;i++)

{

Iterator j = adj[i].listIterator();

while(j.hasNext())

{

System.out.print(j.next()+ ” “);

}

System.out.println();

}

bfs(ver,adj,1);

t–;

}

}

}

i m getting index out of bound error at line

adj[j].set(ladd[i][0],ladd[i][1]);

and adj[j].set(snak[i][0],snak[i][1]);

plz help me out with this implementation

i want to print the shortest path(ie. dice numbers to reach the top)

You can use the printShortestPath() method given in the code for that. You just need to call that method. See this. Hope it helped!

Pingback: Snakes And Ladders – Abordagem com Grafos – Grafos Grafos

Thank you, for such nice explanation. 🙂

My pleasure 🙂

This explanation helped a lot! Thanks 🙂

My pleasure 🙂

Can you please explain Input/Output 2

Why is the answer not

1 80 86 92 96 100

Still 5 moves but wouldn’t that be the logical maximum steps?

Thanks. What clear and concise explanation. Love Aisha

I’m glad you liked it 😀

I rewrite this code in Swift but am not getting the right answer in the second testcase

Heres the link:

https://dl.dropboxusercontent.com/u/8061535/Snakes%26Ladders.playground.zip

rewrote*

Not familiar with Swift… 😛 … But I am keeping your comment so that if a person familiar with Swift reads your comment, he could help you out.. 🙂

Great article and appreciate the effort you put into this. I didn’t read the whole thing yet but right of the bat, I noticed something that immediately throw me off.

Keep in mind, this is my first time coming in contact with Graph Theory after attempting to do the challenge with just simple functions.

My question is, in your adjacency lists, why would you throw Dice 1 at the far end and go up in dice number from right to left. This had me really confused. Its much easier to understand

Vertex 1 -> Dice 1 -> Dice 2 -> Dice 3 -> Dice 4 -> Dice 5 -> Dice 6

It would be great if you formatted your code a little. There is stuff commented out thats part of the code.

I didn’t understand exactly what you suggested… Can you be more specific??

The “Dice X” notation labels the edges… It denotes if ‘X’ appears on the dice, where would you go from the current position to the next position… For example… Vertex 1 → Dice 1 → Vertex 2… This means when you get 1 on your dice, you move from Vertex 1 to Vertex 2… So, in my figure where there’s a ladder… Let’s say you are on Vertex 1, by Dice 1 (arrow given below) you go to Vertex 2, then by Dice 4 (arrow on top) you go to Vertex 6, which is being on Vertex 27… So the path would be…. Vertex 1 → Dice 1 → Vertex 2 → Dice 4 → Vertex 6 (→ ladder →) Vertex 27 ….. It is simple… Just give it a little thought! 😉

hey man, I’m unable to understand what’s happening in breadthFirstSearch function, to be more specific its about the parent and level arrays and also in this function you have commented a working portion of the code.

oh took a while but understood!!!

great work man!!!

I’m glad you could get it by yourself… Thanks a lot! 😀

Your explanation is good, but I dont understand the use of parent and level array.

Okay, I understood that parent helps in tracing the path and level gives the shortest path. But what’s the use of if(level[i]==lev) part?

Okay, I understood it now 🙂

Thanks Vamsi,

Explanation is really helpful.

I am not familier with C language could you please write same in java.

Sure..! I will do it soon 🙂

getting Segmentation Fault error!!

Could you please post the ideone link with the code and the input for which you got the error?!

There is a mistake here:

“… We assume that getting caught by a snake is always unfavorable, and will not add to the progress of a short path…”

That is false. Is easy find an example.

Yes you are right! Corrected it.. Thanks for pointing it out! 🙂

Hello, how would I go about doing an adjacency list in Java 8? I don’t know how to implement from C language…

I have it right here -> http://theoryofprogramming.com/adjacency-list-in-java/ 😉

Hi Vamsi,

How are you handling the veretxes which have null at the end?

It is simple BFS… If a vertex has only NULL, it means there are no adjacent vertices… So BFS just skips this vertex… Have a look at the while loop at line 52 🙂

Why does this give a shortest path to reach 100 ? Can you please explain ?

Sorry for the late reply… We have applied BFS on all the vertices… BFS gives us the shortest distances from a vertex to the start vertex, which is nothing but the level of that vertex, and we also get the parent of each vertex, that is, from which vertex have we reached a particular vertex on our shortest path. Now, I am accessing level[100], where the value 100 is stored in

vertices… So I get the shortest path to the 100^{th}vertex… To print the path, I recursively keep looking at the parent of the vertices starting from 100^{th}vertex till I’ve reached the start vertex… I hope you get it, give it some time, I’m sure you’ll understand it! 🙂Hello sir, can you explain by some examples how graph theory can be used in development projects ?

I haven’t done any projects based on Graph theory yet, but I guess they’ll mostly include visualization related ones…. Like, building a maze, or a racetrack (maybe done by randomized DFS)… Or you could do graph coloring related projects like coloring world map, or the traffic flow problem… Or you could do some visualization of routing algorithms… Looking to do a project to build a maze… I’ll surely make a post here if I do… 🙂

In the function printshortestpath what is the use of elseif block

It was meant for a vertex which does not have a parent, in which case the parent value would be zero… It is not needed here as the parent values would come out just fine… I simply used the path printing function in my Bellman Ford algorithm code. The no parent vertex case was a corner case in that scenario… We don’t need it here… If you want to learn more about the other case, I suggest you to go through the comments in my post on Bellman Ford Algorithm.. 🙂

Hello sir ,

I want proper algorithm of this game..

please help me.

Hi Kushank..! This is the proper algorithm to find the shortest way to win the game…. Can you be more specific as to what exactly you want in your algorithm so that I can help you properly…? 🙂

why you are taking snake tail at 0

I’m sorry @rahul… I didn’t get you…. Can you be more specific..?

I made some changes to your code

Vertices = 9 ;

so it throws me an error – Segmentation Fault.

I make further Changes and it Works .

1)//Dealing with Snakes Edges

for (i = 0; i < num_snakes; ++i) {

scanf("%d%d", &v1, &v2);

j = v1 – 6;

if (j < 1) {

j = 1;

}

2) replacing 100 with vertices every where you have 100 except initialization.

Word of suggestion. Please Write Comments in Program Helps the reader.

Yeah, that’s a little glitch…. Thanks for your suggestion… I have re-written the code… I hope you find it more legit… 🙂

Hey Vamsi,

Really great work, contents are well arranged and complete. Really help full.

Thanks a lot…! 😀

Keep it up! You are doing a great job Vamsi 🙂

Thank you Sir…! 😀

This was really helpful! Thank you; keep em coming!

Sure…! Thanks a lot Simran…!! 😀