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.

class Solution:
    def snakesAndLadders(self, 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)

The insight: 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, because it expands cells in strict order of their distance from the start. The first time BFS dequeues n², its move count is the answer. This is why BFS — not DFS — is the default for shortest paths when all edges cost the same.

from collections import deque

class Solution:
    def snakesAndLadders(self, 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.

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.