State-space BFS with keys and doors

Why this matters

The previous lesson on grids marked each cell as visited once. That rule is correct when the only thing that matters is where you are. Many puzzles also depend on what you carry. A maze may have a locked door that opens only with a matching key. A game may have a switch that opens a gate only after you pick up a tool. In such a maze, the same cell can be a good place to stand with one key and a dead end with no keys at all.

So a plain "visited per cell" rule gives wrong answers. A search that reaches a cell first with no keys marks it as visited. A later route that reaches the same cell with the key it needs is then skipped. The search reports that no route exists, even though one does.

This lesson fixes that by making the search state bigger. The state is the cell plus the set of keys held. The search then visits each cell once per key set, not once in total. The idea is called state-space search: the state is everything the search needs to know to decide what it can do next. In a plain grid, that is only the cell. Here it is the cell and the keys.

The puzzle

The maze is a list of strings. Each character is one cell.

The goal is the shortest walk that collects every key in the maze. The walk does not need to reach an exit. The answer is the number of steps. If no walk collects all the keys, the answer is -1.

Each step moves up, down, left or right by one cell. Walking onto a key cell picks the key up at once. A key stays in the bag for the rest of the walk. A door is passable only if the bag holds the key with the same letter in lowercase. Key a opens door A, key b opens door B, and so on.

First example: a key one step away

Start with the smallest maze that shows the idea.

@.a

The start is at column 0. The key a is at column 2. The walk takes two steps: one step onto the open cell, then one step onto the key. Once the key is picked up, the bag holds every key in the maze, so the walk stops. The answer is 2.

Each step can be described as a state. Here are the states along the walk, written as (cell, keys held, steps taken).

start:     (row 0, col 0), keys none, 0 steps
one step:  (row 0, col 1), keys none, 1 step
two steps: (row 0, col 2), keys a,   2 steps

The key set is written as a set of letters. "Keys none" means the bag is empty. The final state has key a in the bag, and that is every key in the maze, so the search reports 2.

Representing the key set as bits

A key set is a set of letters, and a set can be stored compactly in one integer. Each key gets one bit. Bit 0 stands for a, bit 1 for b, bit 2 for c, and so on up to bit 5 for f. A bit that is 1 means the key is held.

Three small operations do all the work. The bit for a key with letter ch is 1 << (ch - 'a'). The << operator shifts the number 1 to the left by the given amount. Subtracting 'a' from a lowercase letter gives 0 for a, 1 for b, and so on. A key is added with keys |= bit. A door is passable when keys & bit is not zero.

The bit for a door is different. A door letter is uppercase, so the code must subtract 'A', not 'a'. This is one of the most common mistakes, and the mistakes section shows what happens when it is wrong.

Because the bag is an integer, two bags are equal when their numbers are equal. The search can therefore compare key sets with a single ==.

The search state

The state for this search has four parts: the row, the column, the key set and the number of steps taken so far. The steps are part of the state only because the answer is a number of steps. They are not used to decide whether two states are the same.

struct State {
    int row;
    int col;
    int keys;   // bit i is 1 when the key 'a' + i is in the bag
    int steps;
};

Two states count as the same when they have the same row, column and key set. A state with more steps is never better than one with fewer steps for the same cell and keys, because breadth-first search reaches the states in order of steps. The first time a state is reached is the shortest time it can be reached.

The visited array with one slot per key set

The visited array is the record of which states have been reached. A plain grid search needs one slot per cell. This search needs one slot per combination of cell and key set.

With six key letters, there are 64 possible key sets. A maze with R rows and C columns has R times C cells. The number of possible states is then R times C times 64. For a 3 by 5 maze, that is 15 times 64, which is 960 states. The array has one slot for each.

The slot for a state is found with one arithmetic formula. Each cell gets a block of 64 slots, and the key set picks a slot inside that block.

constexpr int masks = 1 << 6;
std::vector<char> seen(static_cast<size_t>(R) * C * masks, 0);
auto index = [&](int r, int c, int keys) {
    return (static_cast<size_t>(r) * C + c) * masks + keys;
};

