Snakes and Ladders

You are given an n x n board labeled from 1 to n^2 in a zigzag pattern. Starting at square 1, you can roll a die (1..6) to move forward. If you land on a square with a ladder or snake (value != -1), you must move to that destination. Return the minimum number of moves to reach square n^2, or -1 if impossible.

Why this is worth learning

Choose the state after the mandatory jump, so one BFS edge is exactly one die roll followed by at most one snake or ladder. Board drawing coordinates are only an encoding of labels.

Before coding: one-minute experiment

On a 3x3 board, where are labels 1, 4, 6, and 9? If landing on 2 jumps to 8 and 8 contains a jump, do you chain it?

Function signature

func SnakesAndLadders(board [][]int) int

Inputs / outputs

• board: n x n with -1 or a destination square number.
• Return: minimum moves to reach n^2, or -1.

Example

board = [
  [-1,-1,-1],
  [-1, 9, 8],
  [-1, 8, 9]
]
Output: 1

Constraints

• 2 <= n <= 20

Core idea (near-solution)

Enumerating die sequences repeats states and may loop through snakes. Build the state meaning first: a state is the final square after one roll and its optional forced jump. For each die outcome, convert its numeric landing square to the alternating-row board coordinates, apply at most one jump, and enqueue the resulting state. Mark that destination, not the pre-jump landing. Every such edge costs exactly one roll, so BFS finds the minimum roll count. Following a chain of jumps would change the legal transition and solve a different board game.

Invariant: BFS explores states in non-decreasing number of moves.

Algorithm (step-by-step)

1. Precompute a function that maps square numbers to (r,c) in the zigzag layout.
2. BFS from square 1 with distance 0.
3. For each square, try dice rolls 1..6:
   • Move to next square.
   • If board has a ladder/snake, jump to its destination.
   • If unvisited, enqueue with distance+1.
4. Return distance when reaching n^2, else -1.

Correctness sketch

For a label s, row-from-bottom is (s-1)/n and the within-row offset is (s-1)%n; reversing the offset on odd rows yields the boustrophedon coordinates. From each state, enumerate every legal die result without overshooting, apply exactly one destination lookup, and enqueue unseen resulting states. These transitions are precisely the legal one-roll moves. FIFO distance ordering therefore finds the minimum number of rolls. Visiting the post-jump state prevents duplicate work when different landings jump to the same destination. A destination that itself contains a jump does not trigger another jump in that same roll.

Trace (hand walkthrough)

Example input:
board = [
  [-1,-1,-1],
  [-1, 9, 8],
  [-1, 8, 9]
]
Output: 1

Walk:
- start at 1; try roll=2 -> reach square 3
- square 3 has ladder to 9 -> reach end in 1 move

Pitfalls to avoid

• Incorrect 1D-to-2D mapping for zigzag rows.
• Marking a square visited before applying snake/ladder jump.

Debugging lens

Draw labels before placing jumps. Off-by-one errors in (s-1) and reversing the wrong row produce plausible but wrong boards. Mark the destination after the jump, not only the die-landing square.

Complexity

• Time: O(n^2).
• Extra space: O(n^2).

Implementation notes (Go)

• Convert 1D positions to (row,col) with zigzag row ordering.
• Apply snake/ladder jumps before marking visited.

Contract precision

At most one snake/ladder is applied per roll. The initial square is the supplied starting state, not an automatic jump event. The board is read-only.

Reconstruction checkpoint

On a 3×3 board, square 2 jumps to 8 and square 8 jumps to 9. A roll from 1 lands on 2. Which square is the resulting BFS state and why is neither 2 nor 9 correct?

Return to Graph BFS · Module quiz