State-space BFS with keys and doors in Python

Why this matters

Many games have locked doors and keys. You walk through a maze, pick up a key, and then a door that was blocked is open. A route planner can work the same way: a permit unlocks a road, and the route changes depending on which permits you hold. In each case the answer to "where can I go next?" depends on more than your position. It depends on what you carry.

The breadth-first search (BFS) in the earlier lesson on grids only looked at position. This lesson adds what you carry to the search, so that the search can see the same cell twice when you arrive with different keys. The lesson uses the grid flood fill from the previous lesson as a starting point, and it uses only the Python standard library.

The rules of the puzzle

The grid is a list of strings. Each string is one row, and each character is one cell. grid[r][c] is the character in row r, column c. The symbols mean the following:

• @ is the start. It is an empty cell.
• . is an empty cell you can walk on.
• # is a wall. You cannot enter it.
• a to f are keys. Stepping onto a key picks it up, and the cell is then empty.
• A to F are doors. A door can be entered only if you already hold the matching key. Door A needs key a, door B needs key b, and so on.

The goal is to pick up every key with the fewest steps. A step is a move up, down, left or right to a cell that is not a wall. Picking up a key takes no extra step, because it happens when you enter the cell.

This grid has one key and a path with no doors:

@..a

You walk right three times and pick up a on the third step. The answer is 3.

One cell is not enough

The first idea most people try is to treat this like the plain grid search. Keep a seen mark for each cell, and never enter a marked cell again. That works for a maze with no keys. It fails here, and the reason is worth understanding.

Look at this grid:

#a##
@.Ab

The start @ is at row 1, column 0. The key a is above the middle cell, and the door A is to the right of the middle cell. The key b is at the far right. The only way to reach b is through door A, and the only way to open A is to pick up a first. So the route must go:

1. From the start, one step right into the middle cell X, which is at row 1, column 1. You hold no keys.
2. One step up to a. You now hold key a.
3. Back down to X. You are on the same cell as before, but now you hold a.
4. Right into door A, which opens now.
5. Right again onto b. All keys are collected after 5 steps.

Step 3 is the problem for the plain search. The cell X was already marked as seen in step 1, when you held no keys. The plain search refuses to enter it again, so it never reaches the door. It reports -1, which means no route exists. The correct answer is 5.

The lesson is that "being at X" is not one situation. Being at X with no keys and being at X with key a are two different situations, because the second one can go through door A and the first one cannot. The search has to remember both.

The state is the cell and the keys

A state is a full description of where you are in the search. For this puzzle a state is three values: the row, the column, and the set of keys held. The search treats each distinct state as a separate node, and it visits each state at most once. Two states can share the same cell if their key sets differ.

The key set is stored as a bit mask. A bit mask is one integer where each binary digit (bit) stands for one yes-or-no fact. Here, bit 0 says whether you hold key a, bit 1 says whether you hold key b, bit 2 says whether you hold key c, and so on. The expression 1 << k makes a number with only bit k set, where << shifts bits to the left. Combining keys uses | (or), and testing for a key uses & (and).

Python integers have no fixed size, so a mask can hold as many bits as you need. You can check a mask in the Python shell:

print(1 << 2)
print(0b11)

4
3

The prefix 0b means the number after it is written in binary. 0b11 is 3.

With two keys there are four possible key sets, so each cell can appear in the search in four different states. In general, with k keys, each cell has 2 ** k possible key sets. The number of states is the number of cells times that value. A 5 by 5 grid with 6 keys has 25 times 64, which is 1600 states, which is small for a computer.

The search

The search keeps a queue of states. Each queue entry is a tuple of four values: the row, the column, the key mask and the number of steps taken so far. A tuple is a fixed group of values in order, written in round brackets. Unpacking a tuple gives each value its own name in one line, as the code below does with row, col, keys, dist = queue.popleft().

The queue is a collections.deque. Its append method adds to the back, and its popleft method removes from the front. A plain list also works if you use append and pop(0), but pop(0) moves every other item one place each time, so it gets slow on a long queue.

The seen structure is three levels of lists. The entry seen[r][c][keys] is True when the state with that cell and that key set has already been queued:

seen = [[[False] * (1 << key_count) for _ in range(cols)] for _ in range(rows)]

The inner [False] * n makes one list of n values. The two comprehensions make a separate list for each cell, so each state has its own entry. Common mistakes below shows what goes wrong without them.

The full program is below. It reads the grid, finds the start and counts the keys, then runs the search. The last five lines run it on five grids:

3
5
2
-1
8

