Fewest dice rolls to reach the last square of a zig-zag board full of snakes and ladders. Treat squares as nodes and rolls as edges, and breadth-first search finds the answer level by level in O(n²).
▼The problem
LeetCode 909 (Medium). An n × n board's squares are numbered 1 to n² boustrophedon style, from the bottom-left, alternating direction every row. Each move, roll a die and go 1 to 6 squares ahead (never past n²); if you land on a ladder's foot or a snake's head (board[r][c] != -1) you move to its end, at most one jump per move. Return the fewest moves from square 1 to square n², or -1. (Cousins in the series: ../word-ladder (BFS, stone tower and wooden ladders), ../rotting-oranges, ../number-of-islands, ../cheapest-flights-within-k-stops, ../network-delay-time; this one draws the board game itself.)
Examples (LeetCode's): the 6 × 6 board with ladders 2 → 15 and 14 → 35 and a snake 17 → 13 → 4 (walked through in scene 6), and [[-1,-1],[-1,3]] → 1 (checked in code, not shown).
The solution
def snakesAndLadders(board):
n = len(board)
def cell(s):
r, c = divmod(s - 1, n)
return n - 1 - r, (c if r % 2 == 0 else n - 1 - c)
seen, q, moves = {1}, deque([1]), 0
while q:
for _ in range(len(q)):
s = q.popleft()
if s == n * n:
return moves
for nxt in range(s + 1, min(s + 6, n * n) + 1):
r, c = cell(nxt)
if board[r][c] != -1:
nxt = board[r][c]
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
moves += 1
return -1Transcript
Snakes and Ladders. An n by n board is numbered from the bottom-left, snaking back and forth. Each move, roll a die and step one to six squares. Land on a ladder or snake, and ride it to the other end. Find the fewest moves to the last square.
Take this six by six board. Two climbs to fifteen, fourteen to thirty-five, and a snake drops seventeen to thirteen. To place a square, subtract one and divide by six: the quotient gives the row, the remainder the column, flipped every other row.
Trying every roll sequence explodes: over sixty million after ten moves, and snakes can loop forever.
Instead, make each square a node, with edges to the next six squares, after any snake or ladder. Each edge is one move, so use breadth-first search: one move away, then two, then three. The first visit to the last square is the answer.
In code, a queue starts at square one. Each round, pop the whole level and try six rolls: map each square to its cell, follow any jump, and queue what's new. Then add a move. If the queue runs dry, return minus one.
Let's walk it. Move one: the ladder lifts us to fifteen, plus three to seven. Move two: sixteen to twenty-one, eight to twelve, and the snake drops us to thirteen. Move three: the ladder at fourteen reaches thirty-five. Move four: thirty-six. Four moves, one down a snake.
Each square is queued once and tries six rolls: order n squared time and space.
Squares are nodes, rolls are edges, and rings spread one move at a time. That's Snakes and Ladders.