The variable masks is 64, the number of key sets. The lambda index turns a row, a column and a key set into one position in the array. The lambda captures C and seen by reference through [&], so it can read them without taking copies. masks is a constant, so it needs no capture.

The whole search

The search is a breadth-first search. It starts with one state, and each round it looks at the states one step further from the start. The first state popped that holds every key gives the answer, because breadth-first search pops states in order of steps.

using Maze = std::vector<std::string>;
 
constexpr int dr4[] = {-1, 1, 0, 0};
constexpr int dc4[] = {0, 0, -1, 1};
 
int shortestToAllKeys(const Maze& maze) {
    const int R = static_cast<int>(maze.size());
    const int C = static_cast<int>(maze[0].size());
    int allKeys = 0;
    int sr = 0, sc = 0;
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) {
            char ch = maze[r][c];
            if (ch >= 'a' && ch <= 'f') allKeys |= 1 << (ch - 'a');
            if (ch == '@') { sr = r; sc = c; }
        }
 
    constexpr int masks = 1 << 6;
    std::vector<char> seen(static_cast<size_t>(R) * C * masks, 0);
    auto index = [&](int r, int c, int keys) {
        return (static_cast<size_t>(r) * C + c) * masks + keys;
    };
 
    std::queue<State> q;
    q.push({sr, sc, 0, 0});
    seen[index(sr, sc, 0)] = 1;
    while (!q.empty()) {
        State s = q.front();
        q.pop();
        if (s.keys == allKeys) return s.steps;
        for (int k = 0; k < 4; ++k) {
            int nr = s.row + dr4[k], nc = s.col + dc4[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            char ch = maze[nr][nc];
            if (ch == '#') continue;
            int keys = s.keys;
            if (ch >= 'a' && ch <= 'f') keys |= 1 << (ch - 'a');
            if (ch >= 'A' && ch <= 'F' && !(s.keys & (1 << (ch - 'A')))) continue;
            if (seen[index(nr, nc, keys)]) continue;
            seen[index(nr, nc, keys)] = 1;
            q.push({nr, nc, keys, s.steps + 1});
        }
    }
    return -1;
}

The first loop reads the maze once. It finds the start cell and builds allKeys, the number that stands for "every key in the maze". The search does not hard-code which keys exist, so it works for any maze.

The main loop takes a state from the front of the queue. If the bag already holds allKeys, the walk is done, and the number of steps is the answer. Otherwise the loop tries the four neighbours.

For each neighbour, the code does five checks in order.

1. Stay inside the grid.
2. Skip walls.
3. If the neighbour is a key, add that key to a copy of the bag. The original bag is not changed, because the other neighbours still need the old bag.
4. If the neighbour is a door, check that the old bag holds the matching key. If not, skip it. The check uses s.keys, the bag before this step, which is correct because a door cannot open itself.
5. Look up the slot for the neighbour with the new bag. If it is already marked, skip. Otherwise mark it and add the state to the queue with one more step.

The return -1 at the end runs only when the queue empties without finding a state with every key. Every reachable state has then been visited, and none holds all the keys.

Worked example: the route through two doors

The next maze is longer and needs a choice. It has two keys and two doors.

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

The start is at row 0, column 0. The key a is at row 0, column 2. The key b is at row 2, column 0. The door A is at row 2, column 2. The door B is at row 2, column 4.

Here is one walk that collects both keys. The walk is written as the cell reached at each step, with the bag after the step.

step 0: (0,0)  bag none
step 1: (0,1)  bag none
step 2: (0,2)  bag a          key a picked up
step 3: (0,3)  bag a
step 4: (1,3)  bag a
step 5: (2,3)  bag a
step 6: (2,2)  bag a          door A opened with key a
step 7: (2,1)  bag a
step 8: (2,0)  bag a, b       key b picked up

