LeetCode 909: Snakes and Ladders

Problem Restatement

We are given an n x n board for a Snakes and Ladders game.

The squares are numbered from 1 to n^2 in a boustrophedon order. That means the numbering starts from the bottom-left square, goes left to right on one row, then right to left on the next row, alternating direction each row.

From a square curr, one dice roll can move to any square from:

curr + 1

through:

min(curr + 6, n * n)

If the destination square has a snake or ladder, meaning board[r][c] != -1, we must move to board[r][c].

A snake or ladder is followed at most once per dice roll. If its destination also has another snake or ladder, we do not follow the second one.

Return the minimum number of dice rolls needed to reach square n^2. If it cannot be reached, return -1. The official statement defines this one-snake-or-ladder-per-roll rule explicitly.

Input and Output

Function shape:

def snakesAndLadders(board: list[list[int]]) -> int:
    ...

Examples

Example 1:

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],
]

Answer:

4

One shortest route is:

1 -> 2 -> 15 -> 17 -> 13 -> 14 -> 35 -> 36

This uses four dice rolls. The moves through 15, 13, and 35 happen because of ladders or snakes.

Example 2:

board = [
    [-1, -1],
    [-1, 3],
]

Answer:

1

From square 1, we can roll to square 2, then the ladder sends us to square 3.

We do not immediately follow another snake or ladder after that same roll.

First Thought: Simulate Greedily

One tempting idea is to always choose the move that lands farthest ahead after applying a snake or ladder.

That does not always work.

A square that moves far ahead may lead into a bad position later. A smaller move may reach a better ladder. Since each dice roll has equal cost, this is a shortest path problem on an unweighted graph.

The right tool is breadth-first search.

Key Insight

Treat every square as a graph node.

From each square curr, there are up to six outgoing edges:

curr -> curr + 1
curr -> curr + 2
...
curr -> curr + 6

After choosing a destination, apply one snake or ladder if the board says so.

Since every edge represents exactly one dice roll, all edges have the same cost.

Breadth-first search finds the minimum number of dice rolls.

Mapping Square Number to Board Cell

The hardest part is converting a square number into (row, col).

Square numbers start from the bottom row.

Let:

q = square - 1
row_from_bottom = q // n
col_in_row = q % n

The actual row in the matrix is:

row = n - 1 - row_from_bottom

If row_from_bottom is even, the row goes left to right.

If row_from_bottom is odd, the row goes right to left.

So:

if row_from_bottom % 2 == 0:
    col = col_in_row
else:
    col = n - 1 - col_in_row

Algorithm

Use BFS.

1. Start from square 1.
2. Put (1, 0) into a queue, where 0 is the number of moves used so far.
3. Mark square 1 as visited.
4. While the queue is not empty:
   • Pop the current square and move count.
   • If the current square is n^2, return the move count.
   • Try all dice outcomes from 1 to 6.
   • Convert the candidate square into (row, col).
   • If board[row][col] != -1, move to that destination.
   • If the final destination was not visited, mark it and push it into the queue.
5. If BFS ends without reaching n^2, return -1.

Correctness

Each BFS edge represents one valid dice roll from the game.

For a chosen next square, the algorithm applies exactly one snake or ladder if present, matching the problem rule.

BFS explores states by increasing number of dice rolls. It visits all squares reachable in 0 rolls, then all squares reachable in 1 roll, then all squares reachable in 2 rolls, and so on.

Therefore, the first time BFS reaches square n^2, the move count is the minimum possible number of dice rolls.

If BFS finishes without reaching square n^2, then no sequence of legal dice rolls can reach the final square, so returning -1 is correct.

Complexity

Implementation

from collections import deque

class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        n = len(board)
        target = n * n

        def get_cell(square: int) -> tuple[int, int]:
            q = square - 1
            row_from_bottom = q // n
            col_in_row = q % n

            row = n - 1 - row_from_bottom

            if row_from_bottom % 2 == 0:
                col = col_in_row
            else:
                col = n - 1 - col_in_row

            return row, col

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

        while queue:
            square, moves = queue.popleft()

            if square == target:
                return moves

            for step in range(1, 7):
                next_square = square + step

                if next_square > target:
                    break

                row, col = get_cell(next_square)

                if board[row][col] != -1:
                    next_square = board[row][col]

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

        return -1

Code Explanation

The board size and final square are:

n = len(board)
target = n * n

The helper function converts a square label into matrix coordinates:

def get_cell(square: int) -> tuple[int, int]:

We first convert to zero-based numbering:

q = square - 1

Then compute which row it belongs to from the bottom:

row_from_bottom = q // n

The actual matrix row is reversed because matrix row 0 is at the top:

row = n - 1 - row_from_bottom

The column depends on the direction of that row:

if row_from_bottom % 2 == 0:
    col = col_in_row
else:
    col = n - 1 - col_in_row

The BFS starts at square 1 with zero dice rolls:

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

For each square, try all six dice outcomes:

for step in range(1, 7):

If the square has a snake or ladder, apply it once:

if board[row][col] != -1:
    next_square = board[row][col]

Unvisited destinations are added to the queue with one more move:

queue.append((next_square, moves + 1))

Testing

def run_tests():
    s = Solution()

    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],
    ]
    assert s.snakesAndLadders(board) == 4

    board = [
        [-1, -1],
        [-1, 3],
    ]
    assert s.snakesAndLadders(board) == 1

    board = [
        [-1, -1],
        [-1, -1],
    ]
    assert s.snakesAndLadders(board) == 1

    board = [
        [-1, -1, -1],
        [-1, 9, 8],
        [-1, 8, 9],
    ]
    assert s.snakesAndLadders(board) == 1

    print("all tests passed")

run_tests()

Test meaning: