Snakes and Ladders LeetCode 909 Guide

LeetCode 909 — Snakes and Ladders — gives you an n x n board where each cell contains either -1 (no snake or ladder) or a positive integer (the destination of a snake or ladder). The board is numbered 1 to n² in boustrophedon order: starting from the bottom-left, the first row goes left-to-right (squares 1 to n), the next row goes right-to-left (squares n+1 to 2n), and so on, alternating direction with each row up to the top. You start at square 1 and want to reach square n².

On each turn you roll a six-sided die and move forward 1 to 6 squares. If the square you land on contains a snake or ladder (board value != -1), you are immediately teleported to the destination — you have no choice. You cannot voluntarily skip a snake or ladder. Your goal is to find the minimum number of dice rolls needed to reach square n², returning -1 if it is impossible.

The problem has a graph interpretation: every square is a node, and from each square you have up to 6 outgoing edges (the six possible die outcomes). If a destination square has a snake or ladder, the edge actually leads to the teleport destination. This makes it a shortest-path problem on an unweighted directed graph, and BFS gives the answer in O(n²) time.

BFS is the ideal algorithm for finding minimum rolls because the game graph is unweighted — every dice roll costs exactly 1 turn regardless of how far you move. BFS processes squares in order of increasing roll count from square 1. The first time BFS reaches square n², the roll count at that moment is guaranteed to be the minimum. No roll can skip levels in BFS, so no shorter path can be missed.

Each square in the game is a node in the graph. From any node, up to 6 edges lead to the squares you can reach with dice rolls of 1 through 6. If any destination square has a snake or ladder, the edge target is replaced with the teleport destination. This means the BFS graph may have fewer than 6 outgoing edges from some nodes when multiple dice rolls lead to the same post-teleport square — but visited tracking handles deduplication.

The game never requires you to stay on a square: on every turn you must roll and move. This means the BFS queue simply holds squares with their roll count, and BFS expands until it finds n² or exhausts all reachable squares. If the queue empties before reaching n², return -1.

The trickiest part of LeetCode 909 is converting a 1-based square number into the correct (row, col) coordinates in the 2D board array. The board is numbered from the bottom-left in boustrophedon fashion: the bottom row is row index n-1 in the array (row 0 in game numbering, containing squares 1 to n), and the top row is array index 0 (containing squares n²-n+1 to n²). Every even game row goes left-to-right; every odd game row goes right-to-left.

To convert square s (1-based) to array coordinates: first compute the zero-based offset offset = s - 1. The game row from the bottom is game_row = offset // n. The array row is r = (n - 1) - game_row (flipping since the array stores the board top-to-bottom). Within the game row, steps = offset % n gives the position within that row. If game_row is even (left-to-right), col = steps. If game_row is odd (right-to-left), col = (n - 1) - steps.

After computing (r, col), look up board[r][col]. If it equals -1, the destination of the dice roll is the plain square number. If it is a positive integer, that positive integer is the teleport destination (already 1-based). Always apply the conversion to determine the real destination before enqueuing into BFS.

Initialize a visited array or set of size n²+1 (indexed by square number 1 to n²). Mark square 1 as visited and enqueue it with roll count 0. In each BFS iteration, dequeue a square and try all six dice rolls: for each next_square from square+1 to min(square+6, n²), convert next_square to (r, col) using the boustrophedon formula, check board[r][col], and set destination = board[r][col] if it is not -1, else destination = next_square.

If destination == n², return the current roll count + 1 immediately. If destination has not been visited, mark it visited and enqueue it with roll count + 1. Checking n² as the destination (not just the rolled square) is important: a ladder could jump you directly to n². If the queue empties without returning, return -1.

Marking visited at enqueue time (not dequeue time) prevents duplicate entries in the queue and ensures O(n²) time complexity. With at most n² nodes and at most 6*n² edges, BFS runs in O(n²) time and uses O(n²) space for the queue and visited array.