The walk takes 8 steps. The first part of the walk is forced. The only way down is the column at position 3, which passes through the open cell at (1,3). The door A at (2,2) can be walked through only after step 2, when the bag holds a. The door B at (2,4) is never needed, because b is reached on the left side.

The program prints the same answer.

8

A reader who tries this by hand often stops at step 5 and thinks the path is blocked by A. Stepping onto A is allowed because the bag holds a at that moment. The state for (2,2) with bag a is different from the state for (2,2) with no bag, and the search keeps both.

Worked example: a route that needs a second visit

The third example is harder. Each cell is visited more than once in the best walk, because the route first goes one way to fetch a key and then returns through the same region.

@..aA
..B#.
....b

The keys are a at row 0, column 3, and b at row 2, column 4. The doors are A at row 0, column 4, and B at row 1, column 2.

The shortest walk is six steps.

step 0: (0,0)  bag none
step 1: (0,1)  bag none
step 2: (0,2)  bag none
step 3: (0,3)  bag a          key a picked up
step 4: (0,4)  bag a          door A opened with key a
step 5: (1,4)  bag a
step 6: (2,4)  bag a, b       key b picked up

The walk cannot go straight down from (0,2) into the door B, because B needs b, and b lies beyond it. The walk goes through the top row to fetch a, then through the door A on the right side, and down the right column to reach b.

The program prints the same answer.

6

Why the per-cell rule gives wrong answers

To see why the key set matters, change the search so that it marks cells only. The change is to ignore the key set in the index. The code below shows that change in the lambda.

auto index = [&](int r, int c, int keys) {
    return (static_cast<size_t>(r) * C + c) * masks;   // key set ignored
};

With this change, the route through two doors still gives 8, but the third example gives -1 instead of 6. The debug trace below comes from the version that ignores keys, run on the third maze. Each line is one state taken from the queue, with the number of steps.

pop 0,0 keys=0 steps=0
pop 1,0 keys=0 steps=1
pop 0,1 keys=0 steps=1
pop 2,0 keys=0 steps=2
pop 1,1 keys=0 steps=2
pop 0,2 keys=0 steps=2
pop 2,1 keys=0 steps=3
pop 0,3 keys=1 steps=3
pop 2,2 keys=0 steps=4
pop 0,4 keys=1 steps=4
pop 2,3 keys=0 steps=5
pop 1,4 keys=1 steps=5
pop 2,4 keys=2 steps=6
-1

The trace shows the problem. The cell at row 2, column 4 holds the key b. The search reaches it from the left, through the bottom row, with only key b in the bag. The walk from the top then reaches the same cell with both keys, but the cell is already marked, so that state is dropped. The walk that would have finished in 6 steps is thrown away.

The fix is the key set in the index. Each state keeps its own slot, so the walk with both keys is kept. The correct version prints 6 for this maze.

A maze with no answer

Some mazes cannot be solved. This one has a door before its only key.

@Aa

The door A sits between the start and the key a. The walk cannot step onto A because the bag is empty. Every other move is blocked by the edge of the maze, so the queue empties after the start state. The search returns -1.

A harder impossible maze shows the same rule with more cells.

@.b
#A#
..a

The key a is in the lower right, and the only way there from the start is through the door A at row 1, column 1. Reaching A needs a, and a needs A. The search finds no route and returns -1. The lesson to take away is that a door must be reachable with the keys you can already get.

Counting the work

The search does at most one queue push for each state, so the running time is proportional to the number of states times four neighbours. The number of states is the number of cells times the number of key sets. With six key letters the number of key sets is 64, so the work for a 100 by 100 maze is at most 10000 times 64 states, which is 640000 states.

The cost grows quickly with the number of keys. Each extra key doubles the number of key sets. With seven keys the number of key sets would be 128, and the code above would need a larger masks value and a larger array. The problem statement usually limits the number of keys, and the limit is the reason the bit-set approach works.

Common mistakes

The mistakes below use real output from g++ 15.2.0 on Ubuntu, compiled with -std=c++20 -Wall.

Using the wrong letter for the door bit

