909. Snakes and Ladders

Problem Description

In this problem, we are given a square board of n x n size, labeled with consecutive numbers from 1 to n^2 in a Boustrophedon style, meaning that the numbers start from the bottom left corner and snake back and forth row by row; the direction of numbering alternates with each row. The player begins at square 1 and the goal is to reach square n^2. On each turn, the player can move to a square in the range of 1 to 6 squares ahead from their current position, as if rolling a six-sided die.

Some squares contain the start of a snake or ladder, indicated by a non-negative number in board[r][c]. If a player lands on such a square, they must follow it to the designated end square. The start and end squares of the board don't contain snakes or ladders. The player only follows a snake or ladder for a single move, not chaining multiple snakes or ladders in a single turn.

The objective is to find the minimum number of moves needed to reach the end of the board. We have to consider the effect of dice rolls, the presence of snakes and ladders which can alter the player's position significantly, and the unique movement pattern due to the Boustrophedon style numbering. It's important to track visited squares to avoid infinite loops (visiting the same squares over and over) and to make sure not to follow the same snake or ladder twice in a single move.

Flowchart Walkthrough

Let's analyze Leetcode 909, Snakes and Ladders, using the Flowchart. We'll step through the decision-making process to determine the appropriate algorithm:

Is it a graph?
- Yes: In Snakes and Ladders, the board can be visualized as a graph where each square is a node, and a direct movement (by dice roll) from one square to another represents an edge.
Is it a tree?
- No: The game board isn't strictly hierarchical and can have multiple paths due to the snakes and ladders acting as shortcuts or setbacks, so it's not a tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: Although the board can be seen as directed because you move forward (and occasionally backward with snakes), it's a small, constrained environment with specific rules that don't typically involve acyclic graph properties.
Is the problem related to shortest paths?
- Yes: The goal is to find the least number of moves to reach the final square, which translates into finding the shortest path from the start to the end node.
Is the graph weighted?
- No: Each move, whether it's a simple move or via a ladder/snake, is considered a single step, equivalent to one roll of the dice.

Based on the responses leading us through the flowchart, we have established that the problem is an unweighted shortest path finding on a graph. Thus, Breadth-First Search (BFS) is an appropriate technique to use. BFS is well-suited for unweighted graphs where we need to find the shortest path, as it explores all nodes at the present depth prior to moving on to nodes at the next depth level.

Intuition

To solve this problem, we employ a Breadth-First Search (BFS) algorithm. BFS is a suitable approach here because it is excellent for finding the shortest path in an unweighted graph, which essentially our game board is. Each roll of the die represents a potential transition from one node (square) to another. Moreover, since snakes and ladders can move the player to non-adjacent nodes, BFS can handle these jumps seamlessly while keeping track of the shortest path.

We maintain a queue to represent game states we need to visit (game states are just positions on the board). We also keep track of visited positions to avoid processing the same state multiple times. For each turn, we consider all reachable positions within a roll of a six-sided die and follow snakes and ladders immediately as they only affect the current move. By gradually exploring all possibilities, we ensure we don't miss any potential paths that might lead to the goal in fewer moves, and once we reach n^2, we can return the number of moves taken.

The function get(x) in the solution converts the label of a square to its coordinates on the board, taking into account the alternating direction of the rows. The use of a set vis ensures that each square is visited no more than once, optimizing the search and avoiding cycles. The BFS loop increments a counter ans which represents the number of moves taken so far until it either finds the end or exhausts all possible paths.

Learn more about Breadth-First Search patterns.

Solution Approach

The implemented solution approach uses Breadth-First Search (BFS), a popular search algorithm, to efficiently find the shortest path to reach the end of the board from the start. Here's the walkthrough of how the solution functions:

BFS Queue: We use a deque (a queue that allows inserting and removing from both ends) to store the squares we need to visit. Initially, the queue contains just the first square 1.
Visited Set: A set vis is used to track the squares we have already visited to prevent revisiting and consequently, getting stuck in loops.
Move Count: ans is a counter that keeps track of the number of moves made so far. It gets incremented after exploring all possible moves within one round of a die roll.
Main Loop: The BFS is implemented in a while loop that continues as long as there are squares to visit in the queue.
Exploring Moves: For each current position, we look at all possible positions we could land on with a single die roll (six possibilities at most), which are the squares numbered from curr + 1 to min(curr + 6, n^2). We use the get(x) function to calculate the corresponding board coordinates from a square number.
Following Snakes or Ladders: If the calculated position has a snake or ladder (board[i][j] != -1), we move to the destination of that snake or ladder as described by the board (next = board[i][j]).
Visiting and Queuing: If the next square (factoring in any snakes or ladders) has not been visited, we add it to the queue and mark it visited.
Checking for Completion: If, during the BFS, we reach the last square n^2, we immediately return the number of moves made (ans) since this would represent the shortest path to the end.
Return Case: If it is not possible to reach the end - which we know if the queue gets exhausted and the end has not been reached - the function returns -1.

The BFS algorithm, coupled with the correct handling of the unique numbering and presence of snakes and ladders, ensures an optimized search for the quickest path to victory.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small example to illustrate how it works.

Example Board

Suppose we have a 3x3 board, which means n=3 and our board looks like this:

+-----+-----+-----+
|  7  |  8  |  9  |
+-----+-----+-----+
|  6  |  5  |  4  |
+-----+-----+-----+
|  1  |  -2 |  3  |
+-----+-----+-----+

The -2 at position 2 means there is a ladder that takes the player directly from square 2 to square 3. The goal is to reach square 9 in the minimum number of moves.

Walkthrough Steps

