Snakes and Ladders
Understanding the Problem
We are playing a game on an n x n board where cells are numbered 1 through n^2 in a zigzag (Boustrophedon) pattern starting from the bottom-left. From any square, we can roll a die (1 through 6) and move forward. If we land on a square with a snake or ladder, we are forced to follow it to its destination. We want to find the minimum number of dice rolls to reach the final square n^2.
Two parts of this problem need care. First, the board numbering is unusual. It starts at the bottom-left, goes right, then reverses direction on the next row up, and so on. Translating between the label number and the actual (row, column) position requires some arithmetic. Second, snakes and ladders introduce non-local jumps. A roll might land on square 5 but end at square 35 because of a ladder. So we cannot greedily pick the highest die roll each time; a smaller roll that hits a ladder can be better.
This is a shortest-path problem on an unweighted graph. Each square is a node, and from each square there are edges to the next 1-6 squares, with some edges redirected by snakes and ladders. BFS finds the shortest path in an unweighted graph, so it gives the minimum number of moves directly.
Key Constraints:
2 <= n <= 20→ The board has at most 400 squares. BFS visits each square once and checks up to 6 neighbors, giving O(n^2) total work. Efficiency is not the constraint here; the difficulty is handling the Boustrophedon numbering and the snake/ladder redirections correctly.board[r][c] == -1means no snake or ladder. Otherwise, it is the destination square.- Squares 1 and n^2 never have a snake or ladder starting from them, so we do not need to worry about edge cases at the start or end.
Approach 1: BFS (Shortest Path)
Intuition
Stripped of the board game theme, the problem is: given a graph where node 1 connects to nodes 2-7, node 2 connects to nodes 3-8, and so on, with some edges redirected by snakes and ladders, find the shortest path from node 1 to node n^2.
Every dice roll costs the same (one move), so BFS gives the minimum number of moves. We start at square 1, explore all squares reachable in one move, then all squares reachable in two moves, and so on, until we reach n^2.
The one piece of arithmetic is the coordinate conversion. The board labels start at 1 in the bottom-left corner and zigzag upward. To convert label s (1-indexed) to (row, col): let quotient = (s - 1) / n and remainder = (s - 1) % n. The row in the matrix is n - 1 - quotient. If quotient is even, the column is remainder; if odd, the column is n - 1 - remainder. Even quotients are rows traversed left-to-right, odd quotients are reversed, which is what produces the zigzag.
A redirection counts as part of the same dice roll, so when a roll lands on a snake or ladder we enqueue and mark visited the final destination, not the intermediate square. This keeps every node at its true move-distance from square 1. Because all edges have the same cost, the first time BFS dequeues n^2 it has reached it in the fewest moves. Marking the intermediate square instead would record a wrong distance for it and could block a shorter path that legitimately ends there from a different roll.
Algorithm
- Create a boolean array
visitedof size n^2 + 1 (using 1-indexed labels). - Initialize a queue with square 1 and mark it as visited. Set
moves = 0. - While the queue is not empty:
- Process all squares at the current level (current number of moves).
- For each square
curr, try destinationscurr + 1throughmin(curr + 6, n^2). - Convert each destination label to (row, col) using the Boustrophedon formula.
- If
board[row][col] != -1, the destination becomesboard[row][col](follow the snake/ladder). - If the final destination is n^2, return
moves + 1. - If the destination has not been visited, mark it visited and add it to the queue.
- If the queue empties without reaching n^2, return -1.
Example Walkthrough
Code
- Time Complexity: O(n^2). There are n^2 squares on the board. BFS visits each square at most once, and for each square we check at most 6 neighbors. The coordinate conversion for each neighbor is O(1).
- Space Complexity: O(n^2). The visited array and queue can each hold up to n^2 entries.
The inline coordinate conversion works, but it interleaves the Boustrophedon math with the BFS loop, so a bug in either part is harder to isolate. The next approach separates the two concerns by preprocessing the board into a flat array before running BFS.
Approach 2: BFS with Flattened Board
Intuition
Instead of converting coordinates during BFS, we preprocess the board into a 1D array flat[1..n^2] where flat[i] is the snake/ladder destination for square i, or -1 if there is none. The Boustrophedon math runs once upfront, and the BFS loop reduces to a lookup: for each neighbor, read flat[next] and redirect if it is not -1.
The algorithm and its complexity are the same as Approach 1; only the timing of the coordinate math changes. Splitting the flattening out as its own step makes each part testable on its own, so a bug in the numbering can be found without touching the BFS.
Algorithm
- Flatten the board into a 1D array
flat[1..n^2]: - Start from the bottom-left (row n-1, col 0).
- Alternate direction each row: left-to-right for even rows from the bottom, right-to-left for odd rows.
- Copy
board[r][c]intoflat[label]for each cell. - Run BFS on the flattened array:
- Start at index 1, target is index n^2.
- For each position, try adding 1-6 to get the next square.
- If
flat[next] != -1, redirect toflat[next]. - Mark visited and enqueue the final destination.
- Return the number of BFS levels when n^2 is reached, or -1.
Example Walkthrough
Code
- Time Complexity: O(n^2). Flattening the board takes O(n^2). BFS visits each of the n^2 squares at most once, checking 6 neighbors per square. Total: O(n^2).
- Space Complexity: O(n^2). The flattened array, visited array, and queue each take O(n^2) space.
Other Approaches Worth Knowing
Dijkstra's algorithm. Every move has weight 1, so the graph is unweighted. Dijkstra would still return the correct answer, but with all edge weights equal it does the same level-by-level exploration BFS does, plus the overhead of a priority queue. That adds an O(log n^2) factor for no benefit. Dijkstra is the choice when edge weights differ; here they do not, so BFS is the right fit.
Bidirectional BFS. Searching forward from square 1 and backward from square n^2 at the same time can shrink the explored frontier on long shortest paths. It does not help much here. The board has at most 400 squares, so plain BFS already visits a tiny graph. The backward search is also awkward to set up: from a square t, the predecessors are all squares s with s + dice reaching t for some roll, including squares whose snake or ladder lands on t. Building that reverse adjacency costs as much as the forward search saves. For this constraint range, single-source BFS is simpler and fast enough.