Snakes and Ladders: BFS on a Board Game

You have an n x n board where squares are numbered from 1 to nn in a boustrophedon pattern (alternating left-to-right and right-to-left, starting from the bottom-left). Some squares have snakes or ladders that instantly transport you to another square. Starting from square 1, you roll a 6-sided die and move forward. Find the minimum number of rolls to reach square nn, or return -1 if it is impossible.

This is LeetCode 909: Snakes and Ladders, and it combines graph traversal with coordinate mapping. The key insight is that the board is just a graph where each square connects to up to 6 forward squares (dice rolls 1 through 6), and snakes/ladders are forced redirections along those edges.

Problem statement

Given an n x n board where board[r][c] equals -1 for normal squares or the destination square for a snake/ladder, return the minimum number of moves to go from square 1 to square n*n. You always start at square 1 (the bottom-left of the board). Each move, you choose a destination square in the range [curr + 1, min(curr + 6, n*n)]. If the destination has a snake or ladder, you must take it. You cannot choose to ignore a snake or ladder.

Approach: BFS on the flattened board

The trick is to think of each square (1 through n*n) as a node in a graph. From any square, you have up to 6 outgoing edges (the 6 possible dice rolls). If the landing square has a snake or ladder, the edge redirects to the snake/ladder destination instead.

The challenge is mapping between the 2D board coordinates and the 1D square numbers. The board uses boustrophedon numbering: row 1 goes left-to-right, row 2 goes right-to-left, row 3 goes left-to-right again, and so on, starting from the bottom of the board.

Here is how to convert a square number s (1-indexed) to board coordinates:

1. Compute the row from the bottom: r = (s - 1) / n
2. Compute the column: c = (s - 1) % n, then flip it on odd rows: if r is odd, c = n - 1 - c
3. Map to the board's row index (since the board is given top-to-bottom): board_row = n - 1 - r

Once you have this mapping, the rest is standard BFS. Start at square 1, explore all reachable squares level by level, and return the distance when you reach square n*n.

from collections import deque

def snakesAndLadders(board):
    n = len(board)

    def get_position(s):
        r, c = divmod(s - 1, n)
        if r % 2 == 1:
            c = n - 1 - c
        return n - 1 - r, c

    visited = set()
    queue = deque([(1, 0)])
    visited.add(1)

    while queue:
        curr, moves = queue.popleft()
        if curr == n * n:
            return moves
        for die in range(1, 7):
            nxt = curr + die
            if nxt > n * n:
                continue
            r, c = get_position(nxt)
            if board[r][c] != -1:
                nxt = board[r][c]
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, moves + 1))
    return -1

Visual walkthrough

Let's trace BFS on a small 6x6 board with ladders at squares 3, 11, and 20, and snakes at squares 16 and 33. Watch how ladders let BFS skip large sections of the board, reaching the end in fewer moves than a snake-free path would require.

The key observation: ladders act as shortcuts that let BFS jump ahead many squares in a single move. Snakes are obstacles that would send you backward, so BFS avoids paths through snake heads by finding alternate routes. Because BFS explores all states at distance d before distance d+1, the first time it reaches square n*n is guaranteed to be the minimum number of rolls.

Complexity analysis

The BFS visits each square at most once and does constant work per square (checking 6 dice outcomes). The coordinate mapping is O(1) per call. So the total time and space are both proportional to the number of squares on the board.

Building blocks

1. BFS shortest path on an implicit graph

The core pattern is standard unweighted shortest-path BFS:

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

while queue:
    state, dist = queue.popleft()
    if state == target:
        return dist
    for neighbor in get_neighbors(state):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append((neighbor, dist + 1))

This template works for any problem where you need the minimum number of steps between two states in an unweighted graph. The only variation between problems is how you define neighbors.

2. Boustrophedon coordinate mapping

The board-specific logic is the get_position function. The pattern for converting a 1-indexed position to 2D coordinates on an alternating-direction grid:

def get_position(s):
    r, c = divmod(s - 1, n)
    if r % 2 == 1:
        c = n - 1 - c
    return n - 1 - r, c

The divmod gives you the row-from-bottom and column. The odd-row flip handles the alternating direction. The n - 1 - r converts from bottom-up indexing to the top-down indexing that the board array uses.

3. Forced edge redirection

When a destination square has a snake or ladder, you do not stay there. You follow the redirection immediately:

r, c = get_position(nxt)
if board[r][c] != -1:
    nxt = board[r][c]

This means your BFS only ever enqueues the final destination after following any snake/ladder. You never "visit" the intermediate square where the snake/ladder sits, you only visit where it takes you.

Edge cases

• Square 1 has a snake or ladder: The problem guarantees board[n-1][0] is -1, so square 1 is always a normal square. No special handling needed.
• Square n*n has a snake or ladder: Similarly guaranteed to be -1. The destination is always a normal square.
• Multiple snakes/ladders in sequence: You only follow one redirection per landing. The problem states that a destination of a snake/ladder is always a normal square (no chaining).
• Board is unreachable: If snakes create a cycle or block all paths, BFS exhausts the queue and returns -1.
• Minimum board size: The smallest valid board is 2x2 with 4 squares. BFS from 1 reaches 4 in a single roll.
• Die roll would exceed n*n: Skip any curr + die that goes past the final square. You cannot overshoot.

From understanding to recall

You have seen how BFS on the flattened board solves Snakes and Ladders. The boustrophedon coordinate mapping, the forced redirections for snakes and ladders, the standard BFS template. It all makes sense when you read through it. But in an interview, you need to write the get_position function with its divmod, odd-row flip, and row inversion from memory.

Spaced repetition makes those details automatic. CodeBricks drills the coordinate-mapping building block and the BFS-with-redirections pattern independently. You type each piece from scratch at increasing intervals until the conversion logic and BFS structure flow out without hesitation. When a board traversal problem appears in your interview, you do not pause to work out the indexing on a whiteboard. You just write it.

Related posts

• Number of Islands - Grid BFS/DFS traversal showing how 2D structures become implicit graphs
• Open the Lock - BFS on a state-space graph with blocked states, the same "minimum moves" pattern
• Word Ladder - Another BFS shortest path problem where each state has multiple neighbors to explore