DR and DC are the same four neighbour moves used in the grid lesson. The key_count is found by counting lowercase letters, and all_keys is a mask with one bit for each key. With two keys, all_keys is (1 << 2) - 1, which is 4 - 1, which is 3, binary 11.

The loop handles each move in a fixed order. A wall is skipped. A door is skipped unless its bit is set in the key set. A key adds its bit to a copy of the key set, new_keys. Only after that does the code check seen, and only then is the new state queued. The check happens with the updated key set, so the state stored in seen always matches the state added to the queue.

The copy matters. Each neighbour starts from the key set the current state had, so picking up a on the way up does not change the keys used for the move to the left. A Python variable does not have its own copy for each loop pass, so the code assigns new_keys = keys inside the loop.

The (new_keys & bit) == 0 check uses brackets. In Python, & binds tighter than ==, so new_keys & bit == 0 also works, but the brackets make the order clear to a reader from any language.

The search returns the distance as soon as it takes out a state that holds every key. Breadth-first search takes states in order of distance, so the first such state has the smallest distance.

Why breadth-first and not depth-first

A depth-first search follows one path until it reaches a dead end or a goal, then turns back. Suppose one route to the last key is 3 steps long, and another is 9 steps long. A depth-first search may follow the 9-step route first, reach the key, and report 9. Nothing in its order tells it that a shorter route exists.

A breadth-first search cannot do that. It finds every state that is 1 step from the start before it looks at any state that is 2 steps away, and so on. So when it takes out a state with every key, no route with fewer steps can still be waiting in the queue. The key-and-door rules do not change this. A state with more keys is still just one more state in the same queue, and it gets its distance from the number of steps, not from the number of keys.

Tracing the example

Here is the search on #a## and @.Ab. The notation (row, column, keys) gives the state, and dist is the step count:

1. Start (1, 0, 0), dist 0. The wall is above, so the only move is right to (1, 1, 0), dist 1.
2. Take (1, 1, 0). Up is key a, so (0, 1, 1) is queued at dist 2. Left is already seen with no keys. Right is door A, and no key is held, so it is skipped.
3. Take (0, 1, 1). Its left and right sides are walls. Down is (1, 1, 1), which is new, so it is queued at dist 3. Note that (1, 1, 0) was already seen, but (1, 1, 1) is a different state.
4. Take (1, 1, 1). Left is the start cell, now with key a, so (1, 0, 1) is queued at dist 4. Right is door A, and bit 0 is set, so (1, 2, 1) is queued at dist 4.
5. Take (1, 0, 1). Its only open neighbour is (1, 1, 1), which is already seen, so nothing is added.
6. Take (1, 2, 1). Right is key b, so (1, 3, 3) is queued at dist 5.
7. Take (1, 3, 3). Its key set equals all_keys, so the search returns 5.

More examples

A single key and a simple path

@.a..

The key is two steps to the right of the start. The search reaches it at distance 2, and since a is the only key, that is the answer. The program gives 2. The .. after the key are not visited, because the search stops as soon as it takes out a state with every key.

A door with the key behind it

@.A.a

Door A sits between the start and the key. No state can pass the door, because the key is needed to open it and the key is on the far side. The search runs out of states and returns -1. The naive version in the common mistakes section also returns -1, which is right, because both versions agree when no route exists.

A longer grid with two doors

@.a..
###.#
b.A.B

The key a is at row 0, column 2. The key b is at row 2, column 0, on the bottom-left. To reach b, a route must pass door A, which is at row 2, column 2. Door B is never needed. The shortest route is: right, right to pick up a, then right to column 3, down to row 1, down to row 2, left through door A to column 1, then left onto b. That is 8 steps. The program prints 8 for this grid.

Common mistakes

Marking each cell only once

If you use one value per cell, the search misses routes that come back to a cell with more keys. The naive version does exactly that. It differs from the method above in two places. It builds seen with one entry per cell, and it checks seen[r][c] before the key bit is added:

seen = [[False] * cols for _ in range(rows)]
...
if ch == "#" or seen[r][c]:
    continue

On the #a## and @.Ab grid, this version returns -1, which is the wrong answer. The fix is the three-level seen indexed by the key mask, with the check placed after the key bit is added.

Repeating a list with * shares the inner lists

[[False] * 2] * 2 looks like it makes a 2 by 2 grid. It makes a list that holds the same inner list twice. Changing one row changes the other:

seen = [[[False] * 2] * 2] * 2
seen[0][0][0] = True
print(seen)

[[[True, False], [True, False]], [[True, False], [True, False]]]

