{ }SolveLogs
⌕
Home / Graphs / #909
LeetCode #909 Medium

Snakes and Ladders

Snakes and Ladders is LeetCode 909 (Medium). On an n × n board numbered in boustrophedon order, return the least number of dice moves needed to reach square n², or -1 if it cannot be reached.

The board is at most 20 × 20, so only 400 squares exist and the search is never the bottleneck. The numbering is.

Constraints
  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n²].
  • The squares labeled 1 and n² do not have snakes or ladders.
arraybreadth-first-searchmatrix
Open on LeetCode ↗
02

Intuition

Every square is a node and each of the six dice outcomes is an edge, so the problem is a shortest path on an unweighted graph — plain BFS, no weights to balance. The search is the easy part; two things around it are where answers go wrong:

  • The numbering. Squares run boustrophedon: from the bottom-left, alternating direction each row going up. Convert a square to the wrong row or column and the BFS runs perfectly on the wrong board.
  • The jump rule. A snake or ladder is taken once per move. Landing on a ladder whose top holds a snake's mouth does not then follow the snake.
How to spot this pattern

A board game whose moves all cost the same is an unweighted shortest-path problem, so BFS applies directly. The distinctive work here is a numbering scheme, not an algorithm: whenever a problem labels its cells unusually, isolate the conversion in a helper and keep the search generic.

03

Approach

Try it first

Before reading on: take a 6x6 board and work out the row and column of square 15 by hand, then write the general formula and check it against squares 1, 6, 7 and 36. Getting that conversion right is most of this problem. Aim for O(n²).

1

Start BFS from square 1

Queue square 1 with 0 moves and mark it seen. Pop a square s and try each roll, s + 1 up to min(s + 6, n²). Every roll costs one move, so BFS reaches each square first by the fewest rolls; Dijkstra would be pointless on uniform weights.

2

Convert square numbers to coordinates in a helper

The boustrophedon board snakes back and forth by row from the bottom up. For square s, take q, r = divmod(s - 1, n):

  • the row is n - 1 - q, counting up from the bottom;
  • the column is r when q is even, but n - 1 - r when q is odd.

Keep it in its own helper — folding it into the search is where this goes wrong.

3

Apply at most one snake or ladder per move

After landing, if the cell is not -1, jump to the square it names and stop there. Do not loop. Following a chain of jumps reports fewer rolls than the rules actually permit, and the boards in the examples are built to expose exactly that.

4

Mark the square you end up on

Record the destination after any jump, not the square the dice landed on. Two different rolls that redirect to the same place are the same state, so marking it once stops the queue filling with duplicates of a square already reached sooner.

5

Count moves on the queue, not by level

Carry the move count alongside each square in the queue and return moves + 1 the instant the final square is generated. Because every edge costs one, the first arrival is already the minimum and there is no need to finish the level.

6

Return -1 when the queue drains

If BFS exhausts every reachable square without ever generating the last one, then no sequence of rolls arrives there and the answer is -1. This is a real outcome, not a defensive guard: a board can wall the final square off behind snakes.

04

Snakes and Ladders solution in Python | C++ | Java

