Snakes and Ladders

Medium Graphs BFS for shortest path Original on LeetCode

Snakes and Ladders is a medium graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (bfs over squares), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated relaxation) up.

Problem

You play on an n × n board whose squares are numbered 1 to n² in a zigzag: numbering starts at the bottom-left corner and runs left to right along the bottom row, then right to left along the row above, and keeps alternating direction as it moves up.

You start on square 1. Each turn you roll a six-sided die and move from square s to any square from s + 1 to min(s + 6, n²) (you choose the roll). If board[r][c] of the square you land on is not -1, it is a snake or ladder and you must move to square board[r][c]. You follow at most one snake or ladder per turn, even if the square you are sent to has its own.

Return the fewest turns needed to reach square n², or -1 if it cannot be reached.

Examples

Example 1

Input
board = [[-1, -1, -1], [-1, -1, -1], [-1, 9, -1]]
Output
1
Why
Square 2 (bottom row, middle) has a ladder to square 9. Roll a 1, climb the ladder, and you are done.

Example 2

Input
board = [[-1, -1, -1, -1], [-1, -1, 3, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]]
Output
3
Why
Square 11 is a snake back to 3, so avoid it. Each roll moves at most 6, so 1 → 7 → 13 → 16 is as fast as it gets.

Example 3

Input
board = [[1, -1, -1], [1, 1, 1], [-1, 1, 1]]
Output
-1
Why
Squares 2 to 7 are all snakes back to square 1, so no roll from square 1 ever gets further.

Constraints

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is -1 or between 1 and n².
  • Squares 1 and n² never hold a snake or ladder.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (repeated relaxation)O(n⁴)O(n²)
Optimal (BFS over squares)O(n²)O(n²)

1Brute force (repeated relaxation)

TimeO(n⁴)Up to n² sweeps, each touching n² squares with 6 rolls.
SpaceO(n²)The flattened board and the dist array.

Keep the best known roll count for every square. Sweep over all squares again and again, improving the six squares each one can reach, until a full sweep changes nothing. This is Bellman-Ford on the board.

  1. Flatten the board into jump[1..n²] using the zigzag numbering.
  2. dist[1] = 0, all others infinity.
  3. Repeat: for every square s with a finite dist, for each roll k in 1..6 with s + k <= n², let t = jump[s + k] if it exists, else s + k, and set dist[t] = min(dist[t], dist[s] + 1).
  4. Stop when a sweep makes no change; return dist[n²] or -1.
class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length, total = n * n;
        int[] jump = flatten(board);
        int[] dist = new int[total + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int s = 1; s <= total; s++) {
                if (dist[s] == Integer.MAX_VALUE) continue;
                for (int k = 1; k <= 6 && s + k <= total; k++) {
                    int t = jump[s + k] != -1 ? jump[s + k] : s + k;
                    if (dist[s] + 1 < dist[t]) {
                        dist[t] = dist[s] + 1;
                        changed = true;
                    }
                }
            }
        }
        return dist[total] == Integer.MAX_VALUE ? -1 : dist[total];
    }

    private int[] flatten(int[][] board) {
        int n = board.length;
        int[] jump = new int[n * n + 1];
        for (int s = 1; s <= n * n; s++) {
            int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
            if (q % 2 == 1) c = n - 1 - c;
            jump[s] = board[r][c];
        }
        return jump;
    }
}

2Optimal (BFS over squares)

TimeO(n²)Each of the n² squares is dequeued once and tries 6 rolls.
SpaceO(n²)The flattened board, the seen array and the queue.

All moves cost one roll, so breadth-first search from square 1 reaches every square in the fewest rolls. The first time the queue pops square n², its level is the answer.

  1. Flatten the board into jump[1..n²] with the zigzag numbering.
  2. Push square 1 with 0 rolls and mark it seen.
  3. Pop s; for k in 1..6 with s + k <= n², let t = jump[s + k] if it is not -1, else s + k.
  4. If t == n² return rolls + 1; otherwise push t if unseen.
  5. If the queue empties, return -1.
class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length, total = n * n;
        int[] jump = new int[total + 1];
        for (int s = 1; s <= total; s++) {
            int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
            if (q % 2 == 1) c = n - 1 - c;
            jump[s] = board[r][c];
        }
        if (total == 1) return 0;
        boolean[] seen = new boolean[total + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(1);
        seen[1] = true;
        int rolls = 0;
        while (!queue.isEmpty()) {
            rolls++;
            for (int size = queue.size(); size > 0; size--) {
                int s = queue.poll();
                for (int k = 1; k <= 6 && s + k <= total; k++) {
                    int t = jump[s + k] != -1 ? jump[s + k] : s + k;
                    if (t == total) return rolls;
                    if (!seen[t]) {
                        seen[t] = true;
                        queue.offer(t);
                    }
                }
            }
        }
        return -1;
    }
}

Edge cases to test

  • A ladder whose top is the head of another snake or ladder: you only take the first one
  • The goal cannot be reached because every square in reach sends you back
  • A 2 × 2 board, where one roll of 3 already finishes
  • Odd rows (counted from the bottom) are numbered right to left

Hints

Hint 1

Each square is a node; a roll is an edge to one of the next six squares, redirected if that square has a snake or ladder.

Hint 2

Every edge costs one roll, so the fewest rolls is a shortest path in an unweighted graph.

Hint 3

Write a helper that turns a square number into (row, column), remembering the zigzag numbering.

FAQ

What is the best time complexity for Snakes and Ladders?

Optimal (BFS over squares) runs in O(n²) time and O(n²) extra space. Each of the n² squares is dequeued once and tries 6 rolls.

Which pattern does Snakes and Ladders use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Snakes and Ladders?

Yes. Brute force (repeated relaxation) takes O(n⁴) time and O(n²) space. Keep the best known roll count for every square.

Which edge cases should I test for Snakes and Ladders?

A ladder whose top is the head of another snake or ladder: you only take the first one; The goal cannot be reached because every square in reach sends you back; A 2 × 2 board, where one roll of 3 already finishes; Odd rows (counted from the bottom) are numbered right to left.