Remember the childhood snake and ladder game which we used to play? Well, in this article we will be discussing the same game and its implementation in programming.
The problem statement that we will be solving is- Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source or 1st cell. This is done by considering that the player can determine which number appears in the dice being biased. The player rolls the dice and if reaches a base of a ladder then he can move up the ladder to a different position/cell and if he reaches a snake then it brings him down away from the destination cell/position. This problem can be solved using a Breadth-First Search (BFS). So, let us first see the prerequisites briefly.
Graph
The graph is a data structure which is used to implement or store paired objects and their relationships with each other. It consists of two main components:
- Vertex/Nodes: These are used to represent the objects. E.g. Let us consider a graph of cities where every node is a city. Let A and B be two such cities represented by two nodes A and B.
- Edges: These represent relationships between those objects. E.g. Let the roads connecting these cities be considered as the relationship that they hold with each other i.e. the edge. One more parameter can be considered which is called the weight. If the roads consist of values like the distance then we can say to reach from city A to B we require some D distance, where D becomes the weight of the edge between A and B.
Here we will be using unweighted directed graph and each cell will be considered as an intersection of nodes/cells of the board. Hence the problem becomes to find the minimum/shortest path to reach the destination cell from the source cell. For this, we will be using Breadth-First Search (BFS) as it gives the shortest path in an unweighted graph.
Breadth First Search (BFS)
Let us first discuss the BFS implementation using adjacency matrix representation. In this method we consider a matrix of vertices which contains the relationship information in the matrix i.e., if a vertex u is connected to vertex v, there will be an edge/relationship at matrix[u][v] and it might be bidirectional or unidirectional weighted or unweighted directed depending up the need of the problem.
Code Implementation:
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *adjMatrixOfGraph(){
int i,u,v;
Graph *G = new Graph;
// cout<<"Enter no. of Vertices ";
cin>>G->V;
//cout<<"Enter no. of Edges ";
cin>>G->E;
G->Adj = new int*[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[j] = new int[G->V];
for(int u = 0 ;u<G->V;u++)
for(int v = 0;v<G->V;v++)
G->Adj[u][v] = 0;
for(int i = 0;i<G->E;i++)
{
//Undirected Graph
//cout<<"Enter edge pair: _%d_%d_ ";
//for directed graph adj(u,v) gives only the edge u->v
cin>>u>>v;
G->Adj[u][v] = 1;
G->Adj[u][v] = 1;
}
return G;
}Space Complexity – where V is the number of vertices.
Now, using this in Breadth First Search (BFS) we implement the following code:
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *createAdjMatrix(int V,int E) {
struct Graph* G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;i<G->V;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;i<G->E;i++)
{
int u,v;
cin>>u>>v;
G->Adj[u][v] = 1;
G->Adj[v][u] = 1;
}
return G;
}
void BFS(struct Graph* G,int u,bool* visited){
queue<int> q;
q.push(u);
visited[u] = true;
while(!q.empty()){
int currentVertex = q.front();
q.pop();
cout<<currentVertex<<" ";
for(int i = 0;i<G->V;i++)
{
if(i==currentVertex)
continue;
if(!visited[i] && G->Adj[currentVertex][i])
{
q.push(i);
visited[i] = true;
}
}
}
}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;i<G->V;i++)
visited[i] = false;
for(int i = 0;i<G->V;i++)
if(!visited[i])
BFS(G,i,visited);
}Now when we have done with the basic requirements let us see the approach of solving the problem. The idea is to traverse the graph nodes in BFS fashion and as the graph is unweighted/uniformly weighted we can use the Breadth First Search Algorithm easily to find the shortest path to the destination node from source node/cell.
We store the distance in the queue for particular nodes and keep on updating the node’s neighbour’s distance if the current distance is smaller than the previous distance and hence at the end of the whole BFS traversal we will have the shortest distance stored in the destination node.
Let us see the code implementation:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int v;
int dist;
};
int minimumSolve(int graph[], int N)
{
bool *visited = new bool[N];
for (int i = 0; i < N; i++)
visited[i] = false; // not visited
//creating a queue
queue<node> q;
visited[0] = true;
node n = {0, 0};
q.push(n);
node cell;
while (!q.empty())
{
cell = q.front();
int v = cell.v;
if (v == N-1)
break;
q.pop();
for (int j=v+1; j<=(v+6) && j<N; ++j)
{
if (!visited[j])
{
node a;
a.dist = (cell.dist + 1);
visited[j] = true;
if (graph[j] != -1)
a.v = graph[j];
else
a.v = j;
q.push(a);
}
}
}
return cell.dist;
}
// Driver program to test methods of graph class
int main()
{
// Let us construct the board given in above diagram
int N = 50;
int graph[N];
for (int i = 0; i<N; i++)
graph[i] = -1;
// Marking the Ladders
graph[4] = 21;
graph[6] = 7;
graph[12] = 25;
graph[25] = 28;
// MArking the Snakes
graph[30] = 0;
graph[12] = 8;
graph[6] = 3;
graph[21] = 6;
cout << minimumSolve(graph, N);
return 0;
}
Space Complexity - O(V*V) where V is the number of vertices/nodes.
Another implementation of the Snake & Ladder game as a function is also given below –
vector<int> calculate(int row,int next_step)
{
//for flipping the dirctions in the board
int x=(next_step-1)/row;
int y=(next_step-1)%row;
if(x%2==1)y=row-1-y;
x=row-1-x;
return {x,y};
}
//vector board function
int snakesAndLadders(vector<vector<int>>& board) {
int r=board.size();
queue<int> q;
q.push(1);
int step=0;
while(!q.empty())
{
int n=q.size();
for(int i=0;i<n;i++)
{
int t=q.front();
q.pop();
if(t==r*r)return step;
for(int i=1;i<=6;i++)
{
int next_step=t+i;
if(next_step>r*r)break;
auto v=calculate(r,next_step);
int row=v[0],col=v[1];
if(board[row][col]!=-1)
{
next_step=board[row][col];
}
if(board[row][col]!=r*r+1)
{
q.push(next_step);
board[row][col]=r*r+1;
}
}
}
step++;
}
return -1;
}
Space Complexity - O(V*V) where V is the number of vertices/nodes.
Time and Space Complexity remains the same. This algorithm is very easy and fun to use as it can also be used to make a simple Snake and Ladder game for small projects. The whole code structure remains the same only the marking of the cells has to be visualised.
Hope this article helps as an aspiring developer and a programmer and it can also be used to create a small project for adding into your portfolio. To learn more, visit our blog section and to explore our programming courses, you can check our out course page.
By Aniruddha Guin
