Snakes and Ladders
Snakes and Ladders: on an n×n boustrophedon board, return the least number of dice moves needed to reach the last square, or -1 if it is unreachable.
- 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.
Intuition
Each square connects to the six ahead of it, so the board is a graph and every move costs one roll — BFS finds the fewest rolls. The only real complication is the boustrophedon numbering, which is best isolated in a helper that converts a square number into board coordinates.
Board games with uniform-cost moves are unweighted shortest-path problems, so BFS applies directly. The distinctive work here is the coordinate mapping — whenever a problem uses an unusual numbering, isolate the conversion in a helper and keep the algorithm generic.
Approach
Before reading on: work out the row and column of square 15 on a 6×6 board by hand, then write the general formula. Keeping that conversion separate from the search is most of the battle. Aim for O(n²).
Isolate the coordinate conversion
Squares are numbered from the bottom-left, running alternately right and left as you go up. For square s (1-indexed), let q = (s - 1) // n and r = (s - 1) % n. The row from the bottom is q, so the array row is n - 1 - q. The column is r on even q and n - 1 - r on odd q, because those rows run backwards. Writing this as a small helper keeps the BFS itself completely free of index arithmetic — mixing the two is where most bugs on this problem come from.
BFS over squares, not cells
Treat the square number as the node. From square s, the reachable neighbours are s+1 through s+6, capped at n². For each, look up the board value: if it is not −1, a snake or ladder redirects the move to that destination instead. Enqueue the resulting square with one more roll and mark it visited. The first time square n² is dequeued — or reached — the roll count is minimal, because BFS expands in order of distance.
One jump per move, never chained
Landing on a ladder moves you to its top, but if that top holds another snake or ladder you do not take it — the rules allow at most one jump per roll. So apply the redirection once and stop. Marking the destination as visited rather than the intermediate square is what enforces this naturally. The board has n² squares each with 6 outgoing edges, giving O(n²) time and space.
Solution & live demo
Common pitfalls
Getting the boustrophedon direction backwards
col = remainder
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
while board[row][col] != -1:
nxt = board[row][col]
row, col = coordinates(nxt)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
visited.add(square + step)
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.
Edge cases
The answer is ⌈(n²−1)/6⌉, the pure dice minimum.
The queue drains without reaching n² and the answer is -1.
Found on the first move, giving 1.
Only one jump is taken per move, so the snake is not chained.
Square 4 is within one roll of square 1, so the answer is 1.