Snake and Ladder Problem in Java
Find the smallest number of dice throws necessary to reach the destination or last cell from the source or first cell on a snake and ladder board. Essentially, the player has complete control over the outcome of the dice throw and wishes to determine the smallest number of tosses necessary to reach the last cell.
If the player reaches a cell that is the base of a ladder, the player must climb that ladder, and if the player reaches a cell that is the mouth of the snake, the player must drop to the tail of the snake without a dice roll.
Take the board given as an example; it takes three minimum tosses of the dice to get from cell 1 to cell 30.
The steps are as follows:
- To go to cell number 3, roll two dice, and then climb the ladder to get to cell number 22.
- Then throw 6 more times to get to 28.
- Finally, I made it from 2 through 30.
Similar alternatives are (2, 2, 6), (2, 4, 4), and (2, 3, 5), among many others.
Consider the given snake and ladder board to be a directed graph with a number of vertices equal to the number of cells on the board. Finding the shortest path in a graph simplifies the problem. If the following six vertices do not have a snake or ladder, every vertex in the graph has an edge to them. If any of the following six vertices has a snake or a ladder, the edge from the current vertex will proceed to the top of the ladder or the tail of the snake. Because all edges have the same weight, we can use the graph's Breadth-First Search to discover the shortest path.
The execution of the following concept is shown below. The input is represented by two things: 'A,' which is the number of cells on the specified board, and an array'move[0...A-1]' of size A. If there is no snake or ladder from u, move[u] is -1; otherwise, move[u] includes the index of the destination cell for the snake or ladder at u.
Filename: SnakesLadder.java
// Java application for determining the smallest number of dice
// Throws are necessary to reach the last cell from the first.
// A given snake's cell with a ladder board
import java.util.LinkedList;
import java.util.Queue;
public class SnakesLadder {
// A queue entry used in BFS
static class qentry {
int c; // Vertex number
int dist; // The distance between this vertex and the source
}
// This method returns the smallest number of dice.
// Throws are necessary to reach the last cell from the 0'th cell.
// In a game of snakes and ladders. move[] is a collection of
// size A, where A is the number of cells on board If there is
// If there is no snake or ladder in cell u, then move[u].
// is -1 Otherwise, move[u] includes the cell to which
// u takes a snake or a ladder.
static int getMinDiceThrows(int move[], int n)
{
int visited[] = new int[n];
Queue<qentry> q = new LinkedList<>();
qentry qe = new qentry();
qe.c = 0;
qe.dist = 0;
// Enqueue and mark node 0 as visited.
visited[0] = 1;
q.add(qe);
// Perform a BFS beginning from the vertex at index 0.
while (!q.isEmpty()) {
qe = q.remove();
int c = qe.c;
// If the destination is the front vertex
// vertex, we are done
if (c == n - 1)
break;
// Otherwise, remove the front vertex from the queue and
// enqueue its neighbouring vertices (or cells
// numbers that may be obtained by rolling a die)
for (int u = c + 1; u <= (c + 6) && u < n;
++u) {
// If this cell has previously been visited,
// ignore
if (visited[u] == 0) {
// Otherwise, determine its distance and
// Register it as visited
qentry a = new qentry();
a.dist = (qe.dist + 1);
visited[u] = 1;
// Look for a snake or a ladder.
// 'c' then snake's tail or top of
// ladder is now near to 'u'
if (move[u] != -1)
a.c = move[u];
else
a.c = u;
q.add(a);
}
}
}
// We arrive here when 'qe' has its last vertex.
// return the vertex distance in 'qe'
return qe.dist;
}
public static void main(String[] args)
{
// Let us build the board shown in the diagram above.
int A = 30;
int moves[] = new int[A];
for (int u = 0; u < A; u++)
moves[u] = -1;
// Ladders
moves[1] = 7;
moves[5] = 21;
moves[10] = 12;
moves[20] = 15;
// Snakes
moves[26] = 0;
moves[21] = 4;
moves[14] = 9;
moves[19] = 2;
System.out.println("The Minimum number of dice rolls needed is "
+ getMinDiceThrows(moves, A));
}
}
Output:
The following approach has an O(N) time complexity since each cell is added and deleted from the queue only once. And an enqueue or dequeue action typically takes O(1) time.
Another option is recursion, in which we travel to each block, in this example from 1 to 30, and keep a record of the minimum number of dice tosses at each block u and store it in an array t.
So, in general, we will:
- Make an array, say 't,' and initialise it with -1.
- Now we'll execute a recursive function from block 1 with a variable called u which we will increment.
- Here also, we will define the base condition as when the block number reaches 30 or greater, we will return 0, and we will also check if this block has been visited before, which we will do by verifying the value of t[u], if this is -1, it means it has not been visited and we will proceed with the function, otherwise it has been visited and we will return the value of t[u].
- Following the completion of the basic cases, we will initialise the variable 'min' with a maximum integer value.
- Now, for every iteration, we would raise the value of u by the value of dice (eg: u+1,u+2....u+6) and verify whether any increment does have a ladder on it, if so, we will update the value of u to the end of the ladder and then send the value to the recursive function, if we don't have a ladder, we will pass the incremented value of u based on dice value to a recursive function; however, if we have a snake, we will not pass this value to a recursive function because we want to get to the end as soon as possible, and the best way to accomplish this is to avoid being eaten by a snake. And we'd keep updating the minimal value for the variable 'min'.
- Finally, we will add min to t[u] and return t[u].
The following technique is implemented as follows:
Filename: SnakeLadder.java
import java.io.*;
import java.util.*;
class SnakeLadder {
// Create an array t of length 31 that will be used from.
// index to 1 to 30
static int[] t = new int[31];
static int minThrow(int n, int arr[])
{
for (int u = 0; u < 31; u++) {
// the initialization of each index of t with -1
t[u] = -1;
}
// establish a hashmap to store snakes and ladders
// then ultimately, for more efficiency
HashMap<Integer, Integer> h = new HashMap<>();
for (int u = 0; u < 2 * n; u = u + 2) {
// start as the key and end as the value
h.put(arr[u], arr[u + 1]);
}
// final ans
return sol(1, h);
}
//by using recursive function
static int sol(int u, HashMap<Integer, Integer> h)
{
// base condintion
if (u >= 30)
return 0;
// checking to see whether the block has previously been visited or
// not(memoization).
else if (t[u] != -1)
return t[u];
// establishing min as the maximum int value
int min = Integer.MAX_VALUE;
// for each dice value ranging from 1 to 6
for (int v = 1; v <= 6; v++) {
// incrementing the value of u with the value of the dice, i.e. v
// introducing a new variable x
//->using a new variable to avoid changing u
// since we'll need it again in a later iteration
int x = u + v;
if (h.containsKey(x)) {
// determining whether this is a snake of ladder or not
// If it's a snake, we will be keep going because
// need a snake
if (h.get(x) < x)
continue;
// If it is a ladder to ladder end, it should be updated
// value
x = h.get(x);
}
// changing min in each iteration to obtain
// from this specific block, the absolute minimum tosses
min = Math.min(min, sol(x, h) + 1);
}
// changing the value of t[u] to min
// memoization
t[u] = min;
return t[u];
}
// main
public static void main(String[] args)
{
// Assuming a snakes and ladders board of 5x6,
// You are given a number N that represents the total
// There are several snakes and ladders, along with an array.
// 2*N in size, with 2*u and (2*u + 1)th values
// mark the beginning and end points, respectively
// a snake or a ladder
int N = 8;
int[] arr = new int[2 * N];
arr[0] = 4;
arr[1] = 12;
arr[2] = 8;
arr[3] = 15;
arr[4] = 6;
arr[5] = 26;
arr[6] = 2;
arr[7] = 21;
arr[8] = 14;
arr[9] = 19;
arr[10] = 12;
arr[11] = 7;
arr[12] = 26;
arr[13] = 3;
arr[14] = 29;
arr[15] = 9;
System.out.println("The Minimum number of dice rolls needed is "
+ minThrow(N, arr));
}
}
Output:
