Snake and Ladders Problem
Problem Statement
Given a Snakes and Ladders board of size N×N, find the minimum number of dice throws required to reach the last cell from the first cell. Snakes take you down and ladders take you up. You can roll a die value from 1 to 6 in each throw.
Example:
- Input: Board size = 30, Ladders:
{2→21, 4→7, 10→25, 19→28}, Snakes:{26→0, 20→8, 16→3, 18→6} - Output:
3(minimum dice throws to reach cell 30)
Noob-Friendly Explanation
Think of the board game Snakes and Ladders. You start at square 1 and want to reach the last square. Each turn you roll a die (1 to 6) and move forward. If you land on a ladder, you climb up. If you land on a snake, you slide down. We want to find the fewest rolls needed to reach the end.
This is like finding the shortest path in a graph. Each cell is a node, and each dice roll creates edges to 6 possible next cells. BFS finds the shortest path!
Approach 1: Brute Force (Recursive)
Intuition
Try all possible dice rolls from each cell recursively. Track the minimum number of rolls needed to reach the destination.
Algorithm
- Start from cell 0.
- For each cell, try rolling 1 to 6.
- If the destination cell has a snake or ladder, follow it.
- Recursively find the minimum throws from the new cell.
- Return the minimum across all choices.
import java.util.*;
public class SnakeLadderBrute {
static int minThrows;
public static int solve(int[] board, int n) {
minThrows = Integer.MAX_VALUE;
boolean[] visited = new boolean[n];
dfs(board, 0, n - 1, 0, visited);
return minThrows;
}
static void dfs(int[] board, int curr, int target, int throws_, boolean[] visited) {
if (curr == target) {
minThrows = Math.min(minThrows, throws_);
return;
}
if (throws_ >= minThrows) return; // prune
visited[curr] = true;
for (int die = 1; die <= 6; die++) {
int next = curr + die;
if (next > target) continue;
int dest = board[next] != -1 ? board[next] : next;
if (!visited[dest]) {
dfs(board, dest, target, throws_ + 1, visited);
}
}
visited[curr] = false;
}
public static void main(String[] args) {
int n = 30;
int[] board = new int[n];
Arrays.fill(board, -1);
// Ladders
board[2] = 21;
board[4] = 7;
board[10] = 25;
board[19] = 28;
// Snakes
board[26] = 0;
board[20] = 8;
board[16] = 3;
board[18] = 6;
System.out.println("Min throws (brute): " + solve(board, n));
}
}Complexity Analysis
- Time Complexity: O(6^N) - in the worst case we explore 6 branches at each cell
- Space Complexity: O(N) - recursion stack and visited array
Approach 2: Optimal (BFS)
Intuition
Model the board as a graph where each cell is a node and dice rolls are edges. BFS from cell 0 gives the shortest path (fewest throws) to reach the last cell, because BFS explores nodes level by level (each level = one throw).
Algorithm
- Create a queue and enqueue cell 0 with 0 throws.
- Mark cell 0 as visited.
- Dequeue a cell, try all 6 dice values.
- If a destination has a snake/ladder, follow it.
- If the destination is the target, return the current throws + 1.
- Otherwise, enqueue the destination if not visited.
import java.util.*;
public class SnakeLadderBFS {
public static int minThrows(int[] board, int n) {
boolean[] visited = new boolean[n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0}); // {cell, throws}
visited[0] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int cell = curr[0];
int throws_ = curr[1];
for (int die = 1; die <= 6; die++) {
int next = cell + die;
if (next >= n) continue;
int dest = board[next] != -1 ? board[next] : next;
if (dest == n - 1) return throws_ + 1;
if (!visited[dest]) {
visited[dest] = true;
queue.offer(new int[]{dest, throws_ + 1});
}
}
}
return -1; // unreachable
}
public static void main(String[] args) {
int n = 30;
int[] board = new int[n];
Arrays.fill(board, -1);
// Ladders
board[2] = 21;
board[4] = 7;
board[10] = 25;
board[19] = 28;
// Snakes
board[26] = 0;
board[20] = 8;
board[16] = 3;
board[18] = 6;
System.out.println("Min throws: " + minThrows(board, n));
}
}Complexity Analysis
- Time Complexity: O(N) - each cell is visited at most once, and for each cell we check 6 neighbours
- Space Complexity: O(N) - for the visited array and queue