Consider a 4x4 board (n=4, squares 1-16). Suppose board[3][0] = 14 (square 3 has a ladder to 14) and board[0][3] = 2 (square 13 has a snake to 2). All other cells are -1. BFS starts: enqueue square 1 (rolls=0), mark visited. Roll 1 from square 1: try squares 2,3,4,5,6,7. Square 3 has a ladder to 14 — destination is 14, enqueue 14 (rolls=1). Square 2 through 7 (no snake/ladder on others in range) enqueued at rolls=1.

At rolls=1, process square 14. From square 14, try 15, 16. Square 16 = n² = 16 — return rolls+1 = 2. The optimal path uses the ladder at square 3 to jump to 14, then rolls to 16 in just 2 total rolls. Without the ladder, reaching square 16 directly would require at least 3 rolls from square 1 (1→7→13→16, but square 13 has a snake back to 2, making that path much longer).

The snake at square 13 (board value 2) would send BFS back to square 2, but since square 2 was already visited at rolls=1, it would be skipped. This demonstrates how visited tracking prevents BFS from re-exploring squares reached by longer paths and ensures the minimum roll count is returned.

Python BFS solution: def snakesAndLadders(board): n=len(board); visited=set([1]); q=deque([(1,0)]); while q: sq,rolls=q.popleft(); for dice in range(1,7): nxt=sq+dice; if nxt>n*n: break; r=(n-1)-(nxt-1)//n; c=(nxt-1)%n if (nxt-1)//n%2==0 else n-1-(nxt-1)%n; if board[r][c]!=-1: nxt=board[r][c]; if nxt==n*n: return rolls+1; if nxt not in visited: visited.add(nxt); q.append((nxt,rolls+1)); return -1. Time O(n²), space O(n²).

Java BFS solution: public int snakesAndLadders(int[][] board) { int n=board.length; boolean[] visited=new boolean[n*n+1]; Queue<int[]> q=new LinkedList<>(); q.offer(new int[]{1,0}); visited[1]=true; while(!q.isEmpty()){ int[] cur=q.poll(); int sq=cur[0],rolls=cur[1]; for(int d=1;d<=6;d++){ int nxt=sq+d; if(nxt>n*n) break; int gr=(nxt-1)/n; int r=n-1-gr; int c=gr%2==0?(nxt-1)%n:n-1-(nxt-1)%n; if(board[r][c]!=-1) nxt=board[r][c]; if(nxt==n*n) return rolls+1; if(!visited[nxt]){ visited[nxt]=true; q.offer(new int[]{nxt,rolls+1}); } } } return -1; }

The coordinate conversion is the trickiest part: game_row = (square-1) // n determines which row from the bottom; array_row = n-1-game_row flips it since the array is top-to-bottom; column direction alternates based on game_row parity. Both Python and Java solutions run in O(n²) time and O(n²) space, processing each of the n² squares at most once with up to 6 dice roll checks each.

Open the Lock (LeetCode 752) is the closest relative to Snakes and Ladders: both are BFS problems on abstract state spaces where the states are not grid cells but higher-level entities (lock combinations or board squares). In Open the Lock, each wheel turn is an edge just as each dice roll is an edge in Snakes and Ladders. Deadends in Open the Lock play the same role as snakes that loop back — states to avoid. Mastering one BFS state-space problem transfers directly to the other.

Shortest Path in Binary Matrix (LeetCode 1091) applies BFS to a 2D grid rather than an abstract state space, but the same BFS-for-minimum-steps reasoning applies. The coordinate system is simpler (no boustrophedon conversion needed), making it a good stepping stone before tackling Snakes and Ladders. Nearest Exit from Entrance in Maze (LeetCode 1926) is another grid BFS variant with an exit-detection condition similar to Snakes and Ladders reaching square n².

Word Ladder (LeetCode 127) is the BFS analogue in string space: each one-letter transformation is an edge, and you seek the minimum transformations from beginWord to endWord. The BFS template is identical to Snakes and Ladders — enqueue start state, expand neighbors, mark visited, return distance when target is reached. These BFS shortest path problems form a family where the state space varies but the algorithm is always the same.