Snakes and Ladders — Solution

Problem

You have an n×n board where squares are numbered 1 to n² starting from the bottom-left corner and winding in a boustrophedon (S-shape) pattern — left to right on odd rows from the bottom, right to left on even rows. On each turn you roll a six-sided die and advance 1–6 squares; if the square you land on has a snake or ladder, you immediately teleport to its destination. Find the minimum number of moves to reach square n², or return -1 if it's impossible.

• Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,2,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,4,-1,-1,-1,-1]]
• Output: 4
• Explanation: Roll 2 (land on sq 2 → teleport to sq 4 via the ladder at board[5][1]=4), then continue with optimal rolls to reach square 36 in 4 total moves.

Counter-example — board[row][col] = -1 means no snake or ladder on that square; only non-negative-one values trigger teleportation.

Intuition

Each square is a node in a graph, and each die roll is an edge to the next 1–6 reachable squares (after any teleportation). Because every edge costs exactly one move, BFS naturally finds the shortest path from square 1 to square n². The main challenge isn't the algorithm — it's correctly translating a square number into its row and column on the boustrophedon-numbered board.

Solution — BFS with Coordinate Conversion

Flatten the problem: treat each square as a node in an unweighted graph and run BFS from square 1. For every square popped from the queue, try all six die outcomes; if the destination has a snake or ladder, jump to its endpoint before enqueuing.

1. Write a helper that converts square number s to (row, col) on the board: compute idx = s - 1, then row_from_bottom = idx // n and col = idx % n; if row_from_bottom is odd, reverse col to n - 1 - col; finally, row = n - 1 - row_from_bottom.
2. Initialize a visited set containing square 1 and a queue with (square=1, moves=0).
3. While the queue is non-empty, dequeue (square, moves).
4. For each roll from 1 to 6, compute next_sq = square + roll; stop if it exceeds n².
5. Convert next_sq to board coordinates and, if the cell is not -1, overwrite next_sq with the teleport destination.
6. If next_sq == n², return moves + 1; otherwise, if unvisited, mark it visited and enqueue (next_sq, moves + 1).
7. Return -1 if the queue empties without reaching n².

1from collections import deque
2
3def snakesAndLadders(board: list[list[int]]) -> int:
4    n = len(board)
5
6    def square_to_rc(s: int) -> tuple[int, int]:
7        idx = s - 1
8        row_from_bottom = idx // n
9        col = idx % n
10        if row_from_bottom % 2 == 1:   # odd rows read right-to-left
11            col = n - 1 - col
12        row = n - 1 - row_from_bottom  # flip so row 0 is at the top
13        return row, col
14
15    visited = {1}
16    queue = deque([(1, 0)])  # (current_square, moves_taken)
17
18    while queue:
19        current_sq, moves = queue.popleft()
20
21        for roll in range(1, 7):
22            next_sq = current_sq + roll
23            if next_sq > n * n:
24                break  # die rolls are sequential; no need to try larger values
25
26            row, col = square_to_rc(next_sq)
27            if board[row][col] != -1:       # snake or ladder present
28                next_sq = board[row][col]   # teleport to its destination
29
30            if next_sq == n * n:
31                return moves + 1
32
33            if next_sq not in visited:
34                visited.add(next_sq)        # mark when enqueuing to prevent duplicates
35                queue.append((next_sq, moves + 1))
36
37    return -1

Time: O(n²) — each of the n² squares is visited at most once.

Space: O(n²) — visited array and BFS queue each hold at most n² entries.

Complexity Summary

Common Mistakes

• Wrong boustrophedon direction: forgetting that odd rows from the bottom read right-to-left — without the if rowFromBottom % 2 == 1: col = n - 1 - col flip, every other row maps to the wrong square.
• Marking visited after dequeuing instead of enqueuing: the same square can be added to the queue many times before it's processed, causing exponential slowdown; always mark visited immediately when you push to the queue.
• Applying teleportation when the cell is -1: only teleport when board[row][col] != -1; treating -1 as a teleport to square -1 causes an index-out-of-bounds or silent wrong answer.
• Off-by-one in square numbering: squares are 1-indexed (1 to n²) but the array is 0-indexed — idx = s - 1 before dividing by n is essential.
• Skipping the teleport destination check for n²: after teleporting, check if the new square equals n²; some solutions only check the die-roll destination and miss a ladder that leads directly to the finish.

Related Problems

• rotting-oranges — BFS on a grid where each cell's state propagates level by level, same "minimum steps" framing
• 01-matrix — multi-source BFS to find the shortest distance from each cell to the nearest zero
• word-ladder — BFS on an implicit graph where nodes are strings and edges are one-character transformations
• number-of-islands — BFS/DFS to explore connected components in a grid
• flood-fill — BFS/DFS spreading from a source cell to all reachable neighbors