Question 57. Find the least number of dice throws needed to complete the snake and ladders game

To find the least number of dice throws, we use the following dynamic programming technique:

1. Initialize the least number of throws needed to reach the positions 1-6 on the board as 1 since we can reach these positions with a single dice throw of a 6-sided dice

2. For any remaining position, we can either reach it from
• any of the previous 6 positions with one dice throw. If there is a snake at a previous position, then we ignore that cell while calculating the least number of throws for the current position

• or we can reach it by a ladder if present from some previous position. If there is a ladder from position I to position P, and we need N throws to reach I, then we can reach P also in N throws.

So we use the formula below to calculate the least number of throws for positions greater than 6

3. The least number of throws to reach the final position of the board gives the least number of throws needed to complete the game

C/C++

```
/*is_snake: if there is a snake at position 20, then is_snake[20] is set to 1
if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to
current position with least number of dice throws. If predecessor[100]
= 95, then we reached 100 from 95. It is computed and returned.
Return value: least number of throws to reach the final position on the board
*/
int find_least_throws(int is_snake[], int ladder[], int predecessor[])
{
/*for a particular position pos on the board, least_throws[pos] will store
the least number of dice throws required to reach the position*/
int least_throws[MAX_POSITIONS_ON_BOARD + 1];
int min_throws, i;

/*Positions from 1 to 6 can be reached from a single dice throw*/
for (pos = 1; pos <= 6; pos++) {
least_throws[pos] = 1;
predecessor[pos] = 0;
}

for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
min_throws = MAX_POSITIONS_ON_BOARD;

/*Find how many dice throws are needed to reach pos from any of
the 6 previous cells*/
for (i = 1; i <= 6; ++i) {
prev_pos = pos - i;

if (is_snake[prev_pos])
continue;

/*Pick the minimum throws needed from the 6 previous cells*/
if (least_throws[prev_pos] + 1 < min_throws) {
min_throws = least_throws[prev_pos] + 1;
predecessor[pos] = prev_pos;
}
}

/*Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
from 4 to 14. So number of dice throws needed to reach 14 = number of
dice throws needed to reach position 4*/
}
}

least_throws[pos] = min_throws;
}
return least_throws[MAX_POSITIONS_ON_BOARD];
}

```

Java

```
/*isSnake: if there is a snake at position 20, isSnake[20] is true
if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to
current position with least number of dice throws. If predecessor[100]
= 95, then we reached 100 from 95. It is computed and returned.
Return value: least number of throws to reach the final position on the board
*/
public static int findLeastThrows(boolean[] isSnake, int[] ladder,
int[] predecessor) {
/*for a particular position pos on board, leastThrows[pos] will store
the least number of dice throws required to reach the position*/
int[] leastThrows = new int [MAX_POSITIONS_ON_BOARD + 1];

/*All positions from 1 to 6 can be reached from a single dice throw*/
int pos;
for (pos = 1; pos <= 6; pos++) {
leastThrows[pos] = 1;
predecessor[pos] = 0;
}

for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
int minThrows = MAX_POSITIONS_ON_BOARD;

/*Find how many dice throws are needed to reach pos from any of
the 6 previous cells*/
for (int i = 1; i <= 6; ++i) {
int prevPos = pos - i;

if (isSnake[prevPos])
continue;

/*Pick minimum throws needed from the 6 previous cells*/
if (leastThrows[prevPos] + 1 < minThrows) {
minThrows = leastThrows[prevPos] + 1;
predecessor[pos] = prevPos;
}
}

/*Suppose we are at pos = 14 and ladder[14] = 4, then there is
a ladder from 4 to 14. So number of dice throws needed to reach
14 = number of dice throws needed to reach position 4*/
}
}

leastThrows[pos] = minThrows;
}
return leastThrows[MAX_POSITIONS_ON_BOARD];
}

```

Python

```
#is_snake: if there is a snake at position 20, is_snake[20] is set to True
#	if there is no ladder at location 90 then ladder[90] = -1
#Return value:  1. least number of throws to reach the position on the board
#		2. predecessor list

#for a particular position pos on the board, least_throws[pos] will store
#the least number of dice throws required to reach the position
least_throws = [0] * (MAX_POSITIONS_ON_BOARD + 1)

#predecessor list has the previous board position from where we came to
#current position with least number of dice throws. If predecessor[100]
# = 95, then we reached 100 from 95.
predecessor = [0] * (MAX_POSITIONS_ON_BOARD + 1)

#All positions from 1 to 6 can be reached from a single dice throw
for  pos in range(1, 7):
least_throws[pos] = 1
predecessor[pos] = 0

for  pos in range(7, MAX_POSITIONS_ON_BOARD+1):
min_throws = MAX_POSITIONS_ON_BOARD

#Find how many dice throws are needed to reach pos from any of
#the 6 previous cells
for  i in range(1, 7):
prev_pos = pos - i

if (is_snake[prev_pos]):
continue

#Pick the minimum throws needed from the 6 previous cells
if (least_throws[prev_pos] + 1 < min_throws) :
min_throws = least_throws[prev_pos] + 1
predecessor[pos] = prev_pos

#Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
#from 4 to 14. So number of dice throws needed to reach 14 = number of
#dice throws needed to reach position 4