A door has an uppercase letter, so its bit must be computed from 'A'. Computing it from 'a' gives a negative shift. The program below shows the mistake, compiled with the undefined-behaviour checker turned on.

int keys = 0b101;
char door = 'A';
int bit = 1 << (door - 'a');

The checker reports the problem at run time.

shift.cpp:7:17: runtime error: shift exponent -32 is negative

The letter 'A' has the code 65 and 'a' has the code 97, so the difference is -32. A negative shift has no defined result. The fix is 1 << (door - 'A'). The same care is needed when a door is checked against the bag.

Marking cells without the key set

This is the wrong-answer mistake described above. The visited array must be indexed by the key set as well as the cell. A test that has a single route through a maze may pass with the wrong code, so test a maze where the first route to a cell has fewer keys than a later route.

Picking up a key without updating the bag

Some code adds the key to the bag only when it checks the next cell, and it forgets to store the new bag in the queued state. The result is a search that never gets the second key, and it returns -1 on mazes that have an answer. In the code above, the new bag keys is stored in the state pushed with q.push({nr, nc, keys, s.steps + 1}), which is the value that matters.

Marking states when they are popped

If a state is marked only when it is taken off the queue, the same state can be queued several times. The answer stays correct, because the first time a state is popped is the shortest. The queue simply holds extra copies. Mark a state when it is pushed, as the code above does.

Forgetting that the answer is about keys, not the exit

The goal is the walk that collects every key, not a walk that reaches a particular cell. A version that stops at a cell called the exit returns the wrong number. Check the problem statement before you pick the stopping rule.

Practice

Each exercise is followed by its answer. Work through each one before reading the answer.

Exercise 1

What is the shortest walk that collects every key in this maze? Count the steps, and say whether the door is used.

@a.
#A#
..b

Show the answer

The answer is 4. The walk is: step onto a at row 0, column 1 (1 step), step down onto the door A at row 1, column 1 (2 steps), step down to row 2, column 1 (3 steps), step right onto b at row 2, column 2 (4 steps). The door is used, and it is opened with the key picked up in the first step. The program in this lesson prints 4 for this maze.

Exercise 2

The maze below has two keys, and both are behind doors. Is the answer -1?

@.b
#A#
..a

Show the answer

Yes, the answer is -1. The key a sits behind the door A, and the door can be opened only with a. The key b is reachable from the start, but a is not, so the walk can never hold both keys. The program prints -1 for this maze.

Exercise 3

A maze has 3 rows, 5 columns and 2 key letters. How many states can the search store at most?

Show the answer

There are 15 cells and 4 key sets. The key sets are: no keys, a only, b only, and both. The most states are 15 times 4, which is 60. The search never stores more than 60 entries in the visited array for this maze, even though the array has room for 64 key sets per cell.

Exercise 4

Why is the door check done before the visited check, and why does it use the bag from before the step?

Show the answer

The door check decides whether the walk may step onto the cell at all. The visited check only avoids repeating a state that was already queued. A blocked door must not be marked as visited with a bag that could not have entered it. The door uses the old bag because the walk must hold the key before it steps onto the door. A cell holds one character, so a cell cannot be a key and a door at once.

Exercise 5

Change the search so that it returns the number of states popped before the answer, instead of the number of steps. Explain whether that number depends on the order in which the four moves are tried.

Show the answer

Add a counter that increases each time a state is popped from the queue, and return it at the point where the answer is found. The number depends on the order of the moves, because the moves decide which states are queued first. The number of steps does not depend on that order, because breadth-first search finds the shortest distance whatever order the moves are tried in.

Summary

• A door can be passed only with its key, so the search state must include the set of keys held, not just the cell.
• Store the key set as bits, with one bit for each letter, and compare key sets with ==.
• The visited array needs one slot for each cell and key set pair, and marking a cell only by its position gives wrong answers.
• Breadth-first search finds the shortest walk that collects every key, and it returns -1 when no walk collects them all.
• Compute the bit for a door from 'A', not 'a', to avoid a negative shift.