Snake and Ladder Problem

Problem Overview

Each dice throw costs one move and can advance 1..6 cells, optionally followed by an instant snake or ladder jump.

Intuition

Each dice throw costs one move and can advance 1..6 cells, optionally followed by an instant snake or ladder jump. That is an unweighted shortest-path graph on cells 1..n^2, so BFS from 1 yields the minimum throws to reach n^2 (or -1 if unreachable).

Algorithm

1Build jump[1..n^2] from ladder/snake pairs (lad and sn store start,end alternating).
2BFS from cell 1 with a visited array; each queue layer is one dice throw.
3From curr, try curr+1..curr+6 within the board; if jump[next] is set, go to jump[next].
4When N = n*n is dequeued, return the current throw count.
5If the queue empties first, return -1.

Example Walkthrough

Input: n = 6, ladders include 5->8 and 11->35, snakes include 17->4 (illustrative 6x6)

1. One optimal path: 1 -dice4-> 5 -ladder-> 8 -dice3-> 11 -ladder-> 35 -dice1-> 36.
2. BFS first reaches 36 after 3 throws.

Output: 3

Common Pitfalls

• Mark visited on the destination after applying the jump, not on the pre-jump cell alone.
• Do not move past n^2 - discard dice results that overshoot.
• Snakes and ladders are applied immediately; you do not roll again in the same throw.
• Return -1 when the last cell is unreachable (e.g. blocked by snakes).

Snake and Ladder Problem.java

Java

// Approach: Model the n x n board (cells 1..n^2) as an unweighted graph: from
// cell c, edges go to c+1..c+6 (if in range), then follow a snake/ladder jump
// if present. BFS from 1 finds the minimum dice throws to reach n^2.
// Complexity: O(n^2) time and O(n^2) space.

import java.util.*;

class Solution {

    public int minThrows(int n, int[] lad, int[] sn) {
        int N = n * n;
        int[] jump = new int[N + 1];
        Arrays.fill(jump, -1);

        for (int i = 0; i < lad.length; i += 2) {
            jump[lad[i]] = lad[i + 1];
        }
        for (int i = 0; i < sn.length; i += 2) {
            jump[sn[i]] = sn[i + 1];
        }

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        q.offer(1);
        visited[1] = true;
        int throwsCount = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.poll();
                if (curr == N) {
                    return throwsCount;
                }
                for (int dice = 1; dice <= 6; dice++) {
                    int next = curr + dice;
                    if (next > N) {
                        continue;
                    }
                    if (jump[next] != -1) {
                        next = jump[next];
                    }
                    if (!visited[next]) {
                        visited[next] = true;
                        q.offer(next);
                    }
                }
            }
            throwsCount++;
        }

        return -1;
    }
}

Was this solution helpful?