Snakes and Ladders

Snakes and Ladders looks like a board game, but it is really a shortest-path problem in disguise. Once you see each square as a node and each die roll as an edge, the answer falls out of plain BFS.

The slow way first

You could try every sequence of rolls and keep the shortest that reaches the end. But the number of roll sequences explodes exponentially, and many of them revisit the same square. Tracking "what is the fewest rolls to reach this square" by brute force re-computes the same answers over and over.

The question to ask: what does each turn really do? A single roll takes you from one square to one of the next six squares (after applying any snake or ladder). That is exactly a graph edge.

The idea: squares are nodes, rolls are edges

Build the graph implicitly. From square s, the neighbors are s+1, s+2, ..., s+6, except a neighbor that holds a snake or ladder is replaced by its destination. Every edge costs one roll, so the fewest rolls to reach the goal is the shortest path in an unweighted graph — and BFS solves that.

Because BFS visits nodes in order of distance, the first time we dequeue the final square, its level is guaranteed to be the minimum number of rolls.

Walk through it

Step through the animation. Square 1 is the BFS root at distance 0. One roll expands to squares 3..8 — landing on 2 takes the ladder to 8, landing on 7 takes the snake to 4. Square 8 is now reachable in one roll, so a single roll from 8 reaches square 9. We dequeue 9 at distance 2, and that is the answer.

Pseudocode

queue = [(square 1, rolls 0)]
visited = {1}
while queue is not empty:
    square, rolls = pop front of queue
    if square is the last square:
        return rolls
    for nxt in square+1 .. min(square+6, last):
        dest = the snake/ladder target of nxt, else nxt itself
        if dest not visited:
            mark dest visited
            add (dest, rolls + 1) to the queue
return -1                     # goal can never be reached

The Python solution

def snakes_and_ladders(board):
    n, target = len(board), len(board) * len(board)
    queue = [(1, 0)]            # (square, rolls)
    visited = {1}
    while queue:
        square, rolls = queue.pop(0)
        if square == target:
            return rolls
        for nxt in range(square + 1, min(square + 6, target) + 1):
            dest = jump[nxt] if nxt in jump else nxt
            if dest not in visited:
                visited.add(dest)
                queue.append((dest, rolls + 1))
    return -1

• queue holds (square, rolls) pairs — a standard BFS frontier ordered by distance.
• visited stops us from re-expanding a square, which is what keeps BFS linear.
• The for nxt loop enumerates the six edges of one die roll, capped at the final square.
• dest = jump[nxt] ... applies a snake or ladder by redirecting the landing square.
• The first dequeued square equal to target returns the fewest rolls, because BFS dequeues in distance order.

Complexity

There are n² squares and at most six outgoing edges per square, so BFS does O(n²) work. The visited set and queue each hold up to n² squares, giving O(n²) space.

When this pattern shows up

Practice