Only one cell was changed, but four entries show True. The fix is the comprehension used in the program: [[False] * 2 for _ in range(2)] creates a new inner list on each pass.

Checking doors without the bit

A door check must test the bit for its own letter. Door A uses ord(ch) - ord("A") to find bit 0, and door B uses ord(ch) - ord("A") to find bit 1. If you test the wrong bit, the search lets you through doors you cannot open, or blocks doors you can. A quick check is to print the bit for a letter before you use it.

Using the wrong base letter

Key letters are lowercase and door letters are uppercase, so their codes differ by 32. A common slip is subtracting ord("A") when you meant ord("a"). In Python this raises an error, which is easier to notice than a wrong answer:

print(1 << (ord("A") - ord("a")))

The last line of the error is:

ValueError: negative shift count

The value ord("A") - ord("a") is -32. Python does not allow a negative shift. If the subtraction goes the other way, the shift is 32, and Python returns the full number, not a wrapped one:

print(1 << (ord("a") - ord("A")))

4294967296

In a language with 32-bit integers this line would wrap around to a different value. Python integers are not limited to 32 bits, so the bit is set at position 32 and the result is much larger than the keys in any grid. Always subtract ord("a") for keys and ord("A") for doors.

Setting the key bit after the seen check

If the code checks seen before it adds the key bit to the key set, it looks up the wrong state. It may skip a valid state, or mark the cell with the old key set. Add the key first, then check seen, as the program above does.

Gaps in the key letters

The size of the seen list comes from the number of lowercase letters. If the keys are a and c with no b, that count is 2, so the list has room for only the bits a and b. The bit for c is 4, which does not fit. For the grid @a.c, the last lines of the error are:

  File "keys_and_doors.py", line 45, in shortest_path
    if seen[r][c][new_keys]:
IndexError: list index out of range

The file name and line number depend on your file. The fix is to give the puzzle contiguous key letters, or to map each key letter to its own bit index before the search starts.

Rows of different lengths

The code takes the width from row 0 with len(grid[0]). If a later row is shorter, reading past its end raises an error:

shortest_path(["@...", ".."])

The last line of the error is:

IndexError: string index out of range

This also needs care for negative indexes. Python does not raise an error for row[-1]. It returns the last character, so a move to column -1 would silently read the far end of the row. The bounds check that starts the loop prevents this. Keep it, and check that every row has the same length before the search starts.

Practice

Exercise 1. What is the answer for the one-row grid @..a?

Show the answer

The answer is 3. The start is at column 0, and the key is at column 3, so three steps right reach it. The key is the only key, so the search stops there.

Exercise 2. A grid has 4 rows, 6 columns and 3 keys. How many states can the search create at most?

Show the answer

There are 4 times 6, which is 24 cells. Three keys give 2 ** 3, which is 8 key sets. The maximum is 24 times 8, which is 192 states.

Exercise 3. For the grid #a## and @.Ab, how many states does the search take out of the queue before it returns?

Show the answer

It takes out 7 states. They are the start, then (1, 1, 0), (0, 1, 1), (1, 1, 1), (1, 0, 1), (1, 2, 1) and (1, 3, 3). The last one is the goal, and the search returns when it is taken out.

Exercise 4. In the naive version, change only the line that builds seen to the three-level list, and leave the check if ch == "#" or seen[r][c]: as it is. Does the program raise an error? What does it print for @.a.., and why?

Show the answer

It raises no error. It prints -1 for @.a.., although the answer is 2. The check seen[r][c] now returns a list of booleans, not one boolean. A non-empty list counts as true in an if, so every neighbour is skipped before the search can move. The fix is to test seen[r][c][new_keys] after the key bit is added, and to set seen[start_r][start_c][0] for the start. With those changes the naive version becomes the correct method above.

Exercise 5. What does this line print, and why?

print(1 << (ord("a") - ord("A")))

Show the answer

It prints 4294967296. The value ord("a") - ord("A") is 32, so the shift is 1 << 32, which is 2 to the power 32. Python integers have no fixed size, so the bit is kept. In a language with 32-bit integers the same expression can give a different result.

Summary

• The plain grid search fails when a route must return to a cell after picking up a key, because the same cell can be a different state.
• A search state is the row, the column and the set of keys held, and the set of keys is stored as a bit mask in an integer.
• Store seen as a three-level list indexed by row, column and key mask, so each cell is visited at most once per key set.
• Add the key bit before the seen check, and test door bits with the matching uppercase letter.
• Build the nested lists with comprehensions, not with *, and check that the rows have equal length before you rely on the mask size.