Snakes and Ladders - Practice Coding Problems

Snakes and Ladders - Problem

You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n²)]. This choice simulates the result of a standard 6-sided die roll.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n².

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c].

Squares 1 and n² are not the starting points of any snake or ladder.

Note: You only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

Return the least number of dice rolls required to reach the square n². If it is not possible to reach the square, return -1.

Input & Output

Example 1 — Small Board with Ladder

$ Input: board = [[-1,4],[-1,3]]

› Output: 1

💡 Note: Start at 1. Roll die to reach 2, but there's a ladder at position 2 that takes you directly to position 4 (the target). Total moves: 1.

Example 2 — Larger Board

$ Input: 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]]

› Output: 4

💡 Note: 36 cells total. Need minimum 4 dice rolls to reach cell 36, using optimal path that may include ladders and avoiding snakes.

Example 3 — Impossible Case

$ Input: board = [[-1,-1],[-1,1]]

› Output: -1

💡 Note: There's a snake at position 4 that brings you back to position 1, creating an infinite loop. Impossible to reach the target.

Constraints

n == board.length == board[i].length
2 ≤ n ≤ 20
board[i][j] is either -1 or in the range [1, n²]
The squares labeled 1 and n² do not have any ladders or snakes

Visualization

Tap to expand

Understanding the Visualization

Input

n×n board with snakes (-1) and ladders (destination)

Process

BFS from position 1, try dice rolls 1-6 each turn

Output

Minimum moves to reach position n²

Key Takeaway

🎯 Key Insight: BFS naturally finds shortest paths in unweighted graphs like this board game

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to use BFS to explore the board level by level, treating each dice roll as an edge in a graph. Since we want the minimum number of dice rolls, BFS guarantees we find the shortest path. Best approach is BFS. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search (Optimal)	O(n²)	O(n²)	Use BFS to find the minimum number of moves by exploring level by level
Brute Force DFS	O(6ⁿ)	O(n²)	Try all possible dice roll sequences using depth-first search

Breadth-First Search (Optimal) — Algorithm Steps

Start BFS from position 1
For each position, try all dice rolls 1-6
Handle snakes/ladders by jumping to destination
Track visited positions to avoid cycles
Return moves when reaching target

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start BFS from position 1 with queue and visited set

Level Exploration

Process all positions at current distance simultaneously

Shortest Path

First time we reach target gives minimum moves

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int pos;
    int moves;
} State;

void getPosition(int square, int n, int* r, int* c) {
    int row = (square - 1) / n;
    int col = (square - 1) % n;
    if (row % 2 == 1) {
        col = n - 1 - col;
    }
    *r = n - 1 - row;
    *c = col;
}

int solution(int** board, int n) {
    int target = n * n;
    State queue[10000];
    int front = 0, rear = 0;
    bool visited[target + 1];
    memset(visited, false, sizeof(visited));
    
    queue[rear++] = (State){1, 0};
    visited[1] = true;
    
    while (front < rear) {
        State curr = queue[front++];
        
        if (curr.pos == target) {
            return curr.moves;
        }
        
        for (int dice = 1; dice <= 6; dice++) {
            int nextPos = curr.pos + dice;
            if (nextPos > target) continue;
            
            int r, c;
            getPosition(nextPos, n, &r, &c);
            if (board[r][c] != -1) {
                nextPos = board[r][c];
            }
            
            if (!visited[nextPos]) {
                visited[nextPos] = true;
                queue[rear++] = (State){nextPos, curr.moves + 1};
            }
        }
    }
    
    return -1;
}

int main() {
    // Simplified parsing for 6x6 board example
    int n = 6;
    int** board = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        board[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            board[i][j] = -1;
        }
    }
    
    // Add some ladders and snakes
    board[4][0] = 15; // ladder at position 2
    board[2][5] = 13; // snake at position 16
    
    printf("%d\n", solution(board, n));
    
    for (int i = 0; i < n; i++) {
        free(board[i]);
    }
    free(board);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each cell is visited at most once, and there are n² cells on the board

⚠ Quadratic Growth

Space Complexity

O(n²)

Queue and visited array can store up to n² positions

⚠ Quadratic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler