DSA sheet · Graphs · BFS shortest path pattern

Snakes and Ladders

The last question of the teacher's BFS pattern. It looks like a game, but it's a shortest-path question in disguise: every square is a node, every dice roll is an edge, and each roll costs 1 move. So the minimum number of rolls is the number of BFS levels. The tricky part isn't BFS at all. It's turning a square number into a (row, col) on a board that's numbered from the bottom, zigzagging left-right and right-left. The teacher spends a long time on that formula, and so do these notes.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · What you must know before starting (graphs, BFS, levels)
· inside Part 0: why BFS levels = fewest moves
Part A · BFS over the squares, level by level
· inside Part A, step 4: board numbering and square → (row, col)
Part B · Revision page

Part 0 · Before starting

Graph words

Node: a point. Edge: a link from one node to another.
Directed edge (3)→(5): you can go 3 to 5 but not back. Dice moves are directed: you only move forward (or down a snake), never "un-roll".
Weighted edge: has a cost. Unweighted: every edge costs 1. Every dice roll is one move, so this graph is unweighted.

a few squares of Example 1 as a graph (each arrow = one roll):
(1)→(15)   (1)→(3)   (1)→(4) ... (1)→(7)      ← rolling 1 lands on 2, whose ladder sends you to 15
(13)→(35)                                   ← rolling 1 from 13 lands on 14, ladder to 35
(15)→(16)  (15)→(13)  ...                    ← rolling 2 from 15 lands on 17, a snake down to 13

Storing a graph

Most graph problems give an edge list, and we build an adjacency list (node → its neighbours):

edge list → adjacency list (directed)

n = 4
edges = [[0, 1], [0, 2], [2, 3]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)          # directed: one way only
print(adj)   # [[1, 2], [], [3], []]

Here we don't build one. From square s the neighbours are always s+1 … s+6 (then follow a snake/ladder if there is one). We can compute them on the fly, just like the 4 directions in a grid problem.

Visited

Snakes send you backwards, so you can come back to a square you've already handled (Example 1: from 15, a snake drops you to 13). Without a visited mark, BFS would push it again and again, and might loop forever. Visited = "this square is already in the queue or done; don't push it again".

BFS and DFS

BFS: queue (collections.deque), visits everything 1 move away, then 2 moves, then 3…
DFS: recursion/stack, follows one sequence of rolls deep before trying others. It finds a way to the end, not the shortest.

Why BFS levels = fewest moves

Level 0 is square 1. Level 1 is every square reachable with one roll. Level 2 is every new square reachable from level 1 with one more roll, and so on. A square first appears in level k only if no sequence of fewer than k rolls reaches it (otherwise it would have shown up in an earlier level and been marked visited). So the level where the last square n² first appears is the minimum number of rolls.

To know which level we're in, we process the queue one level at a time: read size = len(queue) before the round and pop exactly that many. Whatever gets pushed during the round is the next level.

level-by-level BFS template

from collections import deque

adj = [[1, 2], [3], [3], []]
queue = deque([0])
visited = [False] * 4
visited[0] = True
level = 0
while queue:
    for _ in range(len(queue)):     # only this level's nodes
        u = queue.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                queue.append(v)
    level += 1
# the levels were {0}, {1, 2}, {3}
print(level)   # 3

Part A · BFS over the squares, level by level

LeetCode 909

1The question in simple words

You get an n×n board. Its squares are numbered 1 to n² in a special zigzag order (drawn below). You start on square 1. Each move:

Roll a die: pick any square from current + 1 to current + 6, but never past n².
If that square has a snake or ladder (board[r][c] != -1), you must go to board[r][c]. A ladder takes you up, a snake takes you down.
You follow at most one snake/ladder per move, even if the destination has another one.

Return the least number of rolls to reach square n², or −1 if you can't.

In board, -1 means a plain square. Any other number is where the snake/ladder takes you.

Example 1 (n = 6). Left: the board array as given. Right: the square numbers.

