Snakes and Ladders

• Difficulty: Medium
• Topics: Array, Breadth-First Search, Matrix
• Link: https://leetcode.com/problems/snakes-and-ladders/

Problem Description

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

• Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
  • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
• If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
• The game ends when you reach the square n2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

• For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square n2. If it is not possible to reach the square, return -1.

Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints:

• n == board.length == board[i].length
• 2 <= n <= 20
• board[i][j] is either -1 or in the range [1, n2].
• The squares labeled 1 and n2 are not the starting points of any snake or ladder.

Solution

1. Problem Deconstruction

Technical Restatement: Given an n×n matrix representing a Snakes and Ladders board with Boustrophedon cell numbering, implement a single-source shortest path algorithm from cell 1 to cell n² where:

• Each move consists of rolling a fair 6-sided die (1-6 positions forward)
• If the destination cell contains a snake/ladder (value ≠ -1), you must immediately teleport to the indicated cell
• No recursive snake/ladder following occurs
• Return the minimum dice rolls required to reach n², or -1 if unreachable

Beginner Explanation: Imagine a board game where you start at position 1. Each turn, you roll a die and move forward 1-6 spaces. If you land on a ladder, you climb up; if you land on a snake, you slide down. Your goal is to reach the final square in the fewest rolls possible. The board is numbered in a zigzag pattern - left to right on one row, then right to left on the next.

Mathematical Formulation: Let:

• $V = \{1, 2, ..., n^2\}$ (vertices/cells)
• For each $v \in V$, define edges $v \rightarrow w$ where:
  • $w = \min(v + d, n^2)$ for $d \in \{1,...,6\}$
  • If $board[r(w)] \neq -1$, then $w \leftarrow board[r(w)]$
• Find shortest path length from $1$ to $n^2$ in unweighted directed graph

Constraint Analysis:

• $2 \leq n \leq 20$ → $4 \leq n^2 \leq 400$ vertices
  • Enables $O(n^4)$ solutions comfortably
  • BFS ($O(V+E)$) with $V=400$, $E \leq 2400$ is efficient
• Board values either -1 or $[1, n^2]$
  • No out-of-bounds destinations
  • Values form valid teleports within board
• Cells 1 and n² cannot be snake/ladder starts
  • No immediate teleports from start/end
  • Simplifies boundary conditions

Hidden Edge Cases:

• Direct path with no snakes/ladders (simple die rolls)
• All cells except start/end are snakes/ladders
• Snake that creates cycle (e.g., position 5 → 3, position 3 → 5)
• Ladders that skip over snakes
• Maximum board size (n=20, 400 cells) with complex snake patterns

---

2. Intuition Scaffolding

Real-World Metaphor: Like navigating a subway system with express trains (ladders) and detours (snakes). You can only travel 1-6 stops at a time, but if you land on an express station, you’re instantly transported to another station. You want the fewest number of train rides to reach your destination.

Gaming Analogy: Think of a platformer game with warp pipes (ladders) and pitfalls (snakes). Each move you can jump 1-6 platforms forward. If you land on a warp pipe, you’re teleported elsewhere. Find the minimum jumps to beat the level.

Math Analogy: Model as a directed graph where each node connects to up to 6 subsequent nodes, with certain nodes having additional edges to distant nodes. Find the shortest path in this augmented graph.

Common Pitfalls:

1. Greedy ladder chasing - Always taking the farthest ladder may lead to snakes
2. Ignoring cycles - Snake-ladder loops can cause infinite recursion
3. Over-complicating moves - Each die roll allows only one teleport max
4. Misindexing cells - Boustrophedon numbering is tricky to implement
5. BFS vs DFS choice - BFS naturally finds shortest path in unweighted graphs

---

3. Approach Encyclopedia

Brute Force (Theoretical):

def snakesAndLadders(board):
    n = len(board)
    target = n * n
    
    def dfs(cell, rolls):
        if cell == target:
            return rolls
        if rolls > n * n:  # Prevent infinite loops
            return float('inf')
        
        min_rolls = float('inf')
        for die in range(1, 7):
            next_cell = cell + die
            if next_cell > target:
                continue
            
            # Convert to board coordinates
            r, c = get_coordinates(next_cell, n)
            if board[r][c] != -1:
                next_cell = board[r][c]
            
            min_rolls = min(min_rolls, dfs(next_cell, rolls + 1))
        
        return min_rolls
    
    result = dfs(1, 0)
    return result if result != float('inf') else -1

Complexity: $O(6^{n^2})$ - Exponential explosion makes this infeasible

Optimized BFS Approach:

from collections import deque

def snakesAndLadders(board):
    n = len(board)
    target = n * n
    
    def get_coordinates(cell):
        # Convert 1-based cell number to 0-based board coordinates
        row = (cell - 1) // n
        col = (cell - 1) % n
        if row % 2 == 1:  # Reverse for odd rows (Boustrophedon)
            col = n - 1 - col
        return n - 1 - row, col  # Board is bottom-up
    
    visited = [False] * (target + 1)
    queue = deque([(1, 0)])  # (cell, rolls)
    visited[1] = True
    
    while queue:
        cell, rolls = queue.popleft()
        
        if cell == target:
            return rolls
        
        for die in range(1, 7):
            next_cell = cell + die
            if next_cell > target:
                break
            
            r, c = get_coordinates(next_cell)
            if board[r][c] != -1:
                next_cell = board[r][c]
            
            if not visited[next_cell]:
                visited[next_cell] = True
                queue.append((next_cell, rolls + 1))
    
    return -1

Complexity Proof:

• Time: $O(n^2)$ - Each cell visited at most once
• Space: $O(n^2)$ - Queue and visited array storage
• Vertex count: $V = n^2$
• Edge count: $E \leq 6n^2$ (each cell connects to ≤6 others)

Visualization:

Board: 6×6, Target: 36
Boustrophedon numbering:
36 35 34 33 32 31
25 26 27 28 29 30
24 23 22 21 20 19
13 14 15 16 17 18
12 11 10 09 08 07
01 02 03 04 05 06

BFS Exploration:
Level 0: [1]
Level 1: [2,3,4,5,6,7] (die rolls 1-6)
Level 2: From each level 1 cell, explore +1..+6
...

---

4. Code Deep Dive

from collections import deque

def snakesAndLadders(board):
    n = len(board)
    target = n * n
    
    def get_coordinates(cell):
        # Convert linear position to board coordinates
        # Row calculation: cells are filled bottom-up
        row = (cell - 1) // n
        # Column calculation: alternating direction
        col = (cell - 1) % n
        # Reverse columns for odd rows (0-indexed from top)
        if row % 2 == 1:
            col = n - 1 - col
        # Convert to board's coordinate system (0 at top)
        return n - 1 - row, col
    
    visited = [False] * (target + 1)
    queue = deque()
    queue.append((1, 0))  # Start at cell 1 with 0 rolls
    visited[1] = True
    
    while queue:
        current, rolls = queue.popleft()
        
        # Success condition
        if current == target:
            return rolls
        
        # Explore all 6 possible die outcomes
        for die in range(1, 7):
            next_cell = current + die
            
            # Bound check
            if next_cell > target:
                continue
            
            # Convert to board coordinates and check for snakes/ladders
            r, c = get_coordinates(next_cell)
            if board[r][c] != -1:
                next_cell = board[r][c]
            
            # Avoid revisiting cells
            if not visited[next_cell]:
                visited[next_cell] = True
                queue.append((next_cell, rolls + 1))
    
    return -1

Edge Case Handling:

• Example 1: Direct path with strategic ladder usage
  • Line 32-34: Detects ladder at position 2 → teleports to 15
  • Line 27-29: Prevents overshooting target
• Snake cycles: Visited array prevents infinite loops
• Maximum board: Efficient BFS handles n=20 case
• No solution: While loop exits naturally, returns -1

---

5. Complexity War Room

Hardware-Aware Analysis:

• 400 cells × 6 edges = 2400 operations
• ~20KB for visited array (400 booleans + overhead)
• Fits comfortably in L1 cache (typical 32-64KB)
• Queue operations negligible for modern CPUs

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute DFS	$O(6^{n^2})$	$O(n^2)$	8/10	❌ Exponential
BFS	$O(n^2)$	$O(n^2)$	9/10	✅ Optimal
Dijkstra	$O(n^2 \log n)$	$O(n^2)$	7/10	⚠️ Overkill
DP	$O(n^2)$	$O(n^2)$	6/10	⚠️ Complex state

---

6. Pro Mode Extras

Variants Section:

1. Multiple Dice Rolls (LC 909): Standard version
2. Weighted Snakes/Ladders: Use Dijkstra instead of BFS
3. Probability Version: Markov chains to compute expected rolls
4. k Snakes/Ladders Limit: DP with state (cell, snakes_used)
5. Two Players: Game theory with minimax

Interview Cheat Sheet:

• First Mention: “BFS is optimal for unweighted shortest path”
• Key Insight: “Snakes/ladders create additional edges in the graph”
• Common Trap: “Remember the Boustrophedon numbering conversion”
• Testing Strategy: “Verify with the provided examples first”
• Optimization: “Early termination when reaching target”
• Extension Ready: “This approach generalizes to any board configuration”