← DSA Atlas
Dedicated problem page · #909

Snakes and Ladders

MediumGraph DFS and BFSShortest path on a board graphBFS with boustrophedon square-to-cell mapping
Solve on LeetCode ↗
909
MediumGraph DFS and BFSBFS with boustrophedon square-to-cell mappingShortest path on a board graph

Snakes and Ladders

On an n x n board numbered 1..n^2 in a boustrophedon (snake) pattern starting bottom-left, you begin on square 1. Each move rolls a die and advances 1..6 squares. If the destination square holds a snake or ladder (board value != -1), you must move to that value's square. Return the least number of moves to reach square n^2, or -1 if unreachable.

Open official problem prompt ↗
In plain English

Find the fewest dice rolls to travel from square 1 to the final square, obeying the redirections imposed by snakes and ladders.

Picture it like this

It is the classic children's board game: count the minimum number of turns to finish, where a well-placed ladder skips you far ahead and a snake drags you back — but you always advance exactly one to six squares per roll before any redirection.

Example
Input
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output
4
Why
One optimal route in 4 rolls: from 1 roll to 2 (ladder to 15); from 15 roll to 17 (ladder to 13); from 13 roll to 14 (ladder to 35); from 35 roll to 36. That reaches square 36 in 4 total dice rolls.
Constraints
n == board.length == board[i].length2 <= n <= 20grid values are -1 or in the range [1, n^2]Squares 1 and n^2 are not the start of a snake or ladderA board square has at most one snake or ladder
Pattern lesson

See the pattern, then code

Shortest path on a board graph
Recognition clue

Each dice roll is a unit-cost move and you want the fewest moves to a target square — uniform-cost shortest path over squares 1..n^2. The only twist is translating a linear square number into board[row][col] under the snake numbering.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Model squares as nodes; from square s you have edges to s+1..s+6, redirected by any snake/ladder at the landing square. BFS gives the minimum number of rolls because every edge costs one move. The boustrophedon mapping is a pure coordinate conversion done per landing.

New words, made simpleKnow these before the algorithm
Boustrophedon numbering
Row-by-row labeling that alternates direction each row, starting at the bottom-left.
Square
A numbered position 1..n^2, the node in our graph.
Redirection
A snake/ladder value that forces you off the landing square to another square.
Level (moves)
BFS depth = number of dice rolls taken so far.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DFS / recursion

Does not naturally yield the minimum and can loop on snakes; wrong for shortest path.

Recurse over dice choices tracking the minimum rolls.

Time Exponential, revisits squaresSpace O(n^2)
Best choiceBFS over squares

First arrival at n^2 is the minimum roll count; visited set keeps it linear in squares.

Explore squares in rolls-order from square 1, applying redirection at each landing.

Time O(n^2)Space O(n^2)
The rule we keep true

Invariant

When a square is dequeued, its stored moves equals the minimum number of dice rolls to reach it from square 1.

Why this is correct

Reasoning

Every dice roll is one BFS edge of unit cost, so BFS visits squares in non-decreasing roll count. Because a square is marked visited (by its final redirected position) the first time it is enqueued, no square is expanded twice and the first time the target is dequeued gives the optimal number of moves.

The algorithm in three movesSay these aloud before coding
1Write a helper converting square number to (row, col) using divmod and row-parity for the zig-zag

get(2) -> ladder to 15

2BFS from square 1 with a visited set and a moves counter

queue: (1,0) -> (15,1) -> (13,2) ...

3From the current square, generate landings s+1..min(s+6, n^2)

target 36 reached at moves=4

4Redirect to board[r][c] when it is not -1, otherwise stay on the numbered square

5Return moves when n^2 is reached, else -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
..1
15(ladder)2
..3
13(ladder)4
35(ladder)5
366
1 · Readsquare 1
2 · AskIs it the target 36?
3 · Update statequeue=[(1,0)], seen={1}
4 · ResultNo; expand rolls to squares 2..7.
Key takeaway

BFS layers over board squares; ladders shortcut the walk to square 36 in 4 rolls.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 7-11Square-to-cell conversion

    divmod(square-1, n) gives the row-from-bottom and column offset; even rows read left-to-right and odd rows right-to-left, matching the snake layout.

  2. 2
    Lines 13-15BFS seeding

    Start at square 1 with 0 moves; the visited set stores redirected destinations to avoid re-expansion.

  3. 3
    Lines 18-24Generate and redirect moves

    For each of up to six landings, apply the snake/ladder value when present, then enqueue unseen destinations at moves+1.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Target unreachable because ladders/snakes trap you -> return -1
  • n = 2 minimal board
  • A ladder on the last-reachable square lands exactly on n^2
  • Chained expectation: the problem forbids chaining, so you redirect only once per landing (do not follow a snake/ladder at the redirected square)
!

Common beginner mistakes

  • Getting the boustrophedon row/column parity backwards, especially forgetting numbering starts at the BOTTOM row
  • Following a snake/ladder repeatedly (chaining) instead of exactly once per move
  • Marking the pre-redirection square visited rather than the destination
  • Rolling past n^2 — clamp the upper bound with min(square+6, target)
Check your understanding

Why must the visited set store the redirected destination square rather than the square you initially land on?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill