BFS to solve 'Snake and Ladder' Problem.

Howdy folks! Thank you for visiting my blog once again. 😊

Today, let’s implement another interesting algorithm, that is Snake and Ladder board in Java. Consider below snake & ladder board,

fig.1

Problem Statement:

In above board, there are 100 cells. Considering player has a full control over a dice he throws. write an algorithm to find out minimum number of throws required to reach to the last cell which is 100^th cell from the 1^st cell.

Approach:

Let’s convert above board into a graph (Unaware about graph DS? click on mypost) having 100 nodes. Each node is connected to maximum 6 nodes as dice has maximum six numbers. In between if I have the ladder then the top of ladder node is directly connected to the source node. So, in our board Node -1 is connected to the {2,3,4,25,6,7}. Also, if there is a snake then it will take you to the bottom of it. So, in our board if I’m at node 6 then I can go to node {7,8,9,29,30,11}. Looking at the below table, we can understand that in 2 dice throws I can reach to maximum node-58. And we can continue this breadth wise search until 100^th cell is reached (I recommend you to refer mypost on BFS before starting).

No. Of Throws	If Source Node	Then Destination nodes.
Throw-1	1	{2,3,4,25,6,7}
Throw-2	2	{3,4,25,26,27,55}
	3	{4,25,26,27,55,56}
	4	{25,26,27,55,56,57}
	25	{26,27,55,56,57,58}
	6	{7,8,9,29,30,11(snake)}
	7	{8,9,29,30,11,32}

Solution:

So just open your favorite IDE. I have solved the problem using eclipse as shown below.  

package com.mayank4java.algorithms;

import java.util.LinkedList;

import java.util.Queue;

public class SnakeLadderBoard 

{

private int board[];

private boolean isVisited[];

private final static int MAX_DICE_NUM=6;

private int count=0;

public SnakeLadderBoard(){}

public SnakeLadderBoard(int cells){

board=new int[cells];

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

{

board[i]=-1;

}

isVisited=new boolean[cells];

}

/*Inner class*/

class Data

{

int distanceCoverd;

int noOfDiceThrow;

}

public int findMinDiceThrows()

{

Queue<Data> queue = new LinkedList<Data>();

Data data=new Data();

data.distanceCoverd=0;

data.noOfDiceThrow=0;

isVisited[data.distanceCoverd]=true;

queue.add(data);

while(!queue.isEmpty())

{

data = queue.remove();

for(int i=data.distanceCoverd+1 ; i < data.distanceCoverd+6 && i < board.length ;i++)

{

count++;//count is just to find out number of loops

if(!(isVisited[i]))

{

Data child=new Data();

if(board[i] < 0 )

child.distanceCoverd=i;

else

child.distanceCoverd=board[i];

child.noOfDiceThrow=data.noOfDiceThrow+1;

queue.add(child);

isVisited[i]=true;

}

}

/* Below Logic :

* In our example, If distance covered is 93 then adding one hope will reach to the 99

* this logic will make algorithm more time efficient :

* In our case with this logic, loop will run for 290 times and if i replace below if condition with

* if(data.distanceCoverd >= board.length-1){} then,374 loops will be required.

* */

if(data.distanceCoverd >= board.length-MAX_DICE_NUM-1)

{

data.distanceCoverd=data.distanceCoverd+MAX_DICE_NUM;

data.noOfDiceThrow=data.noOfDiceThrow+1;

break;

}

}

System.out.println("Algorithm took "+count+" loops to excecute...");

return data.noOfDiceThrow;

}

public static void main(String[] args) 

{

SnakeLadderBoard play=new SnakeLadderBoard(100);

//Add Ladders

play.board[4]=24;

play.board[9]=29;

play.board[21]=40;

play.board[27]=54;

play.board[43]=94;

play.board[69]=88;

play.board[78]=80;

//Add Snakes

play.board[36]=16;

play.board[30]=13;

play.board[77]=38;

play.board[98]=6;

play.board[91]=34;

play.board[72]=52;

System.out.println("Minimum No of dice throws required "+play.findMinDiceThrows());

}

}

That is it folks! 😊

Hope this post helped you.Also don't forget to share and leave your comments below.