Skip to content
Tutorials Center
My learning

Topics

Lesson 125 of 225 ยท Graphs

BFS Puzzles: Water Jug, Snakes and Ladders, Combination Locks

Solve classic puzzles with breadth-first search in Python by turning each configuration into a graph state: water jugs, snakes and ladders and a combination lock.

Most graph lessons start with a graph drawn for you. Many of the best BFS problems give you no graph at all: just a puzzle with moves. The trick is to see that every situation of the puzzle is a vertex and every legal move is an edge. Because BFS explores in order of distance, it finds the minimum number of moves, as long as every move costs the same.

This lesson turns three puzzles into graphs: the water jug problem, snakes and ladders, and a four-digit combination lock with forbidden codes. You have already seen the same idea on grids in rotting oranges; here the states are less obvious. The graphs are never built in advance: neighbours are generated on demand, which is how you handle state spaces of millions of vertices.

A recipe for state-space BFS

  1. Define the state. Choose the smallest description of the puzzle that makes the future depend only on it (and nothing else). A state must be hashable, such as a tuple or integer.
  2. Define the moves. A function that, given a state, yields the states reachable in one move.
  3. Search. Run BFS from the start state with a dist dictionary (or a parent dictionary if you want the path). The first time you see the goal, its distance is the answer.
  4. Give up cleanly. If the queue empties, the goal is unreachable.

The cost is O(number of states x moves per state). Always estimate the number of states first: it is the one thing that decides whether the approach is feasible.

Water jug

You have two jugs with capacities a and b litres and an endless supply of water. Moves are: fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Can you end up with exactly target litres in either jug, and how many moves does it take?

The state is (x, y), the current water in each jug. There are at most (a + 1)(b + 1) states, and each has six moves.

Python Water jug with the sequence of moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With jugs of 3 and 5 litres, BFS finds a four-litre solution in six moves, and because it explores by distance, no shorter solution exists. For (6, 9) and a target of 4, the answer is impossible: every amount you can ever measure is a multiple of gcd(6, 9) = 3, so 4 is out of reach. The same number theory (a target is reachable iff it is at most max(a, b) and divisible by gcd(a, b)) lets you skip the search, but BFS also gives you the actual moves.

Snakes and ladders

A board has cells 1..n. From cell c you roll a die and move to c + 1 ... c + 6; if you land on the foot of a ladder or the mouth of a snake, you immediately jump to its other end. What is the fewest throws needed to reach the last cell, assuming you can pick any die value?

The state is the cell. The edges are the six die rolls after applying jumps. Every edge costs one throw, so BFS applies directly. One subtlety: a jump happens once per landing and does not chain; if a ladder's top is the foot of another ladder, the puzzle's rules decide, and here we do not chain.

Python Fewest dice throws

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without jumps a 30-cell board needs ceil(29 / 6) = 5 throws. Ladders cut that down, and the walled start prints -1: the first throw can only land on cells 2-7, each a snake back to 1, so the last cell is unreachable. That output shows the "give up cleanly" step of the recipe: an empty queue means no solution.

Combination lock with forbidden codes

A four-wheel lock starts at 0000. One move turns one wheel one step up or down (9 wraps to 0 and back). Some codes are dead ends: reaching one jams the lock, so you may not pass through them. What is the fewest moves to reach a target code?

The state is the 4-digit string. Each state has 8 neighbours, and there are only 10,000 states, so BFS finishes instantly.

Python Opening the lock around the dead ends

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second call takes 6 moves instead of 4 because the dead ends force a detour. 0009 takes one move because the wheel wraps from 0 down to 9. The dead ends around 8888 seal off every neighbour of the target, so it prints -1 even though nearly every other code is reachable. Always check that the start is not itself forbidden.

Making BFS faster

  • Bidirectional BFS. Search from the start and from the goal at once, always expanding the smaller frontier, and stop when they meet. With branching factor d and distance L, this visits about 2 d^(L/2) states instead of d^L. See bidirectional search.
  • Compact states. Encode a state as an integer or string so it hashes quickly; avoid storing big nested lists in dist.
  • Use the right search. If moves have different costs, switch to Dijkstra; with 0 or 1 costs, use 0-1 BFS.

Common mistakes

  • Marking visited too late. Add a state to dist when you enqueue it, not when you dequeue it, or the queue fills with duplicates.
  • Putting more than you need in the state. If two situations that differ only in the path taken are stored separately, the state count explodes. Keep only what affects the future.
  • Mutating a shared list in the state. Use tuples or strings so states are hashable and not changed by accident.
  • Forgetting the unreachable case. Return an explicit marker such as -1 or None after the queue empties.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does BFS give the minimum number of moves in these puzzles?

    BFS expands all states at distance k before any state at distance k+1, so the first time it reaches the goal is along a shortest path when moves have equal cost.
  2. 2. In the water jug puzzle with capacities 6 and 9, why can you never measure 4 litres?

    Filling, emptying and pouring only change amounts by combinations of 6 and 9, which are always multiples of 3.
  3. 3. When should a state be marked visited?

    Marking on enqueue prevents the same state from being added to the queue several times.
  4. 4. A lock puzzle's target is surrounded by dead ends. What does BFS return?

    The target is never reached, so the queue drains and the function reports that the goal is unreachable.

Summary

  • A puzzle becomes a graph when you pick a state and a move function; BFS then finds the minimum number of moves.
  • Neighbours are generated on demand, so the graph never has to be stored.
  • Water jug states are (x, y), snakes and ladders states are cells, lock states are codes.
  • Mark states visited on enqueue and return a marker when the queue empties.
  • Estimate the number of states first; use bidirectional search or Dijkstra when needed.

Next: Universal Sinks, Degree Sequences and Other Graph Oddities.