Snakes and Ladders

Problem

You’re given an n x n board. The cells are numbered 1 to n² in a boustrophedon (“ox-plowing”) layout: numbering starts at the bottom-left corner, runs left-to-right along the bottom row, then the direction flips on each row moving upward.

You start on cell 1. On each move you roll a die and advance to any cell in [current + 1, current + 6] that exists on the board. If that landing cell holds a snake or ladder, you immediately move to its destination — but you take at most one snake/ladder per move (you do not chain into a second one from the destination).

board[r][c] is -1 for an ordinary cell, or the destination cell number of a snake/ladder. Return the least number of moves to reach cell n², or -1 if it’s unreachable.

Examples

• board = [[-1,-1],[-1,3]] → 1 — cell 2 is a ladder to 3, but from cell 1 you can also roll a 3 straight to cell 4 (n²) in one move.
• 6×6 board with board[5][1]=15 (cell 2→15), board[3][1]=35 (cell 14→35), board[3][4]=13 (cell 17→13) → 4 — 1 →2(↑15) →17(↓13) →14(↑35) →36.
• board = [[-1,-1,-1],[-1,9,8],[-1,8,9]] → 1 — from cell 1, reaching cell 2 or beyond and taking a ladder lands you on 9 (n²) in one move.

Constraints

• 2 <= n <= 20, so at most 400 cells.
• Every move has the same cost (one roll), which is the key to the expected complexity.
• A cell that is itself a snake/ladder head is never a valid resting square — you only stop on its destination.

Think about it first

TL;DR

Treat cells as nodes with unit-cost edges to the next six cells; BFS from cell 1 gives the fewest moves — O(n²) time, O(n²) space.

Approach 1 — Brute-force DFS over all roll sequences

The naive idea: recursively try every die roll from the current cell, following snakes/ladders, and track the minimum moves to reach n². Because ladders and snakes create cycles, you must mark cells in the current path to avoid looping forever.

def snakesAndLadders(board: list[list[int]]) -> int:
    n = len(board)
    target = n * n

    def to_coord(cell: int) -> tuple[int, int]:
        quot, rem = divmod(cell - 1, n)
        row = n - 1 - quot
        col = rem if quot % 2 == 0 else n - 1 - rem
        return row, col

    best = float("inf")

    def dfs(cell: int, moves: int, on_path: set) -> None:
        nonlocal best
        if cell == target:
            best = min(best, moves)
            return
        for d in range(1, 7):
            nxt = cell + d
            if nxt > target:
                break
            r, c = to_coord(nxt)
            if board[r][c] != -1:
                nxt = board[r][c]
            if nxt not in on_path:
                on_path.add(nxt)
                dfs(nxt, moves + 1, on_path)
                on_path.remove(nxt)

    dfs(1, 0, {1})
    return -1 if best == float("inf") else best

Complexity: exponential — the number of distinct simple paths through the board blows up combinatorially. DFS is the wrong tool for a shortest path in an unweighted graph; it enumerates paths instead of finding the minimum directly.

Approach 2 — BFS (the right tool)

Every move costs exactly one roll, so the graph is unweighted. In an unweighted graph, breadth-first search reaches each node by the fewest edges: it expands cells in strict order of their distance from the start. The first time BFS dequeues n², its move count is the answer. That property is why BFS, not DFS, is the standard choice for shortest paths when every edge costs the same.

from collections import deque

def snakesAndLadders(board: list[list[int]]) -> int:
    n = len(board)
    target = n * n

    def to_coord(cell: int) -> tuple[int, int]:
        quot, rem = divmod(cell - 1, n)
        row = n - 1 - quot
        col = rem if quot % 2 == 0 else n - 1 - rem
        return row, col

    visited = {1}
    queue = deque([(1, 0)])  # (cell, moves)
    while queue:
        cell, moves = queue.popleft()
        if cell == target:
            return moves
        for d in range(1, 7):
            nxt = cell + d
            if nxt > target:
                break
            r, c = to_coord(nxt)
            dest = board[r][c]
            if dest != -1:
                nxt = dest
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, moves + 1))
    return -1

Walkthrough (6×6 board, ladders 2→15, 14→35, snake 17→13, target 36): BFS starts at (1, 0). Rolling a 1 lands on cell 2, whose ladder sends us to 15 → enqueue (15, 1). From 15 a roll of 2 reaches cell 17, whose snake drops us to 13 → enqueue (13, 2). From 13 a roll of 1 reaches cell 14, whose ladder lifts us to 35 → enqueue (35, 3). From 35 a roll of 1 reaches 36 → dequeued as (36, 4). Answer 4. Because BFS processes cells in distance order, no shorter route can be missed.

flowchart LR
    A["cell 1"] -->|"roll 1, ladder 2 to 15"| B["cell 15"]
    B -->|"roll 2, snake 17 to 13"| C["cell 13"]
    C -->|"roll 1, ladder 14 to 35"| D["cell 35"]
    D -->|"roll 1"| E["cell 36 target"]

Complexity: at most n² nodes, each expanding 6 edges → O(n²) time, O(n²) space for the queue and visited set. (Dijkstra would also work but is overkill: with uniform weights it degenerates into exactly this BFS.)

Common pitfalls

• Boustrophedon conversion. The row direction alternates. Get the parity check backwards and cell 7 lands in the wrong column; test the mapping on a tiny board before trusting it.
• Chaining snakes/ladders. You take at most one per move — apply the board destination once, do not follow a snake at the destination too.
• Marking the head vs. the destination as visited. Add the final landing cell (post-snake/ladder) to visited, not the intermediate cell you rolled onto; otherwise you can mis-dedupe.
• nxt > target guard. Rolls that overshoot n² are illegal moves — break (or continue) instead of indexing off the board.

Pattern takeaway

When a problem asks for the minimum number of steps and every step costs the same, reach for BFS: it visits nodes in nondecreasing distance order, so the first arrival is optimal. DFS suits reachability and connectivity, not shortest paths. The real work is often just modeling — here, turning an oddly-numbered board into a clean graph of cells and edges.