board[r][c]                              square numbers (zigzag from the bottom)
      c=0  c=1  c=2  c=3  c=4  c=5             c=0 c=1 c=2 c=3 c=4 c=5
r=0   -1   -1   -1   -1   -1   -1        r=0    36  35  34  33  32  31   ←
r=1   -1   -1   -1   -1   -1   -1        r=1    25  26  27  28  29  30   →
r=2   -1   -1   -1   -1   -1   -1        r=2    24  23  22  21  20  19   ←
r=3   -1   35   -1   -1   13   -1        r=3    13  14  15  16  17  18   →
r=4   -1   -1   -1   -1   -1   -1        r=4    12  11  10   9   8   7   ←
r=5   -1   15   -1   -1   -1   -1        r=5     1   2   3   4   5   6   →  start

ladders: 2 → 15,  14 → 35          snake: 17 → 13          answer: 4

The teacher reads it like a normal board game: land on 2 and you climb to 15; land on 14 and you climb to 35; land on 17 and the snake takes you down to 13.

2What the constraints tell us

2 <= n <= 20 → at most 400 squares. Each square tries 6 rolls → about 2400 steps. Tiny.
board[i][j] is −1 or a square number from 1 to n².
Squares 1 and n² have no snake or ladder → we start cleanly on 1, and reaching n² ends the game.
The board doesn't give us "square 15 is at row 3, col 2". We must compute (row, col) from the square number every time we read the board.

3Intuition: you play alone and try every roll

The teacher makes this point clearly: it isn't a game between players to see who wins. You are the only player, and you get to choose every roll. The question is: "if the die gave the best numbers, how few rolls would you need?"

Two ways she plays Example 1:

	rolls	squares	moves
greedy-looking	1, 6, 6, 6, 3	1 → 2 (ladder 15) → 21 → 27 → 33 → 36	5
best	5, 6, 2, 1	1 → 6 → 12 → 14 (ladder 35) → 36	4

Taking the first ladder looks clever but isn't best. We can't guess which choices win, so we try all rolls at once, level by level. That's BFS. Also, "least number of rolls" with every roll costing 1 is the signal for BFS that she trains us to spot in this pattern.

4Building the logic from her examples

Level 1: what's reachable with one roll from square 1?

From 1, a roll of 1–6 lands on 2, 3, 4, 5, 6, 7. But landing on 2 doesn't leave you on 2: square 2 has a ladder, so you end up on 15. So we push 15, not 2. The other five are plain squares.

RuleFor each roll: nxt = cur + roll. Look up board at nxt's (row, col). If it isn't −1, replace nxt with that value. Then do the visited check and push.

