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:
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
So whenever we land on one of these cells, we know where to move immediately.
6. Store Snakes
for (int i = 0; i < sn.length; i += 2) {
jump[sn[i]] = sn[i + 1];
}
For:
sn = [17, 4, 19, 7, 34, 1, 21, 9];
we get:
jump[17] = 4
jump[19] = 7
jump[34] = 1
jump[21] = 9
So:
17 → 4
19 → 7
34 → 1
21 → 9
7. Why Do We Need visited[]?
We create:
boolean[] visited = new boolean[total + 1];
Without visited, we might visit the same cell many times.
For example:
1 → 2
1 → 3
2 → 3
Cell 3 can be reached from both 1 and 2.
Once we have visited 3, there is no need to process it again because BFS guarantees that the first time we reach a cell is through the minimum number of throws.
Therefore:
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
8. Starting BFS
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
visited[1] = true;
We start at:
Cell 1
So the queue initially contains:
[1]
And:
int throwsCount = 0;
means we have made zero throws.
9. Processing the Queue
while (!queue.isEmpty()) {
As long as there are cells to process, BFS continues.
We use:
int size = queue.size();
This is important because all cells currently in the queue are reachable using the same number of throws.
For example:
After 1 throw:
2 3 4 5 6 7
We process all of them before increasing throwsCount.
10. Trying All Dice Values
The most important part is:
for (int dice = 1; dice <= 6; dice++) {
int next = current + dice;
Because we control the dice, we can choose:
1
2
3
4
5
6
For example, if:
current = 8
then possible next cells are:
8 + 1 = 9
8 + 2 = 10
8 + 3 = 11
8 + 4 = 12
8 + 5 = 13
8 + 6 = 14
11. Handling Snakes and Ladders
After calculating the next cell:
if (jump[next] != 0) {
next = jump[next];
}
Suppose:
current = 8
dice = 3
Then:
next = 11
If there is a ladder:
11 → 35
then:
next = 35;
So the move becomes:
8 --(dice 3)--> 11 --(ladder)--> 35
The ladder does not require an additional dice throw.
12. Example Walkthrough
Consider:
n = 6
lad = [3,22, 5,8, 11,35, 20,32]
sn = [17,4, 19,7, 34,1, 21,9]
The optimal solution is:
1 → 5 → 8
ladder
8 → 11 → 35
ladder
35 → 36
Throw 1
Choose:
dice = 4
Move:
1 → 5
There is a ladder:
5 → 8
So we immediately reach:
8
Throws:
1
Throw 2
Choose:
dice = 3
Move:
8 → 11
There is a ladder:
11 → 35
So we reach:
35
Throws:
2
Throw 3
Choose:
dice = 1
Move:
35 → 36
Destination reached.
Therefore:
Answer = 3
13. Why Not DFS?
We could use DFS to explore paths, but DFS does not naturally guarantee the shortest path.
For example, DFS might find:
1 → 2 → 3 → 4 → ... → 36
using many throws before discovering a much shorter path.
BFS instead explores by distance:
0 throws
1 throw
2 throws
3 throws
...
So BFS is the natural choice.
14. Why Does BFS Give the Minimum?
Every dice throw has exactly the same cost:
1 throw
We can think of the board as an unweighted graph.
For example:
2
↗
1 → 3
↘
4
Every edge represents one dice throw.
BFS finds the shortest path in an unweighted graph.
Therefore:
Minimum dice throws
=
Shortest path from cell 1 to cell n*n
15. Why Is the Answer Sometimes -1?
The problem may contain snakes that create cycles or prevent us from progressing toward the destination.
If BFS finishes and the destination was never reached:
return -1;
This means there is no possible sequence of dice throws that reaches n*n.
16. Complexity Analysis
Let:
N = n²
There are N cells.
For every cell, we try at most 6 dice values:
1, 2, 3, 4, 5, 6
Therefore:
Time Complexity = O(6 × N)
= O(N)
= O(n²)
The arrays and queue can contain up to N cells:
Space Complexity = O(N)
= O(n²)
So the solution satisfies the expected complexity:
Time : O(n²)
Space : O(n²)
Final Takeaway
The main idea to remember for this problem is:
Snake and Ladder is a shortest-path problem on an unweighted graph, so use BFS.
The algorithm is:
1. Create a jump[] array for snakes and ladders.
2. Start BFS from cell 1.
3. For every cell, try dice values 1 through 6.
4. Apply a snake/ladder immediately after landing.
5. Mark cells as visited.
6. The first time we reach n*n, return the number of throws.
7. If BFS ends without reaching n*n, return -1.
This approach is simple, efficient, and directly matches the O(n²) expected complexity.