Snakes and Ladders BFS — Shortest Path on Game Board (LeetCode 909)

Snakes and Ladders (LeetCode 909) is a BFS problem disguised as a board game. You need to find the minimum number of dice rolls to reach the final square. The tricky part is converting between the board’s 2D layout and 1D square numbers.

The Problem

Given an n x n board with snakes and ladders, find the minimum number of moves to reach square n*n starting from square 1.

• Each move: roll a die (1 to 6) and move forward
• If you land on a snake or ladder, you must take it (teleport to the destination)
• Board uses boustrophedon numbering (alternating left-right, right-left per row, starting from bottom-left)
• board[r][c] = -1 means no snake/ladder; otherwise board[r][c] is the destination

Why BFS?

Each square on the board is a node. From each node, you have up to 6 edges (dice rolls 1-6). BFS explores all nodes reachable in 1 move, then 2 moves, and so on. The first time you reach square n*n, that is the minimum number of moves.

This is unweighted shortest path — exactly what BFS is designed for.

The 1D-to-2D Conversion

The board is numbered bottom-to-top with alternating direction per row (boustrophedon pattern). Given a 1-indexed square number s on an n x n board:

def square_to_coords(s, n):
    """Convert 1-indexed square number to (row, col) in the 2D board."""
    # Row from bottom (0-indexed)
    row_from_bottom = (s - 1) // n
    col = (s - 1) % n

    # Odd rows from bottom go right-to-left
    if row_from_bottom % 2 == 1:
        col = n - 1 - col

    # Convert to top-indexed row for the board array
    row = n - 1 - row_from_bottom

    return row, col

Example for a 6x6 board:

Square 1  → row_from_bottom=0, col=0 → board row 5, col 0
Square 6  → row_from_bottom=0, col=5 → board row 5, col 5
Square 7  → row_from_bottom=1, col=0 → zigzag: col=5 → row 4, col 5
Square 12 → row_from_bottom=1, col=5 → zigzag: col=0 → row 4, col 0
Square 36 → row_from_bottom=5, col=5 → zigzag: col=0 → row 0, col 0

Python BFS Implementation

from collections import deque

def snakes_and_ladders(board):
    """
    BFS to find minimum dice rolls to reach the last square.
    Time: O(n^2) — each square visited at most once.
    Space: O(n^2) — for visited set and queue.
    """
    n = len(board)
    target = n * n

    def get_board_value(s):
        """Get board value at 1-indexed square s."""
        row_from_bottom = (s - 1) // n
        col = (s - 1) % n
        if row_from_bottom % 2 == 1:
            col = n - 1 - col
        row = n - 1 - row_from_bottom
        return board[row][col]

    # BFS
    queue = deque([(1, 0)])  # (square, moves)
    visited = {1}

    while queue:
        square, moves = queue.popleft()

        # Try all dice rolls
        for dice in range(1, 7):
            next_sq = square + dice
            if next_sq > target:
                continue

            # Check for snake or ladder
            val = get_board_value(next_sq)
            if val != -1:
                next_sq = val  # teleport

            if next_sq == target:
                return moves + 1

            if next_sq not in visited:
                visited.add(next_sq)
                queue.append((next_sq, moves + 1))

    return -1  # unreachable

Step-by-Step Trace

Consider a simplified 3x3 board:

board = [
    [-1, -1,  9],   # row 0: squares 9, 8, 7
    [-1, -1, -1],   # row 1: squares 4, 5, 6
    [-1, -1, -1],   # row 2: squares 1, 2, 3
]

Square 7 has a ladder to square 9 (board[0][2] = 9).

Target = 9

BFS:
  Start: queue=[(1,0)], visited={1}

  Process (1, 0):
    dice 1 → sq 2, val=-1, not visited → queue=[(2,1)], visited={1,2}
    dice 2 → sq 3, val=-1 → queue=[(2,1),(3,1)], visited={1,2,3}
    dice 3 → sq 4, val=-1 → add (4,1)
    dice 4 → sq 5, val=-1 → add (5,1)
    dice 5 → sq 6, val=-1 → add (6,1)
    dice 6 → sq 7, val=9 → next_sq=9 → TARGET! return 0+1 = 1

Answer: 1 (roll a 6, land on 7 which has ladder to 9)

Handling Edge Cases

What if a snake/ladder destination has another snake/ladder?

Per LeetCode’s rules, you only take one snake/ladder per move. If you land on square X that sends you to Y, you stay at Y even if Y has its own snake/ladder. The BFS naturally handles this because Y will be processed in a future move.

What about landing beyond the board?

If square + dice > n*n, skip that dice roll. You cannot move beyond the last square.

Complete Solution with All Edge Cases

from collections import deque

def snakes_and_ladders(board):
    n = len(board)
    target = n * n

    def get_value(s):
        r = (s - 1) // n
        c = (s - 1) % n
        if r % 2 == 1:
            c = n - 1 - c
        return board[n - 1 - r][c]

    queue = deque([(1, 0)])
    visited = {1}

    while queue:
        sq, moves = queue.popleft()

        for d in range(1, 7):
            nxt = sq + d
            if nxt > target:
                continue

            val = get_value(nxt)
            if val != -1:
                nxt = val

            if nxt == target:
                return moves + 1

            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, moves + 1))

    return -1

Common Mistakes

1. Wrong 1D-to-2D conversion — forgetting the zigzag pattern or getting row direction wrong
2. Not handling the target check after teleport — you can land on the target via a ladder
3. Visiting the pre-teleport square instead of post — mark the final destination as visited
4. Allowing multiple teleports in one move — per problem rules, at most one
5. Off-by-one errors — squares are 1-indexed, board array is 0-indexed

Complexity Analysis

Metric	Value
Time	O(n^2) — each of the n^2 squares visited at most once
Space	O(n^2) — visited set + queue

The BFS visits each square at most once. From each square, we do constant work (6 dice rolls). Total: O(6 * n^2) = O(n^2).

When to Use This Pattern

Use BFS shortest path when:

• You need the minimum number of steps/moves to reach a target
• The graph is unweighted (each step costs the same)
• There are teleportation mechanics (snakes, ladders, portals)
• The state space is finite and can be enumerated

Related Problems

Problem	Difficulty	Key Idea
LeetCode 909 — Snakes and Ladders	Medium	This problem
LeetCode 127 — Word Ladder	Hard	BFS shortest transformation
LeetCode 1091 — Shortest Path in Binary Matrix	Medium	BFS on grid
LeetCode 752 — Open the Lock	Medium	BFS on state space

Key Takeaway

Snakes and Ladders is BFS on a graph where nodes are board squares and edges are dice rolls (possibly modified by snakes/ladders). The hardest part is the 1D-to-2D boustrophedon conversion. Once you model the board correctly, standard BFS gives you the answer.