Snakes and Ladders Game Code

Hello people…! In this post I will explain you how to find the shortest path to win the Snakes and Ladder game by using the Breadth First Search (BFS) Algorithm. If you don’t know the algorithm, I suggest you read my post about it. 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 Ladder. Now, 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.

We assume that getting caught by a snake is always unfavorable, and will not add to the progress of a short path. 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 theSorry for the bad snip…! 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
  eplace 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 ‘num’ and replaces it with the value ‘replaced_num’ 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 backtracked from Vertex 100, finding who it’s parent was, then, who the parent’s parent was and so on to find the path and finally printed it in reverse order.

/*
 * Snake and Ladder Shortest Path in C
 * using Adjacency List and
 * Breadth First Search.
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <stdio.h>
#include <stdlib.h>

struct node {
	int val;
	struct node * next;
};

struct node * add(struct node * head, int num)
{
	struct node * p = (struct node *) malloc(sizeof(struct node));

	p->val = num;
	p->next = head;

	return p;
}

void breadth_first_search(struct node * list[], int vertices, int parent[], int level[])
{
	struct node * temp;
	int i, par, lev, flag = 1;

	lev = 0;
	level[1] = lev;

	while (flag) {
		flag = 0;
		for (i = 1; i <= vertices; ++i) {
			if (level[i] == lev) {
				flag = 1;
				temp = list[i];
				par = i;

				while (temp != NULL) {
					if (level[temp->val] != -1) {
						temp = temp->next;
						continue;
					}

					level[temp->val] = lev + 1;
					parent[temp->val] = par;
					temp = temp->next;
				}
			}
		}

		++lev;
	}
}

void replace(struct node * head, int num, int replaced_num)
{
	struct node * p = head;

	while (p->next != NULL) {
		if (p->val == num) {
			break;
		}

		p = p->next;
	}

	p->val = replaced_num;
}

int main()
{
	int vertices, edges, i, j, v1, v2;

	vertices = 100;		//For a 10X10 board
	edges = 0;			//Just to count the edges

	struct node * list[vertices + 1];

	int parent[vertices + 1];
	int level[vertices + 1];	

	for (i = 0; i <= vertices; ++i) {
		//Initialising our arrays
		list[i] = NULL;
		parent[i] = 0;
		level[i] = -1;
	}

	for (i = 1; i <= vertices; ++i) {
		for (j = 1; j <= 6 && j + i <= 100; ++j) {
			list[i] = add(list[i], i + j);
			++edges;
		}
	}

	printf("Edges added so far = %d\n", edges);

	int num_ladders, num_snakes;

	printf("Enter the Number of Ladders and Snakes -\n");
	scanf("%d%d", &num_ladders, &num_snakes);

	printf("Enter the Ladder Edges -\n");
	//Dealing with Ladder Edges
	for (i = 0; i < num_ladders; ++i) {
		scanf("%d%d", &v1, &v2);

		j = v1 - 6;

		if (j < 1) {
			j = 1;
		}

		for (; j < v1; ++j) {
			replace(list[j], v1, v2);
		}
	}

	printf("Enter the Snake Edges -\n");
	//Dealing with Snakes Edges
	for (i = 0; i < num_snakes; ++i) {
		scanf("%d%d", &v1, &v2);

		j = v1 - 6;

		if (j < 0) {
			j = 0;
		}

		for (; j < v1; ++j) {
			//Replacing Vertex value v1 by v2
			replace(list[j], v1, v2);
		}
	}

	//Printing Adjacency List
	printf("\nAdjacency List -\n");
	for (i = 1; i <= vertices; ++i) {
		printf("%d -> ", i);

		struct node * temp = list[i];

		while (temp != NULL) {
			printf("%d -> ", temp->val);
			temp = temp->next;
		}

		printf("NULL\n");
	}

	breadth_first_search(list, vertices, parent, level);
	printf("\nNumber of Moves required = %d\n", level[vertices]);

	/*Just a little mechanism to print the shortest path*/
	int path[level[vertices] + 1];

	j = 100;
	path[0] = j;

	for (i = 1; i <= level[vertices]; ++i) {
		path[i] = parent[j];
		j = parent[j];
	}

	printf("\nShortest Path -\n");
	for (i = level[vertices]; i >= 0; --i) {
		printf("%d -> ", path[i]);
	}
	printf("Finish...!\n");

	return 0;
}

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² 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…! 🙂

You may also like –

• Dynamic Programming – Introduction and Fibonacci Numbers
• Binary Indexed Tree or Fenwick Tree
• Number Theory – Modular Arithmetic
• Graph Theory – Breadth First Search
• Quick Sort

More in the Navigation Page ! →