The Snake and Ladder Problem is a classic graph traversal problem. Although it looks like a board-game simulation, the key observation is that we can model every cell as a node in a graph and every dice throw as an edge.
The goal is to find the minimum number of dice throws required to travel from cell 1 to cell n × n.
1. Understanding the Problem
We are given:
n— size of the board.lad[]— pairs representing ladders.lad[0] → lad[1]lad[2] → lad[3]and so on.
sn[]— pairs representing snakes.sn[0] → sn[1]sn[2] → sn[3]and so on.
For example:
lad = [3, 22, 5, 8]
means:
3 → 22
5 → 8
If we land on 3, we immediately move to 22.
If we land on the start of a snake, we immediately move down.
We control the dice result, so on every throw we can choose any value from 1 to 6.
2. Why BFS?
The important part of the problem is:
Find the minimum number of moves.
This is exactly what Breadth-First Search (BFS) is designed for.
Imagine each cell is a node:
1 → 2
1 → 3
1 → 4
1 → 5
1 → 6
1 → 7
From cell 1, one dice throw can take us to any cell from 2 to 7.
Each dice throw has the same cost:
1 throw
So we can perform BFS.
BFS explores:
0 throws
↓
1 throw
↓
2 throws
↓
3 throws
↓
...
Therefore, when BFS reaches n*n for the first time, that is guaranteed to be the minimum number of throws.
3. Representing Snakes and Ladders
Instead of repeatedly searching through lad[] and sn[], we create an array:
int[] jump = new int[total + 1];
Here:
jump[start] = destination
For example:
lad = [3, 22, 5, 8]
becomes:
jump[3] = 22
jump[5] = 8
Similarly, if:
sn = [17, 4, 19, 7]
we have:
jump[17] = 4
jump[19] = 7
This makes checking a snake or ladder very fast.
4. Complete Java Solution
import java.util.*;
class Solution {
public int minThrows(int n, int[] lad, int[] sn) {
int total = n * n;
// jump[i] stores the destination of a snake/ladder
int[] jump = new int[total + 1];
// Store ladders
for (int i = 0; i < lad.length; i += 2) {
jump[lad[i]] = lad[i + 1];
}
// Store snakes
for (int i = 0; i < sn.length; i += 2) {
jump[sn[i]] = sn[i + 1];
}
// visited[i] tells whether cell i has already been visited
boolean[] visited = new boolean[total + 1];
Queue<Integer> queue = new LinkedList<>();
// Start from cell 1
queue.offer(1);
visited[1] = true;
int throwsCount = 0;
while (!queue.isEmpty()) {
int size = queue.size();
// Process all cells reachable using throwsCount throws
while (size-- > 0) {
int current = queue.poll();
// Destination reached
if (current == total) {
return throwsCount;
}
// Try dice values 1 to 6
for (int dice = 1; dice <= 6; dice++) {
int next = current + dice;
// Cannot go beyond the last cell
if (next > total) {
break;
}
// Take snake or ladder immediately
if (jump[next] != 0) {
next = jump[next];
}
// Visit this cell if not visited before
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
throwsCount++;
}
// Destination cannot be reached
return -1;
}
}
5. Step-by-Step Explanation
Step 1: Calculate the last cell
int total = n * n;
If:
n = 6
then the board contains:
6 × 6 = 36
cells.
So our destination is:
36
Step 2: Create the jump array
int[] jump = new int[total + 1];
We use total + 1 because the cells are numbered from 1 to total.
For a 6 × 6 board:
jump[1]
jump[2]
...
jump[36]
Cell 0 is unused.
Step 3: Store ladders
for (int i = 0; i < lad.length; i += 2) {
jump[lad[i]] = lad[i + 1];
}
Suppose:
lad = [3, 22, 5, 8, 11, 35, 20, 32];
The loop creates:
jump[3] = 22
jump[5] = 8
jump[11] = 35
jump[20] = 32

Join the conversation! Your thoughts help the community grow.