Initialize the BFS queue with the starting square [1], add 1 to the visited set, and set ans (the move counter) to 0.
Begin the BFS loop.
- Dequeue 1, the current square.
- Explore all possible moves (squares 2 through 6, but since our board is 3x3, squares 4 through 6 do not exist).
- Square 2 has a ladder to square 3, so we move to 3 instead of stopping at 2.
- Add 3 to the visited set and enqueue it.
Increment ans to 1 (we've made one move).
Dequeue 3 and explore the next moves (4 through 9, but since we can reach at most 8 with a roll of six, we only consider up to 8).
- None of the squares from 4 to 8 contain a snake or ladder, so we enqueue squares 4, 5, 6, 7, and 8 and mark them visited.
- The end square 9 cannot be reached in this turn.
Increment ans to 2 (we've made two moves).
Dequeue 4, 5, 6, 7, and 8 in the next iterations. From any of these squares, a roll of one or more will reach the end square 9.
Once 9 is reached, return the current ans value, which now is 3 as the minimum number of moves taken to reach the end of the board.

Hence, using this method, we determine that the minimum number of moves needed to reach the end of this 3x3 Boustrophedon style snake and ladder board is 3.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def snakesAndLadders(self, board: List[List[int]]) -> int:
5        # Helper function to map the board number to board coordinates (i,j)
6        def get_square_coordinates(square_number):
7            row, col = (square_number - 1) // board_size, (square_number - 1) % board_size
8            if row % 2 == 1:
9                # On odd rows, the counting is from right to left.
10                col = board_size - 1 - col
11            # Transform row to start from bottom of board
12            return board_size - 1 - row, col
13
14        board_size = len(board)  # n by n board
15        queue = deque([1])  # Start from square 1
16        visited = {1}  # Keep track of visited squares
17        steps = 0  # Counter for number of moves
18
19        while queue:
20            # Process all squares at the current depth.
21            for _ in range(len(queue)):
22                current_square = queue.popleft()
23
24                # Win condition: reached the last square
25                if current_square == board_size * board_size:
26                    return steps
27
28                # Check all possible next moves by dice roll (1-6)
29                for next_square in range(current_square + 1, min(current_square + 7, board_size * board_size + 1)):
30                    i, j = get_square_coordinates(next_square)
31
32                    # If there's a ladder or snake, take it.
33                    if board[i][j] != -1:
34                        next_square = board[i][j]
35
36                    # If next square has not been visited, add it to the queue
37                    if next_square not in visited:
38                        queue.append(next_square)
39                        visited.add(next_square)
40
41            # Increment the number of moves after expanding all possible moves at current depth.
42            steps += 1
43      
44        # If we have exited the loop without reaching the last square, it's not possible to win.
45        return -1
46

1class Solution {
2    private int boardSize;
3
4    // Method to find the shortest path to reach the last square
5    public int snakesAndLadders(int[][] board) {
6        boardSize = board.length; // Get the size of the board (n x n)
7        Deque<Integer> queue = new ArrayDeque<>(); // A queue to perform BFS
8        queue.offer(1); // Start from the first square
9        boolean[] visited = new boolean[boardSize * boardSize + 1]; // Visited array to keep track of visited squares
10        visited[1] = true; // Mark the first square as visited
11        int moves = 0; // Moves counter
12      
13        // Perform BFS to reach the last square
14        while (!queue.isEmpty()) {
15            for (int i = queue.size(); i > 0; --i) { // Iterate over current level
16                int current = queue.poll(); // Get the current square
17                if (current == boardSize * boardSize) { // Check if reached the end
18                    return moves;
19                }
20                // Explore the next 6 possible moves
21                for (int k = current + 1; k <= Math.min(current + 6, boardSize * boardSize); ++k) {
22                    int[] position = convertToPosition(k); // Convert square number to board coordinates
23                    int next = k; // Next square
24                    // Check if there's a snake or ladder in the square
25                    if (board[position[0]][position[1]] != -1) {
26                        next = board[position[0]][position[1]]; // Go to the new square
27                    }
28                    // If it's not visited, mark as visited and add to the queue
29                    if (!visited[next]) {
30                        visited[next] = true;
31                        queue.offer(next);
32                    }
33                }
34            }
35            moves++; // Increment move count after finishing one level in BFS
36        }
37        return -1; // Return -1 if it's impossible to reach the end
38    }
39
40    // Convert the square number to board coordinates (i, j)
41    private int[] convertToPosition(int squareNum) {
42        int row = (squareNum - 1) / boardSize;
43        int col = (squareNum - 1) % boardSize;
44        // In even rows (from the top), the order is right to left
45        if (row % 2 == 1) {
46            col = boardSize - 1 - col; 
47        }
48        // Convert row to the actual row in the board from the bottom
49        return new int[] {boardSize - 1 - row, col};
50    }
51}
52

1class Solution {
2public:
3    int boardSize; // The size of the board is stored at the class level.
4
5    // The main function to play the game on the given board.
6    int snakesAndLadders(vector<vector<int>>& board) {
7        boardSize = board.size(); // Initial board size
8        queue<int> positionsQueue; // Queue to hold positions to explore
9        positionsQueue.push(1); // Starting position
10        vector<bool> visited(boardSize * boardSize + 1, false); // Visited squares
11        visited[1] = true; // Start square is visited
12        int moves = 0; // Counter for number of moves
13
14        // BFS to find the shortest path
15        while (!positionsQueue.empty()) {
16            int levelSize = positionsQueue.size();
17            for (int i = 0; i < levelSize; ++i) {
18                int current = positionsQueue.front();
19                positionsQueue.pop();
20              
21                // Check if we've reached the last square
22                if (current == boardSize * boardSize) return moves;
23              
24                // Explore each possibility from the current position
25                for (int nextPos = current + 1; nextPos <= min(current + 6, boardSize * boardSize); ++nextPos) {
26                    auto position = convertTo2D(nextPos); // Convert 1D position to 2D grid indices
27                    int target = nextPos;
28                    int row = position.first, col = position.second;
29                    // If there is a ladder or snake, move to its end.
30                    if (board[row][col] != -1) target = board[row][col];
31                    // If the target square is not visited, add it to queue
32                    if (!visited[target]) {
33                        visited[target] = true;
34                        positionsQueue.push(target);
35                    }
36                }
37            }
38            ++moves; // Increment move count after each level of BFS.
39        }
40        return -1; // If we are here, there is no solution.
41    }
42
43    // Converts a 1D array index to 2D grid indices considering snaking rows.
44    pair<int, int> convertTo2D(int pos) {
45        int row = (pos - 1) / boardSize;
46        int col = (pos - 1) % boardSize;
47        if (row % 2 == 1) { // For odd rows we reverse the column index.
48            col = boardSize - 1 - col;
49        }
50        // Convert row from bottom to top because the last row of the board is board grid 1D index 1.
51        row = boardSize - 1 - row;
52        return {row, col};
53    }
54};
55

1// The size of the board is stored as a global variable.
2let boardSize: number;
3
4// Converts a 1D array index to 2D grid indices considering snaking rows.
5function convertTo2D(pos: number): [number, number] {
6    const row = Math.floor((pos - 1) / boardSize);
7    let col = (pos - 1) % boardSize;
8    if (row % 2 === 1) { 
9        // For odd rows (according to zero-index), we reverse the column index.
10        col = boardSize - 1 - col;
11    }
12    // Convert row from bottom to top as the last row of the board corresponds to the first 1D index.
13    const convertedRow = boardSize - 1 - row;
14    return [convertedRow, col];
15}
16
17// The main function to play the game on the given board.
18function snakesAndLadders(board: number[][]): number {
19    boardSize = board.length; // Initialize board size
20    const positionsQueue: number[] = []; // Queue to hold positions to explore
21    positionsQueue.push(1); // Starting position
22    const visited = new Array(boardSize * boardSize + 1).fill(false); // Visited squares
23    visited[1] = true; // Start square is visited
24    let moves = 0; // Counter for number of moves
25
26    // BFS to find the shortest path.
27    while (positionsQueue.length > 0) {
28        const levelSize = positionsQueue.length;
29        for (let i = 0; i < levelSize; ++i) {
30            const current = positionsQueue.shift()!;
31          
32            // Check if we've reached the last square.
33            if (current === boardSize * boardSize) return moves;
34          
35            // Explore each possibility from the current position.
36            for (let nextPos = current + 1; nextPos <= Math.min(current + 6, boardSize * boardSize); ++nextPos) {
37                const [row, col] = convertTo2D(nextPos); // Convert 1D position to 2D grid indices.
38                let target = nextPos;
39              
40                // If there is a ladder or snake, move to its end.
41                if (board[row][col] !== -1) target = board[row][col];
42              
43                // If the target square is not visited, add it to the queue.
44                if (!visited[target]) {
45                    visited[target] = true;
46                    positionsQueue.push(target);
47                }
48            }
49        }
50        moves++; // Increment the move count after each level of BFS.
51    }
52    return -1; // If we are here, there is no solution.
53}
54

Time and Space Complexity

The given Python code represents a solution for finding the minimum number of moves to reach the end of a snake and ladder board game using a Breadth-First-Search (BFS) algorithm. To analyze the time and space complexity, I will break down the operations performed by the code.

Time Complexity

The time complexity of the solution is determined by the number of vertices in the graph and the number of edges that are explored in the BFS algorithm. Each cell in the board can be considered a vertex, and the possible moves from each cell form the edges.

The outer while loop runs as long as there are elements in the queue q. In the worst case, every cell could be enqueued once, which corresponds to the number of cells in the board, n * n.
For each element in the queue, the inner for loop considers up to 6 possible moves (representing rolling a die).
The helper function get, which translates a linear board position to a matrix position, is constant time, O(1), for each call.

The complexity for each layer of vertices explored is O(6) due to the six possible moves (the die roll), resulting in a total time complexity of O(n^2 * 6). Since constant factors are dropped in Big O notation, the overall time complexity simplifies to O(n^2).

Space Complexity

The space complexity of the solution is determined by the additional space required by data structures that store intermediate results or states during the execution of the algorithm.

The queue q can hold all the vertices in the worst case, so its space complexity is O(n * n), since each cell could be visited once.
The set vis also has a space complexity of O(n * n) as it may contain a unique entry for every cell in the worst-case scenario.
The get function uses a constant amount of space.

Considering both the queue and visited set, the space complexity is O(n^2).

Therefore, the overall time complexity is O(n^2), and overall space complexity is O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know