Doubt: should I mark 2 visited, or 15?
→ The teacher says either is possible, but mark 15, the square you actually end up on. The queue holds positions where you stand, and you never stand on 2 (you're forced up the ladder). If you only marked 2, then reaching 15 another way later would push 15 a second time.

Why we must go level by level

Everything reached from square 1 in one roll is "1 move", whether it was 15 via the ladder or plain 7. If we just popped forever, we couldn't tell when the first move ends and the second begins. So: freeze size = len(queue), pop only that many (here 15, 3, 4, 5, 6, 7), then moves += 1. When 15 is popped, its children (16, 13, …) are pushed behind 7, and they belong to the next move.

Level 2 in her dry run: snakes and the visited check

Pop 15: rolls give 16, 17 → snake → 13, 18, 19, 20, 21. Push 16, 13, 18, 19, 20, 21 and mark them.
Pop 3: 4–7 are already visited, so only 8, 9 are new.
Pop 4: only 10 is new. Pop 5: 11. Pop 6: 12.
Pop 7: 8–12 visited; 13 is already visited (it came from 15's snake). Nothing new.

She points out the 13 case: without the visited array, square 13 would sit in the queue twice.

Stopping and the edge of the board

Return as soon as we pop square n²: the current moves is the answer (first arrival = fewest rolls).
Past the end: if cur + roll > n², stop trying bigger rolls. Her example: from 35, a roll of 1 gives 36. A roll of 2 gives 37, which is off the board, and 3, 4, 5, 6 would be too. So break out of the roll loop (only the inner loop, not the BFS).
−1: if the queue empties without popping n², it's unreachable (for example, every square in reach has a snake back down).

The hard part: square number → (row, col)

The board is numbered like this (the word is boustrophedon, "as the ox ploughs": one row left to right, the next right to left):

n = 6                                         n = 3
row(top)  numbers          direction           row(top)  numbers   direction
  0     36 35 34 33 32 31     ←                   0       7  8  9     →
  1     25 26 27 28 29 30     →                   1       6  5  4     ←
  2     24 23 22 21 20 19     ←                   2       1  2  3     →   start
  3     13 14 15 16 17 18     →
  4     12 11 10  9  8  7     ←
  5      1  2  3  4  5  6     →   start

Two problems: the numbering starts at the bottom, but list index 0 is the top row. And every other row runs backwards.

Step 1: the row

Squares come in blocks of n per row. Use num - 1 to count from 0. Then k = (num - 1) // n tells which row it is counting from the bottom (0 = bottom row).

Her example: num = 22, n = 6 → (22 − 1) // 6 = 21 // 6 = 3. That's the 4th row from the bottom (rows from the bottom: 0, 1, 2, 3). But the list is indexed from the top, so flip it: row = (n - 1) - k = 5 − 3 = 2. Check the picture: 22 is in top-row index 2 ✓.

Row formularow = n - 1 - (num - 1) // n
Same formula for any n, even or odd.

Step 2: the column

Inside a row, (num - 1) % n is the position from the start of that row:

For rows that run left → right, that position is the column. num = 15: 14 % 6 = 2 → column 2 ✓. num = 4: 3 % 6 = 3 → column 3 ✓.
For rows that run right → left, count from the right: col = n - 1 - (num - 1) % n. num = 21: 20 % 6 = 2 → 5 − 2 = 3 → column 3 ✓. num = 33: 32 % 6 = 2 → 5 − 2 = 3 ✓.

Step 3: which rows run backwards? (where she slows down)

Counting from the bottom it's simple: bottom row k = 0 runs →, k = 1 runs ←, k = 2 runs →… Rows with odd k run backwards, for every n.

But if you look at the row index from the top, the pattern depends on n. With n = 6, the bottom row is top-index 5 (odd) and runs →. With n = 3, the bottom row is top-index 2 (even) and runs →. The teacher shows this with n = 3: for num = 4, a rule like "odd top-row → plain column" gives column 0, but 4 is really in column 2. So "is the top row index odd?" works for one n and breaks for the other.

Her fix is to test (n - row) instead of row: when (n - row) is even, the row runs right → left. Why this works: n - row = n - (n - 1 - k) = k + 1. So (n - row) is even exactly when k is odd, which is exactly "runs backwards". It doesn't depend on n any more.

Doubt: her even/odd explanation is about subtracting numbers. Is there a simpler way to say it?
→ Yes. Use k (the row from the bottom) directly: k even → left to right, k odd → right to left. It's the same test as hers (because n − row = k + 1), just easier to remember. The code below uses k.

num (n = 6)	k = (num−1)//6	row = 5 − k	(num−1)%6	k odd?	col
1	0	5	0	no	0
2	0	5	1	no	1 → board[5][1] = 15 (ladder)
7	1	4	0	yes	5 − 0 = 5
14	2	3	1	no	1 → board[3][1] = 35 (ladder)
17	2	3	4	no	4 → board[3][4] = 13 (snake)
22	3	2	3	yes	5 − 3 = 2
36	5	0	5	yes	5 − 5 = 0

num (n = 3)	k	row = 2 − k	(num−1)%3	k odd?	col
4	1	1	0	yes	2 − 0 = 2 ✓ (her example)
6	1	1	2	yes	0
8	2	0	1	no	1

5Approach steps

n = len(board), last = n * n.
visited = list of n² + 1 False values (index 0 unused, so square s uses index s). Mark 1, push 1. moves = 0.
While the queue isn't empty: for size items of this level:
pop cur; if cur == last → return moves;
for roll 1..6: nxt = cur + roll; if nxt > last → break;
get (row, col) of nxt; if board[row][col] != -1 → nxt = board[row][col];
if nxt not visited → mark it, push it.
After each level, moves += 1. If the queue empties → return −1.

6Code (Python)

Snakes and Ladders · level-by-level BFS + square → (row, col)

from collections import deque

class Solution:
    def snakesAndLadders(self, board):
        n = len(board)
        last = n * n
        visited = [False] * (last + 1)       # index = square number (0 unused)
        visited[1] = True
        queue = deque([1])
        moves = 0

        while queue:
            for _ in range(len(queue)):      # one level = one roll
                cur = queue.popleft()
                if cur == last:
                    return moves
                for roll in range(1, 7):
                    nxt = cur + roll
                    if nxt > last:           # bigger rolls go even further off the board
                        break
                    r, c = self.getRowCol(nxt, n)
                    if board[r][c] != -1:    # snake or ladder: forced to move
                        nxt = board[r][c]
                    if not visited[nxt]:
                        visited[nxt] = True
                        queue.append(nxt)
            moves += 1
        return -1

    def getRowCol(self, num, n):
        k = (num - 1) // n                   # row counted from the BOTTOM (0 = bottom)
        row = n - 1 - k                      # flip: list index counts from the top
        col = (num - 1) % n                  # position from the start of that row
        if k % 2 == 1:                       # same as (n - row) % 2 == 0: row runs right to left
            col = n - 1 - col
        return row, col

7Code line by line

line	what it means
last = n * n	The goal square.
visited = [False] * (last + 1)	One slot per square. She makes it size n² + 1 so square s sits at index s, with no "−1" shifting.
visited[1] = True queue = deque([1])	Single source: square 1. Marked as soon as it's pushed.
for _ in range(len(queue)):	`len(queue)` is read once, so only this level's squares are popped in this round.
if cur == last: return moves	The first time the goal is popped, `moves` is the number of levels = fewest rolls.
for roll in range(1, 7):	Try every die face, 1 to 6.
if nxt > last: break	Off the board. Bigger rolls are further off, so stop this inner loop. (BFS continues.)
r, c = self.getRowCol(nxt, n)	Where square nxt lives in the 2D list.
if board[r][c] != -1: nxt = board[r][c]	Forced jump. Only one jump per move: we don't look up the destination's own snake/ladder.
if not visited[nxt]:	Check the square where you end up (15, not 2).
moves += 1	One full level handled → one more roll used.
return -1	The queue ran dry and the goal was never popped.
k = (num - 1) // n	Row number from the bottom.
row = n - 1 - k	Row number from the top, which is what `board[row]` needs.
col = (num - 1) % n	Position inside the row, counting from where that row starts.
if k % 2 == 1: col = n - 1 - col	Odd rows (from the bottom) run right to left, so count from the right edge.

Doubt: in her Java code the first run failed with "cannot find symbol".
→ She had called the helper with num instead of the loop variable next. She fixed the argument and it passed. In our code that's getRowCol(nxt, n).

8Dry run (Example 1)

level (moves)	popped	rolls land on → after snake/ladder	new squares pushed	queue AFTER the level
0	1	2→15, 3, 4, 5, 6, 7	15 3 4 5 6 7	15 3 4 5 6 7
1	15	16, 17→13, 18, 19, 20, 21	16 13 18 19 20 21	16 13 18 19 20 21 8 9 10 11 12
	3	4 5 6 7 (visited), 8, 9	8 9
	4	5–9 visited, 10	10
	5	…, 11	11
	6	…, 12	12
	7	8–12 visited, 13 visited	none
2	16	17→13 (visited), 18–21 visited, 22	22	22 35 23 24 25 26 27 …
	13	14→35, 15, 16, 17→13, 18, 19 (visited)	35
	18, 19, 20, 21, 8, 9, 10, 11, 12	new squares 23 … 27 from 18–21; the small ones find nothing new (12 + 2 = 14 ⇒ 35, already pushed)	23 24 25 26 27
3	… 35 …	35 + 1 = 36	36	… 36 …
4	… 36	cur == 36	–	return 4

The path BFS found: 1 → (roll 1) 2 ⇒ 15 → (roll 2) 17 ⇒ 13 → (roll 1) 14 ⇒ 35 → (roll 1) 36. Four rolls. It's a different 4-roll path from the teacher's (1 → 6 → 12 → 14 ⇒ 35 → 36). Both have 4 rolls; BFS only promises the number is the smallest. (In her board drawing the snake is even helpful: falling from 17 to 13 puts you one step before the 14 ladder.)

visited after level 0

1 3 4 5 6 7 15

after level 1

1 3-13 15-21
(2, 14, 17 never "stood on")

level 2 reaches

35 via 13 → 14
then 36 in level 3

9Complexity & remember

Time O(6 · n²): each square enters the queue at most once (visited), and each popped square tries 6 rolls. getRowCol is a few arithmetic steps, O(1). With n ≤ 20 that's at most 2400 roll checks.
Space O(n²): the queue and the visited list, each up to n² + 1 entries.

RememberSquares are nodes, rolls are edges of cost 1 → BFS by levels, moves = level. For each roll: off the board → break; convert to (row, col); follow the snake/ladder once; check visited on the landing square. row = n−1−k, col = (num−1)%n, flipped when k is odd.

Part B · Revision page

	grid BFS (e.g. Shortest Path in Binary Matrix)	Snakes and Ladders
node	a cell (r, c)	a square number 1..n²
neighbours	4 or 8 directions	cur+1 … cur+6, then one snake/ladder jump
visited	a grid or a distance mark	list of size n² + 1
answer	distance stored per cell	number of levels (`moves`)
extra trick	bounds check	square → (row, col) on a zigzag board

square → (row, col)	formula
row from the bottom	`k = (num - 1) // n`
row in the list	`row = n - 1 - k`
column	`(num - 1) % n`, then `n - 1 - col` if k is odd (her test: `(n - row) % 2 == 0`)

If you remember only 5 lines 1. Least rolls, each roll costs 1 → BFS, count levels.
2. Start: push 1, mark it. Pop level by level; pop n² → return moves.
3. Rolls 1..6; past n² → break.
4. Convert to (row, col); if board isn't −1, jump there (just once).
5. Mark and push the landing square; empty queue → −1.

Mistakes to avoid ✗ reading board[(num-1)//n] directly (rows are counted from the bottom)
✗ forgetting that every other row is reversed
✗ deciding the reversed rows by the top row index (breaks when n is odd)
✗ marking the square you rolled onto (2) instead of where you land (15)
✗ following a second snake/ladder from the destination
✗ adding a move per popped square instead of per level

test it yourself (paste under the solution above)

board = [[-1, -1, -1, -1, -1, -1],
         [-1, -1, -1, -1, -1, -1],
         [-1, -1, -1, -1, -1, -1],
         [-1, 35, -1, -1, 13, -1],
         [-1, -1, -1, -1, -1, -1],
         [-1, 15, -1, -1, -1, -1]]
s = Solution()
print(s.snakesAndLadders(board))                      # 4
print(s.snakesAndLadders([[-1, -1], [-1, 3]]))        # 1
print(s.snakesAndLadders([[1, 1, -1], [1, 1, 1], [-1, 1, 1]]))   # -1
print(s.getRowCol(22, 6))                             # (2, 2)
print(s.getRowCol(4, 3))                              # (1, 2)
print(s.getRowCol(36, 6))                             # (0, 0)

Based on this video: Snakes and Ladders | BFS