Snakes and Ladders
Snakes and Ladders is a medium graphs problem solved with the bfs for shortest path pattern.
The best approach, optimal (bfs over squares), runs in O(n²) time and O(n²) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated relaxation) up.
Problem
You play on an n × n board whose squares are numbered 1 to n² in a zigzag: numbering starts at the bottom-left corner and runs left to right along the bottom row, then right to left along the row above, and keeps alternating direction as it moves up.
You start on square 1. Each turn you roll a six-sided die and move from square s to any square from s + 1 to min(s + 6, n²) (you choose the roll). If board[r][c] of the square you land on is not -1, it is a snake or ladder and you must move to square board[r][c]. You follow at most one snake or ladder per turn, even if the square you are sent to has its own.
Return the fewest turns needed to reach square n², or -1 if it cannot be reached.
Examples
Example 1
- Input
board = [[-1, -1, -1], [-1, -1, -1], [-1, 9, -1]]- Output
1- Why
- Square 2 (bottom row, middle) has a ladder to square 9. Roll a 1, climb the ladder, and you are done.
Example 2
- Input
board = [[-1, -1, -1, -1], [-1, -1, 3, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]]- Output
3- Why
- Square 11 is a snake back to 3, so avoid it. Each roll moves at most 6, so 1 → 7 → 13 → 16 is as fast as it gets.
Example 3
- Input
board = [[1, -1, -1], [1, 1, 1], [-1, 1, 1]]- Output
-1- Why
- Squares 2 to 7 are all snakes back to square 1, so no roll from square 1 ever gets further.
Constraints
n == board.length == board[i].length2 <= n <= 20board[i][j]is-1or between1andn².- Squares
1andn²never hold a snake or ladder.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeated relaxation) | O(n⁴) | O(n²) |
| Optimal (BFS over squares) | O(n²) | O(n²) |
1Brute force (repeated relaxation)
O(n⁴)Up to n² sweeps, each touching n² squares with 6 rolls.O(n²)The flattened board and the dist array.Keep the best known roll count for every square. Sweep over all squares again and again, improving the six squares each one can reach, until a full sweep changes nothing. This is Bellman-Ford on the board.
- Flatten the board into jump[1..n²] using the zigzag numbering.
- dist[1] = 0, all others infinity.
- Repeat: for every square s with a finite dist, for each roll k in 1..6 with s + k <= n², let t = jump[s + k] if it exists, else s + k, and set dist[t] = min(dist[t], dist[s] + 1).
- Stop when a sweep makes no change; return dist[n²] or -1.
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length, total = n * n;
int[] jump = flatten(board);
int[] dist = new int[total + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
boolean changed = true;
while (changed) {
changed = false;
for (int s = 1; s <= total; s++) {
if (dist[s] == Integer.MAX_VALUE) continue;
for (int k = 1; k <= 6 && s + k <= total; k++) {
int t = jump[s + k] != -1 ? jump[s + k] : s + k;
if (dist[s] + 1 < dist[t]) {
dist[t] = dist[s] + 1;
changed = true;
}
}
}
}
return dist[total] == Integer.MAX_VALUE ? -1 : dist[total];
}
private int[] flatten(int[][] board) {
int n = board.length;
int[] jump = new int[n * n + 1];
for (int s = 1; s <= n * n; s++) {
int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
if (q % 2 == 1) c = n - 1 - c;
jump[s] = board[r][c];
}
return jump;
}
}class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
total = n * n
jump = self.flatten(board)
INF = float('inf')
dist = [INF] * (total + 1)
dist[1] = 0
changed = True
while changed:
changed = False
for s in range(1, total + 1):
if dist[s] == INF:
continue
for k in range(1, 7):
if s + k > total:
break
t = jump[s + k] if jump[s + k] != -1 else s + k
if dist[s] + 1 < dist[t]:
dist[t] = dist[s] + 1
changed = True
return -1 if dist[total] == INF else dist[total]
def flatten(self, board: List[List[int]]) -> List[int]:
n = len(board)
jump = [-1] * (n * n + 1)
for s in range(1, n * n + 1):
q = (s - 1) // n
r = n - 1 - q
c = (s - 1) % n
if q % 2 == 1:
c = n - 1 - c
jump[s] = board[r][c]
return jumpclass Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size(), total = n * n;
vector<int> jump = flatten(board);
vector<int> dist(total + 1, INT_MAX);
dist[1] = 0;
bool changed = true;
while (changed) {
changed = false;
for (int s = 1; s <= total; s++) {
if (dist[s] == INT_MAX) continue;
for (int k = 1; k <= 6 && s + k <= total; k++) {
int t = jump[s + k] != -1 ? jump[s + k] : s + k;
if (dist[s] + 1 < dist[t]) {
dist[t] = dist[s] + 1;
changed = true;
}
}
}
}
return dist[total] == INT_MAX ? -1 : dist[total];
}
private:
vector<int> flatten(vector<vector<int>>& board) {
int n = board.size();
vector<int> jump(n * n + 1, -1);
for (int s = 1; s <= n * n; s++) {
int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
if (q % 2 == 1) c = n - 1 - c;
jump[s] = board[r][c];
}
return jump;
}
};function snakesAndLadders(board) {
const n = board.length, total = n * n;
const jump = new Array(total + 1).fill(-1);
for (let s = 1; s <= total; s++) {
const q = Math.floor((s - 1) / n), r = n - 1 - q;
let c = (s - 1) % n;
if (q % 2 === 1) c = n - 1 - c;
jump[s] = board[r][c];
}
const dist = new Array(total + 1).fill(Infinity);
dist[1] = 0;
let changed = true;
while (changed) {
changed = false;
for (let s = 1; s <= total; s++) {
if (dist[s] === Infinity) continue;
for (let k = 1; k <= 6 && s + k <= total; k++) {
const t = jump[s + k] !== -1 ? jump[s + k] : s + k;
if (dist[s] + 1 < dist[t]) {
dist[t] = dist[s] + 1;
changed = true;
}
}
}
}
return dist[total] === Infinity ? -1 : dist[total];
}2Optimal (BFS over squares)
O(n²)Each of the n² squares is dequeued once and tries 6 rolls.O(n²)The flattened board, the seen array and the queue.All moves cost one roll, so breadth-first search from square 1 reaches every square in the fewest rolls. The first time the queue pops square n², its level is the answer.
- Flatten the board into jump[1..n²] with the zigzag numbering.
- Push square 1 with 0 rolls and mark it seen.
- Pop s; for k in 1..6 with s + k <= n², let t = jump[s + k] if it is not -1, else s + k.
- If t == n² return rolls + 1; otherwise push t if unseen.
- If the queue empties, return -1.
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length, total = n * n;
int[] jump = new int[total + 1];
for (int s = 1; s <= total; s++) {
int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
if (q % 2 == 1) c = n - 1 - c;
jump[s] = board[r][c];
}
if (total == 1) return 0;
boolean[] seen = new boolean[total + 1];
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
seen[1] = true;
int rolls = 0;
while (!queue.isEmpty()) {
rolls++;
for (int size = queue.size(); size > 0; size--) {
int s = queue.poll();
for (int k = 1; k <= 6 && s + k <= total; k++) {
int t = jump[s + k] != -1 ? jump[s + k] : s + k;
if (t == total) return rolls;
if (!seen[t]) {
seen[t] = true;
queue.offer(t);
}
}
}
}
return -1;
}
}class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
total = n * n
jump = [-1] * (total + 1)
for s in range(1, total + 1):
q = (s - 1) // n
r = n - 1 - q
c = (s - 1) % n
if q % 2 == 1:
c = n - 1 - c
jump[s] = board[r][c]
if total == 1:
return 0
seen = [False] * (total + 1)
seen[1] = True
queue = deque([1])
rolls = 0
while queue:
rolls += 1
for _ in range(len(queue)):
s = queue.popleft()
for k in range(1, 7):
if s + k > total:
break
t = jump[s + k] if jump[s + k] != -1 else s + k
if t == total:
return rolls
if not seen[t]:
seen[t] = True
queue.append(t)
return -1class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size(), total = n * n;
vector<int> jump(total + 1, -1);
for (int s = 1; s <= total; s++) {
int q = (s - 1) / n, r = n - 1 - q, c = (s - 1) % n;
if (q % 2 == 1) c = n - 1 - c;
jump[s] = board[r][c];
}
if (total == 1) return 0;
vector<bool> seen(total + 1, false);
queue<int> q;
q.push(1);
seen[1] = true;
int rolls = 0;
while (!q.empty()) {
rolls++;
for (int size = q.size(); size > 0; size--) {
int s = q.front();
q.pop();
for (int k = 1; k <= 6 && s + k <= total; k++) {
int t = jump[s + k] != -1 ? jump[s + k] : s + k;
if (t == total) return rolls;
if (!seen[t]) {
seen[t] = true;
q.push(t);
}
}
}
}
return -1;
}
};function snakesAndLadders(board) {
const n = board.length, total = n * n;
const jump = new Array(total + 1).fill(-1);
for (let s = 1; s <= total; s++) {
const q = Math.floor((s - 1) / n), r = n - 1 - q;
let c = (s - 1) % n;
if (q % 2 === 1) c = n - 1 - c;
jump[s] = board[r][c];
}
if (total === 1) return 0;
const seen = new Array(total + 1).fill(false);
seen[1] = true;
let queue = [1];
let rolls = 0;
while (queue.length > 0) {
rolls++;
const next = [];
for (const s of queue) {
for (let k = 1; k <= 6 && s + k <= total; k++) {
const t = jump[s + k] !== -1 ? jump[s + k] : s + k;
if (t === total) return rolls;
if (!seen[t]) {
seen[t] = true;
next.push(t);
}
}
}
queue = next;
}
return -1;
}Edge cases to test
- A ladder whose top is the head of another snake or ladder: you only take the first one
- The goal cannot be reached because every square in reach sends you back
- A 2 × 2 board, where one roll of 3 already finishes
- Odd rows (counted from the bottom) are numbered right to left
Hints
Hint 1
Each square is a node; a roll is an edge to one of the next six squares, redirected if that square has a snake or ladder.
Hint 2
Every edge costs one roll, so the fewest rolls is a shortest path in an unweighted graph.
Hint 3
Write a helper that turns a square number into (row, column), remembering the zigzag numbering.
FAQ
What is the best time complexity for Snakes and Ladders?
Optimal (BFS over squares) runs in O(n²) time and O(n²) extra space. Each of the n² squares is dequeued once and tries 6 rolls.
Which pattern does Snakes and Ladders use?
It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.
Is there a brute force solution for Snakes and Ladders?
Yes. Brute force (repeated relaxation) takes O(n⁴) time and O(n²) space. Keep the best known roll count for every square.
Which edge cases should I test for Snakes and Ladders?
A ladder whose top is the head of another snake or ladder: you only take the first one; The goal cannot be reached because every square in reach sends you back; A 2 × 2 board, where one roll of 3 already finishes; Odd rows (counted from the bottom) are numbered right to left.