Snakes and Ladders — BFS on Board State

Problem Statement#

LeetCode 909 — Snakes and Ladders (Medium)

You are given an n x n board. The board cells are numbered from 1 to n², starting from the bottom-left corner and alternating direction each row (Boustrophedon order). Cells contain either -1 (no snake/ladder) or a destination square number.

Starting on square 1, you roll a die (values 1–6). After landing on a square, if it has a snake or ladder (value != -1), you are immediately transported to the destination. Determine the minimum number of dice rolls to reach square n². Return -1 if impossible.

Constraints:

• 2 <= n <= 20
• board[i][j] is -1 or in range [1, n²]
• Square 1 and square n² don't have snakes or ladders

Example 1:

board = [
  [-1,-1,-1,-1,-1,-1],
  [-1,-1,-1,-1,-1,-1],
  [-1,-1,-1,-1,-1,-1],
  [-1, 1,-1,-1,-1,-1],
  [-1,-1,-1,-1,-1,-1],
  [-1,-1,-1,-1,-1,-1]
]
 
Output: 4
Explanation: One minimum path is:
  Roll 2 → square 3
  Roll 6 → square 9 (hits ladder, moves to square 1)... 
  Optimal: use dice wisely to navigate snakes/ladders.

Example 2:

board = [[-1,-1],[-1, 3]]
Output: 1
Explanation: Roll 2 from square 1 to reach square 3 = n² = 4? No, n=2, n²=4.
Roll 3 → square 4. Done in 1 roll.

Example 3:

board = [[-1,-1,-1],[1,-1,-1],[-1,-1,-1]]
Output: 2
Explanation: Square numbering from bottom-left. Roll to navigate in 2 dice rolls.

Why This Problem Matters#

Snakes and Ladders is a deceptively simple-sounding problem that trips up many candidates because of one hidden challenge: converting between square numbers and 2D board coordinates. The board is numbered in Boustrophedon (alternating snake) order — left-to-right on even rows from the bottom, right-to-left on odd rows from the bottom. Getting this mapping wrong produces subtly incorrect answers.

Once the mapping is correct, the underlying algorithm is standard BFS: you are finding the minimum number of moves in an unweighted graph where each node is a square (1 to n²) and edges represent all valid dice outcomes including snake/ladder teleports.

This problem pattern — state-space BFS on a game or puzzle — recurs constantly in interviews. Variations include sliding puzzle (LC 773), open the lock (LC 752), and many others. Mastering the state-space BFS template plus careful index arithmetic makes all of them tractable.

The Core Insight#

The graph is over square numbers (integers 1 to n²), not over (row, col) pairs. From square s, you can move to squares s+1, s+2, ..., s+6. If the destination square has a snake or ladder, you teleport immediately. BFS on this graph finds the minimum number of dice rolls.

The challenging part is the coordinate conversion. For a board of size n:

• Square s (1-indexed) has quotient, remainder = divmod(s-1, n)
• quotient is the row from the bottom (0 = bottom row)
• The board row is n - 1 - quotient (since the board array has row 0 at the top)
• If quotient is even, columns go left-to-right: column = remainder
• If quotient is odd, columns go right-to-left: column = n - 1 - remainder

Visual Dry Run#

n=3 board (square numbers, bottom-up, snake order):
  Row 0 (top):    7  8  9
  Row 1 (middle): 6  5  4
  Row 2 (bottom): 1  2  3
 
Squares 1-3: bottom row, left to right → (row=2, col=0,1,2)
Squares 4-6: middle row, right to left → (row=1, col=2,1,0)
Squares 7-9: top row, left to right   → (row=0, col=0,1,2)
 
BFS from square 1:
  Step 0: queue = [(1, 0)]
  Step 1: from square 1, try +1 to +6 → squares 2,3,4,5,6,7
    Square 9 = n²? Not reachable in one roll from 1 (max is 7)
    Enqueue all unvisited: 2,3,4,5,6,7
  Step 2: from square 7, roll 2 → square 9 = n² → return 2 rolls!

Common Mistakes#

1. Getting the Boustrophedon coordinate mapping wrong. The most common error: forgetting that even-numbered rows (from the bottom) go left-to-right and odd go right-to-left. Off-by-one in divmod or the row flip formula produces wrong positions.

2. Applying the snake/ladder after exceeding n². You must clamp: if s + d > n*n, skip that dice outcome. Don't apply snake/ladder logic to out-of-bounds squares.

3. Not following the snake/ladder chain. The problem says you follow at most one snake/ladder per landing. You do not chain (land → snake → another snake). Just read board[r][c] once and use that as the final destination.

4. Treating the starting square as special. Square 1 is just a starting point. If it has a snake/ladder, you do apply it — but the problem guarantees it won't.

