Problem of The Day: Snakes and Ladders

Problem Statement

leetcode problem link

Intuition

The Snakes and Ladders game can be thought of as a graph traversal problem, where each square on the board is a node, and dice rolls determine edges between them (up to 6 edges per node). Given this, a Breadth-First Search (BFS) is the natural choice to find the shortest path (minimum number of dice rolls) from square 1 to square N×N.

Approach

1. Flatten the Board with Zigzag Pattern: The input board is a 2D array with rows going from top to bottom, but the game progresses in a bottom-left to top-right zigzag pattern. We flatten the board into a 1D mapping (jumps) of square index → destination (if a ladder/snake exists).

2. BFS Traversal:

   • Start BFS from square 1 with 0 dice rolls.
   • For each position, simulate all dice rolls from 1 to 6.
   • If the target square has a ladder or snake, jump to the destination.
   • To avoid infinite loops on cyclic ladders/snakes, track seen jumps per path.
   • Keep a global visited set to avoid reprocessing the same square.
   • If we reach square N×N, return the number of moves.

3. Return -1 if the end is unreachable.

Complexity

• Time complexity:
  \(O(N^2)\)
  We potentially visit each square once, and simulate up to 6 moves from each.

• Space complexity:
  \(O(N^2)\)
  For the jumps mapping, visited set, and queue used in BFS.

Code

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        N = len(board)
        jumps = defaultdict(int)
        square_index = 1
        direction = True
        for row in range(N - 1, -1, -1):
            if direction:
                for col in range(N):
                    if board[row][col] != -1:
                        jumps[square_index] = board[row][col]
                    square_index += 1
            else:
                for col in range(N - 1, -1, -1):
                    if board[row][col] != -1:
                        jumps[square_index] = board[row][col]
                    square_index += 1

            direction = not direction

        queue = deque()
        queue.append([1, 0])
        visited = set()
        visited.add(1)
        while queue:
            curr, num_of_rolls = queue.popleft()

            for i in range(curr + 1, min(curr + 6, N**2) + 1):
                next_square_index = i

                seen = set()
                while next_square_index in jumps and next_square_index not in seen:
                    next_square_index = jumps[next_square_index]
                    seen.add(next_square_index)

                if next_square_index == N**2:
                    return num_of_rolls + 1

                if next_square_index not in visited:
                    queue.append([next_square_index, num_of_rolls + 1])
                    visited.add(next_square_index)

        return -1

Editorial

Approach 1: Breadth-first search

from collections import deque


class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        cells = [None] * (n**2 + 1)
        label = 1
        columns = list(range(0, n))
        for row in range(n - 1, -1, -1):
            for column in columns:
                cells[label] = (row, column)
                label += 1
            columns.reverse()
        dist = [-1] * (n * n + 1)
        q = deque([1])
        dist[1] = 0
        while q:
            curr = q.popleft()
            for next in range(curr + 1, min(curr + 6, n**2) + 1):
                row, column = cells[next]
                destination = (board[row][column] if board[row][column] != -1
                               else next)
                if dist[destination] == -1:
                    dist[destination] = dist[curr] + 1
                    q.append(destination)
        return dist[n * n]