Snake and Ladder Problem

Objective – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position.
You can assume the dice you throw results in always favor of you means you can control the dice.

Rules:

  • Start from cell 1.
  • Throw the dice and whatever number you get, move on the number of cells on the board.
  • If you reach a cell which is base of a ladder, then you have to climb up that ladder without a dice throw.
  • If you reach a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.

Example:

Minimum moves required to reach end (36th cell) from start(1st cell)  = 3

  1. First throw on dice, get 2 to reach cell number 3, then take the ladder to reach 16.
  2. Second throw on dice to get 5 to cell number 21, and then take ladder to reach 32.
  3. Third throw on dice to get 4 to reach cell number 36.

Approach:

  • Consider each as a vertex in directed graph.
  • From cell 1 you can go to cells 2, 3, 4, 5, 6, 7 so vertex 1 will have directed edge towards vertex 2, vertex 3….vertex 7. Similarly consider this for rest of the cells.
  • For snake- connect directed edge from head of snake vertex to tail of snake vertex. (See example image above- snake from 12 to 2. So directed edge from vertex 12 to vertex 2)
  • For ladder- connect directed edge from bottom of ladder vertex to top of the ladder vertex.
  • Now problem is reduced to Shorted path problem. So by Breadth-First Search (using queue) we can solve the problem.

Implementation:

  • Each vertex will store 2 information, cell number and number of moves required to reach to that cell. (cell, moves)
  • Start from cell (vertex) 1, add it to the queue.
  • For any index = i, Remove vertex ‘i’ from queue and add all the vertices to which can be reached from vertex ‘i’ by throwing the dice once and update the moves for each vertex (moves = moves to reach cell ‘i’ + 1 if no snake or ladder is present else moves = cell to which snake or ladder will leads to)
  • Remove a vertex from queue and follow the previous step.
  • Maintain visited[] array to avoid going in loops.
  • Once reach to the end(destination vertex), stop.

See the animation below for more understanding.

 
1-12
2-12
3-12
4-12
5-12
6-2
7-12
8-12
9-12
10-12
11-12
12-12
previous arrow
PlayPause
next arrow
Shadow

Time Complexity: O(N)

Complete Code:

import java.util.LinkedList;
import java.util.Queue;
public class SnakeAndLadder {
static class Vertex {
int cell;
int moves;
}
public int findMinMoves(int [] board){
int size = board.length;
//create visited array for each cell
boolean [] visited = new boolean[size];
Queue<Vertex> queue = new LinkedList<>();
//start from position 1 (index 0) and it is already visited
Vertex vertex = new Vertex();
vertex.cell=0;
vertex.moves =0;
queue.add(vertex);
visited[0] = true;
//BFS from cell number 0
while(queue.isEmpty()==false){
//remove from front of queue
vertex = queue.remove();
int cellNum = vertex.cell;
//check if reached to the end
if(cellNum==size1)
break;
//if not reached to the end then add the reachable adjacent cells from the current cells
//Since dice can be controlled and max value can be achieved 6
//so from the current cell, you can reach to next 6 cells so add next 6 cells
for (int i = cellNum+1; i <(cellNum+6) && i<size ; i++) {
//check if cell is already not visited
if(visited[i]!=true){
//add it to the queue, update moves and mak visited
Vertex currentVertex = new Vertex();
currentVertex.moves = vertex.moves+1; //can be reached by throwing dice one more time
visited[i] = true;
//now fill the cell can be reached (might be snake or ladder)
if(board[i]==1){
//means can be reached by throwing dice at that cell
currentVertex.cell = i;
}else{
//might be snake OR ladder at this cell 'i'
//then tail of the snake or top of the ladder will be achieved
// by reaching at cell 'i'
currentVertex.cell = board[i];
}
//add to queue
queue.add(currentVertex);
}
}
}
return vertex.moves;
}
public static void main(String[] args) {
int size = 36;
int [] board = new int[size];
for (int i = 0; i <size ; i++) {
board[i] = 1;
}
//ladders
board[2] = 15;
board[14] = 24;
board[20] = 31;
// Snakes
board[11] = 1;
board[29] = 3;
board[34] = 21;
SnakeAndLadder s = new SnakeAndLadder();
System.out.println("Minimum Dice throws needed to reach to end: " + s.findMinMoves(board));
}
}

view raw
SnakeAndLadder.java
hosted with ❤ by GitHub


Output:

Minimum Dice throws needed to reach to end: 3

Reference: here