5. Using DFS instead of BFS. DFS can find a path, but only BFS guarantees the minimum number of dice rolls.

6. Visiting duplicate states via different dice rolls. Always mark a square as visited the first time you enqueue it, not when you dequeue it. Otherwise the same square may be enqueued multiple times.

Solutions#

Python#

from collections import deque
 
class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        n = len(board)  # board is n x n
 
        def square_to_pos(s):
            """Convert 1-indexed square number to (row, col) in board array."""
            quot, rem = divmod(s - 1, n)       # quot = distance from bottom row
            row = n - 1 - quot                  # convert to top-indexed row
            col = rem if quot % 2 == 0 else n - 1 - rem  # snake direction
            return row, col
 
        visited = {1}                           # track visited squares
        q = deque([(1, 0)])                     # (square, dice_rolls_so_far)
 
        while q:
            square, rolls = q.popleft()
 
            # Try all 6 dice outcomes from current square
            for d in range(1, 7):
                next_sq = square + d
                if next_sq > n * n:             # can't go past the final square
                    break
 
                r, c = square_to_pos(next_sq)   # find board cell for this square
 
                # Apply snake or ladder if present
                if board[r][c] != -1:
                    next_sq = board[r][c]
 
                # Reached the target square
                if next_sq == n * n:
                    return rolls + 1
 
                # Enqueue if not yet visited
                if next_sq not in visited:
                    visited.add(next_sq)
                    q.append((next_sq, rolls + 1))
 
        return -1  # target square is unreachable

JavaScript#

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    const n = board.length;  // board is n x n
 
    // Convert 1-indexed square number to [row, col] in board array
    function squareToPos(s) {
        const quot = Math.floor((s - 1) / n);  // row index from bottom
        const rem = (s - 1) % n;               // position within that row
        const row = n - 1 - quot;              // flip to top-indexed row
 
        // Even rows from bottom go left-to-right; odd go right-to-left
        const col = quot % 2 === 0 ? rem : n - 1 - rem;
        return [row, col];
    }
 
    const visited = new Set([1]);   // track visited squares by number
    const q = [[1, 0]];            // queue: [square, rolls]
    let head = 0;                   // pointer for efficient dequeue
 
    while (head < q.length) {
        const [square, rolls] = q[head++];  // dequeue
 
        // Try dice values 1 through 6
        for (let d = 1; d <= 6; d++) {
            let nextSq = square + d;
            if (nextSq > n * n) break;      // can't go beyond final square
 
            const [r, c] = squareToPos(nextSq);  // map to board cell
 
            // Follow snake or ladder if present
            if (board[r][c] !== -1) {
                nextSq = board[r][c];
            }
 
            // Check if we reached the target
            if (nextSq === n * n) return rolls + 1;
 
            // Enqueue unvisited squares
            if (!visited.has(nextSq)) {
                visited.add(nextSq);
                q.push([nextSq, rolls + 1]);
            }
        }
    }
 
    return -1;  // could not reach n*n
};

Complexity Analysis#

• Time: There are n² squares. Each square is enqueued and processed at most once. From each square, we explore at most 6 neighbors. Total: O(6 * n²) = O(n²).
• Space: The visited set and BFS queue each hold at most n² entries. The board itself is O(n²) but is given as input.

Follow-up Questions#

1. What if dice can roll 1 to k instead of 1 to 6? The BFS is identical; just loop d from 1 to k. Time complexity becomes O(k * n²).

2. What if snakes and ladders can chain? The problem says they don't, but if they did, you'd need to follow the chain until you reach a cell with no snake/ladder or revisit detection.

3. Find the actual path of moves, not just the count? Store parent pointers: parent[square] = (prev_square, dice_value). Reconstruct by tracing back from n².

4. What if the board is very large (n = 1000)? The BFS approach still works in O(n²) time and space. The coordinate conversion formula doesn't change.

This Pattern Solves#

• LC 752 — Open the Lock — BFS on state space of lock combinations
• LC 773 — Sliding Puzzle — BFS on board permutation states
• LC 127 — Word Ladder — BFS on word state space
• Any minimum moves on a game board problem where the state space is finite and moves are uniform cost

Key Takeaways#

• Snakes and Ladders is a state-space BFS problem — state is a square number (1 to n^2), not a (row, col) pair
• BFS on the square-number state space gives minimum dice rolls because each BFS level = one dice roll
• The Boustrophedon coordinate conversion is the hardest part: use divmod, then flip direction for even rows from bottom
• After converting a square number to (row, col), apply the snake/ladder mapping if one exists at that cell
• Mark states visited before enqueuing (using a visited set or distance array) to avoid reprocessing
• Time O(n^2), space O(n^2) — each of the n^2 squares visited at most once
• State-space BFS template: define state, generate valid next states, BFS for minimum transitions