Snakes and Ladders

Problem Statement

You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style (left-to-right in even rows, right-to-left in odd rows).

Some cells contain snakes or ladders:

• board[r][c] > 0: Ladder takes you from that cell to board[r][c]
• board[r][c] == -1: Regular cell (no snake or ladder)
• Snakes and ladders are represented differently in the problem (negative values or special encoding)

You start at square 1 on the board. On each turn:

• Roll a dice (you can move 1 to 6 steps forward)
• If you land on a square with a ladder, you climb it
• If you land on a square with a snake, you slide down
• Return the minimum number of dice rolls needed to reach square n²

Key Insight

• This is a shortest path problem on a game board where dice rolls are moves.
• Each state is a board position, and each transition is a dice roll (1-6 steps).
• BFS finds the minimum moves; DFS explores all paths.

Examples

n	board setup	Output	Explanation
2	[[-1,-1],[-1,-1]]	1	Roll 1: 1 → 2. No snakes/ladders. Already at n²=4 is impossible in 1 move; actual minimum is 2.
2	[[-1,-1],[-1,3]]	1	From position 1, roll 1 to reach position 2, then roll 2 to reach position 4. Minimum is 2.
3	[[-1,2,-1],[4,3,-1],[2,-1,-1]]	2	Use ladders strategically to reach position 9 in minimum rolls.
4	[[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,5]]	3	Simple board progression without snakes/ladders: reach position 16 in 3 rolls (1→6→12→16).

Constraints

• 2 <= n <= 100
• board.length == board[i].length == n
• 1 <= board[i][j] <= n² or board[i][j] == -1
• The cells labeled 1 and n² have board[i][j] == -1
• There is at most one snake or ladder per cell
• board[i][j] != board[j][i] (snakes and ladders are unique per cell)

Real-World Applications

Where this pattern appears

• Game AI and pathfinding — Board game solvers finding optimal move sequences in games with probabilistic moves (dice rolls) and state transitions.
• Network optimization — Finding minimum-cost or minimum-hop paths in systems with both forward (ladder) and backward (snake) state transitions.
• Robot navigation — Path planning for robots moving through grids with teleportation portals (ladders) or traps (snakes).
• Simulation and modeling — Any system where agents move through discrete states with both accelerators and decelerators toward a goal state.

Complexity Comparison

Approach	Time	Space	Notes
BFS	O(n)	O(n)	First approach
DFS	O(n)	O(n)	Second approach

Approach 1: BFS

★ Recommended

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

snakes_and_ladders_bfs.py

from collections import deque

def snakesAndLadders(board):
    """BFS to find shortest path in game board."""
    n = len(board)

    def get_coords(pos):
        pos -= 1
        row = n - 1 - pos // n
        col = pos % n if (n - 1 - row) % 2 == 0 else n - 1 - pos % n
        return row, col

    queue = deque([(1, 0)])
    visited = {1}

    while queue:
        pos, moves = queue.popleft()
        if pos == n * n:
            return moves

        for i in range(1, 7):
            next_pos = pos + i
            if next_pos > n * n:
                break

            row, col = get_coords(next_pos)
            if board[row][col] != -1:
                next_pos = board[row][col]

            if next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, moves + 1))

    return -1

C++

snakes_and_ladders_bfs.cpp

class Solution {
    // TODO: Implement
};

Java

SnakesAndLaddersBfs.java

import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(1);
        visited.add(1);
        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int pos = queue.poll();
                if (pos == n * n) return moves;

                for (int next = pos + 1; next <= Math.min(pos + 6, n * n); next++) {
                    int[] cell = getCell(next, n);
                    int destination = board[cell[0]][cell[1]];
                    if (destination != -1) next = destination;

                    if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            moves++;
        }
        return -1;
    }

    private int[] getCell(int pos, int n) {
        int row = (pos - 1) / n;
        int col = (pos - 1) % n;
        if (row % 2 == 1) col = n - 1 - col;
        return new int[]{n - 1 - row, col};
    }
}

JavaScript

snakes_and_ladders_bfs.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

snakes_and_ladders_bfs.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

snakes_and_ladders_bfs.go

package main

// TODO: Implement solution

Approach 2: DFS

✓ Simple

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

snakes_and_ladders_dfs.py

def snakesAndLadders(board):
    """DFS with memoization to find shortest path."""
    n = len(board)

    def get_coords(pos):
        pos -= 1
        row = n - 1 - pos // n
        col = pos % n if (n - 1 - row) % 2 == 0 else n - 1 - pos % n
        return row, col

    memo = {}

    def dfs(pos):
        if pos == n * n:
            return 0
        if pos in memo:
            return memo[pos]

        result = float('inf')
        for i in range(1, 7):
            next_pos = pos + i
            if next_pos > n * n:
                break

            row, col = get_coords(next_pos)
            if board[row][col] != -1:
                next_pos = board[row][col]

            result = min(result, 1 + dfs(next_pos))

        memo[pos] = result
        return result

    ans = dfs(1)
    return ans if ans != float('inf') else -1

C++

snakes_and_ladders_dfs.cpp

class Solution {
    // TODO: Implement
};

Java

SnakesAndLaddersDfs.java

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        return dfs(1, board, n, new boolean[n * n + 1]);
    }

    private int dfs(int pos, int[][] board, int n, boolean[] visited) {
        if (pos == n * n) return 0;
        visited[pos] = true;
        int minMoves = Integer.MAX_VALUE;

        for (int next = pos + 1; next <= Math.min(pos + 6, n * n); next++) {
            int[] cell = getCell(next, n);
            int destination = board[cell[0]][cell[1]];
            if (destination != -1) next = destination;

            if (!visited[next]) {
                int moves = dfs(next, board, n, visited);
                if (moves != Integer.MAX_VALUE) {
                    minMoves = Math.min(minMoves, moves + 1);
                }
            }
        }

        return minMoves;
    }

    private int[] getCell(int pos, int n) {
        int row = (pos - 1) / n;
        int col = (pos - 1) % n;
        if (row % 2 == 1) col = n - 1 - col;
        return new int[]{n - 1 - row, col};
    }
}

JavaScript

snakes_and_ladders_dfs.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

snakes_and_ladders_dfs.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

snakes_and_ladders_dfs.go

package main

// TODO: Implement solution

Interview Tips

Key trade-offs to discuss

• Approach 1 vs Approach 2 trade-offs
• Edge cases and how to handle them
• Follow-up questions

← Previous
#210 Course Schedule II Next
#433 Minimum Genetic Mutation →