LeetCode 909 - Snakes and Ladders

The problem is asking us to simulate a modified game of Snakes and Ladders on an n x n board. The board is labeled from 1 to n² in a boustrophedon pattern, which means the numbering starts from the bottom-left, alternates direction every row, and ends at the top-right.

leetcodemediumarraybreadth-first-searchmatrix

LeetCode Problem 909

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem is asking us to simulate a modified game of Snakes and Ladders on an n x n board. The board is labeled from 1 to n² in a boustrophedon pattern, which means the numbering starts from the bottom-left, alternates direction every row, and ends at the top-right. You start at square 1, and each turn you roll a 6-sided die, moving from your current square curr to any square next between curr + 1 and curr + 6, subject to the board boundaries. If next has a ladder or snake (board[r][c] != -1), you are forced to move to its destination. Importantly, you only follow one snake or ladder per move.

The input is a 2D integer matrix representing the board, where -1 denotes an empty cell and any other number represents a snake or ladder destination. The output is the minimum number of dice rolls to reach square n². If it is impossible to reach the end, we return -1.

Constraints tell us that n ranges from 2 to 20, which implies that the board can have at most 400 squares. This is small enough to consider graph traversal approaches. Edge cases include boards where ladders or snakes immediately transport you to the end, boards with no ladders or snakes, and boards where some squares are unreachable due to snake loops.

Approaches

A brute-force approach would attempt to simulate all possible sequences of dice rolls recursively or iteratively, exploring every path from 1 to n². At each square, you would consider moving 1 through 6 steps, follow a ladder or snake if present, and recursively continue. While this guarantees correctness, it is infeasible because the number of paths grows exponentially with the board size.

The key observation for an optimal approach is that the game can be modeled as a shortest path problem on an unweighted graph. Each square is a node, and edges exist from curr to each next reachable with a dice roll, considering snakes and ladders. Since each move has equal cost (one dice roll), Breadth-First Search (BFS) can find the minimum number of moves efficiently. BFS guarantees the shortest path because it explores all positions reachable in k moves before exploring positions reachable in k + 1 moves.

Approach Time Complexity Space Complexity Notes
Brute Force O(6^(n²)) O(n²) Explores all dice roll sequences; infeasible for n up to 20
Optimal (BFS) O(n²) O(n²) Treats the board as a graph and finds shortest path efficiently

Algorithm Walkthrough

  1. Convert the 2D board into a 1D array flattened where index i corresponds to square i + 1. While flattening, handle the boustrophedon pattern: even-indexed rows from the bottom go left-to-right, odd-indexed rows go right-to-left.
  2. Initialize a queue for BFS starting at square 1 (index 0). Track visited squares with a set to avoid revisiting.
  3. Begin BFS. For each current square curr, consider moving to next squares in the range [curr + 1, min(curr + 6, n²)].
  4. If a next square contains a ladder or snake (flattened[next - 1] != -1), move to its destination. Otherwise, stay at next.
  5. If the destination square is n², return the number of moves taken to reach it.
  6. Mark newly visited squares as visited and add them to the BFS queue.
  7. If the queue is empty and the end square has not been reached, return -1.

Why it works: BFS explores all reachable squares in increasing number of dice rolls. By visiting each square only once, we guarantee that the first time we reach a square is with the minimum number of moves. Handling the snakes and ladders as direct jumps ensures we always move optimally in each turn.

Python Solution

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        flattened = [-1] * (n * n)
        idx = 0
        for r in range(n - 1, -1, -1):
            row_range = range(n) if (n - 1 - r) % 2 == 0 else range(n - 1, -1, -1)
            for c in row_range:
                flattened[idx] = board[r][c]
                idx += 1

        queue = deque([(1, 0)])  # (current square, moves)
        visited = set([1])

        while queue:
            curr, moves = queue.popleft()
            if curr == n * n:
                return moves
            for next_sq in range(curr + 1, min(curr + 6, n * n) + 1):
                dest = flattened[next_sq - 1] if flattened[next_sq - 1] != -1 else next_sq
                if dest not in visited:
                    visited.add(dest)
                    queue.append((dest, moves + 1))

        return -1

This implementation first flattens the 2D board into a 1D array while respecting the boustrophedon pattern. BFS ensures exploration of all reachable squares in increasing moves. The visited set prevents revisiting squares, which guarantees optimal performance.

Go Solution

package main

import "container/list"

func snakesAndLadders(board [][]int) int {
    n := len(board)
    flattened := make([]int, n*n)
    idx := 0
    for r := n - 1; r >= 0; r-- {
        var rowRange []int
        if (n-1-r)%2 == 0 {
            rowRange = makeRange(0, n-1, 1)
        } else {
            rowRange = makeRange(n-1, 0, -1)
        }
        for _, c := range rowRange {
            flattened[idx] = board[r][c]
            idx++
        }
    }

    visited := make(map[int]bool)
    queue := list.New()
    queue.PushBack([2]int{1, 0})
    visited[1] = true

    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        curr, moves := elem.Value.([2]int)[0], elem.Value.([2]int)[1]
        if curr == n*n {
            return moves
        }
        for next := curr + 1; next <= curr+6 && next <= n*n; next++ {
            dest := next
            if flattened[next-1] != -1 {
                dest = flattened[next-1]
            }
            if !visited[dest] {
                visited[dest] = true
                queue.PushBack([2]int{dest, moves + 1})
            }
        }
    }
    return -1
}

func makeRange(start, end, step int) []int {
    var res []int
    if step > 0 {
        for i := start; i <= end; i += step {
            res = append(res, i)
        }
    } else {
        for i := start; i >= end; i += step {
            res = append(res, i)
        }
    }
    return res
}

The Go version mirrors the Python logic, using a map for visited tracking and a list.List for BFS queue. A helper function generates the appropriate column iteration for boustrophedon flattening.

Worked Examples

Example 1:

Board flattened to 1D: [ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 35, -1, -1, 13, -1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

BFS queue operations:

Moves Queue Action
0 [(1,0)] Start at 1
1 [(15,1), 2,3,4,5,6] Roll 1 → 6; ladder from 2 → 15
2 [(16,2), 17,18,19,20,21] Next moves considering snakes/ladders
3 [(22,3), ...] Continue BFS
4 [(36,4)] Reach end

Minimum dice rolls = 4.

Example 2:

Board flattened: [ -1, -1, -1, 3 ]

Moves Queue Action
0 [(1,0)] Start at 1
1 [(3,1), 2] Roll 1 → 2, roll 2 → 3 (ladder)

Minimum dice rolls = 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each square is visited at