▶1class Solution:
▶2 def snakesAndLadders(self, board):
▶3 n = len(board)
▶4 target = n * n
▶5 
▶6 def coordinates(square):
▶7 quotient, remainder = divmod(square - 1, n)
▶8 row = n - 1 - quotient
▶9 col = remainder if quotient % 2 == 0 else n - 1 - remainder
▶10 return row, col
▶11 
▶12 visited = {1}
▶13 queue = deque([(1, 0)])
▶14 while queue:
▶15 square, moves = queue.popleft()
▶16 for step in range(1, 7):
▶17 nxt = square + step
▶18 if nxt > target:
▶19 break
▶20 row, col = coordinates(nxt)
▶21 if board[row][col] != -1:
▶22 nxt = board[row][col]
▶23 if nxt == target:
▶24 return moves + 1
▶25 if nxt not in visited:
▶26 visited.add(nxt)
▶27 queue.append((nxt, moves + 1))
▶28 return -1
to k = snake or ladderreached12to 73456to 3789start on square 1, 0 moves used
board3 × 39 squares
numberingboustrophedonbottom row first, rows alternate
The numbering runs bottom-left and reverses every row. A cell marked to k holds a snake or a ladder that moves you to square k. Keep the square-to-coordinate conversion in its own helper — getting it wrong gives a search that runs perfectly on the wrong board.
to k = snake or ladderreached12to 73456to 3789at square 1 after 0 move(s)
square1taken off the queue
moves used0
queueempty0 waiting
Take square 1 off the front of the queue. BFS expands in order of distance, so everything reachable in 0 move(s) is handled before anything that needs more.
to k = snake or ladderreached12to 73456to 3789roll 1 → square 7
roll1from square 1
lands on2 → 7a ladder
queue7square 7 added
Rolling 1 lands on square 2, which holds a ladder up to square 7. Take that jump once and stop — if square 7 also held one, it would not be followed. Mark square 7, the square actually occupied, not square 2.
to k = snake or ladderreached12to 73456to 3789roll 2 → square 3
roll2from square 1
lands on3no jump
queue7, 3square 3 added
Rolling 2 lands on square 3, which is an ordinary square. It is new, so mark it and add it to the queue to be expanded later.
to k = snake or ladderreached12to 73456to 3789roll 3 → square 4
roll3from square 1
lands on4no jump
queue7, 3, 4square 4 added
Rolling 3 lands on square 4, which is an ordinary square. It is new, so mark it and add it to the queue to be expanded later.
to k = snake or ladderreached12to 73456to 3789roll 4 → square 5
roll4from square 1
lands on5no jump
queue7, 3, 4, 5square 5 added
Rolling 4 lands on square 5, which is an ordinary square. It is new, so mark it and add it to the queue to be expanded later.
to k = snake or ladderreached12to 73456to 3789roll 5 → square 3, already seen
roll5from square 1
lands on6 → 3a snake
queue7, 3, 4, 5unchanged
Rolling 5 lands on square 6, which holds a snake down to square 3. Take that jump once and stop — if square 3 also held one, it would not be followed. Square 3 has been reached before, so it is not queued again.
to k = snake or ladderreached12to 73456to 3789roll 6 → square 7, already seen
roll6from square 1
lands on7no jump
queue7, 3, 4, 5unchanged
Rolling 6 lands on square 7, which is an ordinary square. It has been reached before by a route no longer than this one, so it is not queued again.
to k = snake or ladderreached12to 73456to 3789at square 7 after 1 move(s)
square7taken off the queue
moves used1
queue3, 4, 53 waiting
Take square 7 off the front of the queue. BFS expands in order of distance, so everything reachable in 1 move(s) is handled before anything that needs more.
to k = snake or ladderreached12to 73456to 3789roll 1 → square 8
roll1from square 7
lands on8no jump
queue3, 4, 5, 8square 8 added
Rolling 1 lands on square 8, which is an ordinary square. It is new, so mark it and add it to the queue to be expanded later.
to k = snake or ladderreached12to 73456to 3789reached square 9 in 2 move(s)
roll2from square 7
lands on9
answer2fewest dice moves
Square 9 reached in 2 move(s). BFS expands by distance, so the very first arrival is already the fewest rolls — there is no shorter route still waiting in the queue.
05

Common pitfalls

Getting the boustrophedon direction backwards

✗ Wrong
col = remainder
✓ Right
col = remainder if quotient % 2 == 0 else n - 1 - remainder

Alternate rows are numbered right to left. Using the plain remainder reads the wrong cell on every odd row, so snakes and ladders appear in the wrong places and the answer is silently wrong.

Chaining jumps

✗ Wrong
while board[row][col] != -1:
    nxt = board[row][col]
    row, col = coordinates(nxt)
✓ Right
if board[row][col] != -1:
    nxt = board[row][col]

The rules permit at most one snake or ladder per move. Following a chain of them reports fewer rolls than are legally possible.

Marking the pre-jump square as visited

✗ Wrong
visited.add(square + step)
✓ Right
visited.add(nxt)  # after the jump is applied

The square you actually occupy is the jump's destination. Marking the intermediate square lets the same destination be enqueued repeatedly and can block a genuinely shorter route.

06

Edge cases

A board with no snakes or ladders

The answer is the pure dice minimum, since a roll of six is always available and nothing redirects it.

A ladder whose top square holds a snake

Only one jump is taken per move, so the ladder is followed and the snake is not. Chaining them would under-report the answer.

The final square is unreachable

The queue drains without ever generating the last square, and the function returns -1.

A 2x2 board

Square 4 is within a single roll of square 1, so the answer is 1 — the smallest board the constraints allow.

07

Complexity

Time
O(n²)
Space
O(n²)
Each of the n² squares is enqueued at most once and has at most six outgoing moves.
← Prev · #907
Sum of Subarray Minimums
Next · #930 →
Binary Subarrays With Sum