Solving Snake and Ladder: BFS Graph Algorithm Tutorial
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
This problem is popular in coding interviews as it tests your understanding of graph algorithms, particularly breadth-first search. It's also a fun problem that relates to a game many of us played growing up!
Problem Statement
You are given an n×n board with cells numbered from 1 to n². The game starts from cell 1, and the goal is to reach cell n². You roll a 6-faced dice and move your token by the number shown on the dice.
If your token lands on a cell with the bottom of a ladder, you must climb the ladder to its top. If your token lands on a cell with the head of a snake, you must slide down to the tail of the snake.
Your task is to find the minimum number of dice rolls required to reach the destination (cell n²). If it's not possible to reach the destination, return -1.
Brute Force Approach
Explanation
The simplest way to think about this problem is to try all possible paths from the start to the end and find the one with the minimum dice rolls.
For each position, we have 6 possible moves (rolling 1-6 on the dice). We can use a recursive approach where at each step:
- Try all 6 possible moves
- For each move, check if we land on a ladder or snake and adjust the new position
- Continue the process from each new position
This approach will correctly find the minimum number of dice rolls, but it's extremely inefficient. We would revisit the same positions multiple times, leading to redundant calculations.
Time Complexity: O(6^n), where n is the target position. In the worst case, we make 6 recursive calls at each step.
Space Complexity: O(n) for the recursion stack.
Code (Python)
def min_dice_rolls_brute_force(n, board):
def dfs(position, rolls):
# Base cases
if position == n*n:
return rolls
if position > n*n:
return float('inf')
min_rolls = float('inf')
# Try all 6 possible dice values
for i in range(1, 7):
next_pos = position + i
# Check if next position has a ladder or snake
if next_pos <= n*n and board[next_pos] != -1:
next_pos = board[next_pos]
# Recursive call
rolls_needed = dfs(next_pos, rolls + 1)
min_rolls = min(min_rolls, rolls_needed)
return min_rolls
# Create a board representation where board[i] represents the destination of
# a snake or ladder at position i, or -1 if there is none
game_board = [-1] * (n*n + 1)
for snake_ladder in board:
start, end = snake_ladder
game_board[start] = end
result = dfs(1, 0)
return result if result != float('inf') else -1
Code (C++)
#include <vector>
#include <climits>
#include <unordered_map>
using namespace std;
int minDiceRollsBruteForce(int n, vector<vector<int>>& board) {
// Create a map for snakes and ladders
unordered_map<int, int> snakesAndLadders;
for (const auto& pair : board) {
snakesAndLadders[pair[0]] = pair[1];
}
// Helper function for DFS
function<int(int, int)> dfs = [&](int position, int rolls) {
// Base cases
if (position == n*n) {
return rolls;
}
if (position > n*n) {
return INT_MAX;
}
int minRolls = INT_MAX;
// Try all 6 possible dice values
for (int i = 1; i <= 6; i++) {
int nextPos = position + i;
// Check if next position has a ladder or snake
if (nextPos <= n*n && snakesAndLadders.find(nextPos) != snakesAndLadders.end()) {
nextPos = snakesAndLadders[nextPos];
}
// Recursive call
int rollsNeeded = dfs(nextPos, rolls + 1);
if (rollsNeeded != INT_MAX) {
minRolls = min(minRolls, rollsNeeded);
}
}
return minRolls;
};
int result = dfs(1, 0);
return (result == INT_MAX) ? -1 : result;
}
Code (Java)
import java.util.*;
public class SnakeAndLadder {
public static int minDiceRollsBruteForce(int n, int[][] board) {
// Create a map for snakes and ladders
Map<Integer, Integer> snakesAndLadders = new HashMap<>();
for (int[] pair : board) {
snakesAndLadders.put(pair[0], pair[1]);
}
// Helper function using a recursive method
return dfs(1, 0, n, snakesAndLadders);
}
private static int dfs(int position, int rolls, int n, Map<Integer, Integer> snakesAndLadders) {
// Base cases
if (position == n*n) {
return rolls;
}
if (position > n*n) {
return Integer.MAX_VALUE;
}
int minRolls = Integer.MAX_VALUE;
// Try all 6 possible dice values
for (int i = 1; i <= 6; i++) {
int nextPos = position + i;
// Check if next position has a ladder or snake
if (nextPos <= n*n && snakesAndLadders.containsKey(nextPos)) {
nextPos = snakesAndLadders.get(nextPos);
}
// Recursive call
int rollsNeeded = dfs(nextPos, rolls + 1, n, snakesAndLadders);
if (rollsNeeded != Integer.MAX_VALUE) {
minRolls = Math.min(minRolls, rollsNeeded);
}
}
return minRolls;
}
}
Optimized Approach
Explanation
The key insight for optimizing this problem is to recognize it as a shortest path problem in a graph. We can model the board as a graph where:
- Each cell is a node
- There are edges from each cell to the next 6 cells (representing dice rolls)
- Snakes and ladders are additional edges that allow us to move between non-adjacent cells
Since all edges (dice rolls) have the same weight (1), we can use Breadth-First Search (BFS) to find the shortest path from the start to the end.
BFS visits nodes level by level, so the first time we reach the destination, we're guaranteed to have found the shortest path. This is much more efficient than the brute force approach.
Time Complexity: O(n²), where n² is the total number of cells. We visit each cell at most once.
Space Complexity: O(n²) for the queue and visited set.
BFS (Breadth-First Search) starts at position 1 on the board. In Snake and Ladder, each move represents rolling a dice (1-6) and moving that many positions forward.
From position 1, we can roll a dice (1-6) to reach positions 2, 3, 4, 5, 6, or 7. This forms our first level of the BFS traversal.
Let's assume position 3 has a ladder that takes us to position 22, and position 5 has a snake that drops us to position 2. This changes our graph structure.
When we continue BFS to the second level (a second dice roll), some positions may be visited multiple times through different paths. BFS ensures we find the shortest path to each position.
Code (Python)
from collections import deque
def min_dice_rolls(n, board):
# Create a board representation where board[i] represents the destination of
# a snake or ladder at position i, or -1 if there is none
game_board = [-1] * (n*n + 1)
for snake_ladder in board:
start, end = snake_ladder
game_board[start] = end
# Use BFS to find shortest path
queue = deque([(1, 0)]) # (position, rolls)
visited = set([1])
while queue:
position, rolls = queue.popleft()
# If we've reached the destination
if position == n*n:
return rolls
# Try all possible dice rolls (1-6)
for i in range(1, 7):
next_pos = position + i
# Check if next position is valid
if next_pos > n*n:
continue
# Check if next position has a ladder or snake
if game_board[next_pos] != -1:
next_pos = game_board[next_pos]
# Add to queue if not visited
if next_pos not in visited:
visited.add(next_pos)
queue.append((next_pos, rolls + 1))
# If destination is unreachable
return -1
Code (C++)
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int minDiceRolls(int n, vector<vector<int>>& board) {
// Create a map for snakes and ladders
unordered_map<int, int> snakesAndLadders;
for (const auto& pair : board) {
snakesAndLadders[pair[0]] = pair[1];
}
// Use BFS to find shortest path
queue<pair<int, int>> q; // (position, rolls)
unordered_set<int> visited;
q.push({1, 0});
visited.insert(1);
while (!q.empty()) {
auto [position, rolls] = q.front();
q.pop();
// If we've reached the destination
if (position == n*n) {
return rolls;
}
// Try all possible dice rolls (1-6)
for (int i = 1; i <= 6; i++) {
int nextPos = position + i;
// Check if next position is valid
if (nextPos > n*n) {
continue;
}
// Check if next position has a ladder or snake
if (snakesAndLadders.find(nextPos) != snakesAndLadders.end()) {
nextPos = snakesAndLadders[nextPos];
}
// Add to queue if not visited
if (visited.find(nextPos) == visited.end()) {
visited.insert(nextPos);
q.push({nextPos, rolls + 1});
}
}
}
// If destination is unreachable
return -1;
}
Code (Java)
import java.util.*;
public class SnakeAndLadder {
public static int minDiceRolls(int n, int[][] board) {
// Create a map for snakes and ladders
Map<Integer, Integer> snakesAndLadders = new HashMap<>();
for (int[] pair : board) {
snakesAndLadders.put(pair[0], pair[1]);
}
// Use BFS to find shortest path
Queue<int[]> queue = new LinkedList<>(); // [position, rolls]
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{1, 0});
visited.add(1);
while (!queue.isEmpty()) {
int[] current = queue.poll();
int position = current[0];
int rolls = current[1];
// If we've reached the destination
if (position == n*n) {
return rolls;
}
// Try all possible dice rolls (1-6)
for (int i = 1; i <= 6; i++) {
int nextPos = position + i;
// Check if next position is valid
if (nextPos > n*n) {
continue;
}
// Check if next position has a ladder or snake
if (snakesAndLadders.containsKey(nextPos)) {
nextPos = snakesAndLadders.get(nextPos);
}
// Add to queue if not visited
if (!visited.contains(nextPos)) {
visited.add(nextPos);
queue.offer(new int[]{nextPos, rolls + 1});
}
}
}
// If destination is unreachable
return -1;
}
}The Snake and Ladder problem is a great example of how a real-world game can be modeled as a graph problem. While we can solve it using a recursive, brute force approach by trying all possible dice rolls at each step, this quickly becomes inefficient due to its exponential time complexity.
By recognizing that we're essentially looking for the shortest path in a graph where all edges (dice rolls) have equal weight, we can apply Breadth-First Search to find the solution much more efficiently. The BFS approach has a linear time complexity with respect to the size of the board, making it suitable for solving the problem with larger boards.
This problem shows the importance of:
Identifying the right data structure and algorithm for a given problem
Converting real-world scenarios into abstract models
Optimizing solutions to reduce time complexity
The next time you play Snake and Ladder, you'll know there's an algorithm that can calculate the minimum number of rolls needed to win!
