A safe has three locks, each of which is unlocked by a card, like a hotel room door. Each lock (call them 1, 2 and 3) and can be opened using one of three key cards (A, B or C). To open the safe, each of the cards must be inserted into a lock slot and then someone must press a button labeled “Attempt To Open.”
The locks function independently. If the correct key card is inserted into a lock when the button is pressed, that lock will change state — going from locked to unlocked or unlocked to locked. If an incorrect key card is inserted in a lock when the attempt button is pressed, nothing happens — that lock will either remain locked or remain unlocked. The safe will open when all three locks are unlocked. Other than the safe opening, there is no way to know whether one, two or all three of the locks are locked.
Your job as master safecracker is to open the locked safe as efficiently as possible. What is the minimum number of button-press attempts that will guarantee that the safe opens, and what sequence of attempts should you use?
I don’t believe there is an efficient way to solve the problem (read: polynomial time), but there are efficient ways to search the space of solutions and techniques we can use to make an exhaustive search more tractable. This problem sits nicely at the boundary between what is solvable vs unsolvable via brute force. So without further ado…
Encoding the state of the safe
First, we have to specify what it is we’re searching over. There are six possible safes, which correspond to the six permutations of (A,B,C). They are: {ABC,ACB,BAC,BCA,CAB,CBA}. Each permutation indicates which key opens which lock. For example, “BAC” is a safe where lock 1 is opened by key B, lock 2 is opened by key A, and lock 3 is opened by key C. The safe can also be in one of 8 different states, which correspond to whether each lock is currently open or closed. We can write these as binary numbers: {000,001,010,011,100,101,110,111}. For example, “010” is a safe where lock 2 is unlocked and locks 1 and 3 are locked.
Every time we make a move, we choose some assignment of the keys (A,B,C) to the locks (1,2,3). There are six possible moves we can make, which correspond to permutations of (A,B,C) as before: {ABC,ACB,BAC,BCA,CAB,CBA}. Given a hypothetical sequence of moves, we can track what happens by computing the state of the safe for each of its possible starting configurations. A simple way to track is to make a table, which I will illustrate using an example. If our safe is the “ABC” safe, and we apply the sequence of moves: ABC,CBA,BCA. The table looks like:
ABC safe |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
ABC (111) |
111 |
110 |
101 |
100 |
011 |
010 |
001 |
000 |
CBA (010) |
101 |
100 |
111 |
110 |
001 |
000 |
011 |
010 |
BCA (000) |
101 |
100 |
111 |
110 |
001 |
000 |
011 |
010 |
First move (ABC): We start with a row that contains every possible state. Applying the move “ABC” will toggle all the locks, since we are working with the safe “ABC” (all keys are correct). This is equivalent to XORing the current state with the bitstring “111”. In effect, every 0 becomes 1 and vice versa, which leads us to the second row. Note that the “000” state became “111”, so the safe is opened! For the other seven initial states, the safe remains locked but is now in a different state.
Second move (CBA): this move corresponds to an XOR with “010” since only the B is in the correct position. So the third row is produced by only toggling the middle bit of the states in the second row. Here, we see that the initial state “010” leads to an open safe after the second move.
Third move (BCA): This move accomplishes nothing since none of the letters are in the correct position (XOR with “000”).
For each of the six possible safes, we can make such a table, track the evolution of each of the 8 states as the sequence of moves is applied, and keep track of which columns eventually achieve a “111” (opened safe). Each safe responds differently because the keys are matched differently to the locks. For example, if we apply the same sequence of moves to the “BAC” safe instead, we obtain:
BAC safe |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
ABC (001) |
001 |
000 |
011 |
010 |
101 |
100 |
111 |
110 |
CBA (000) |
001 |
000 |
011 |
010 |
101 |
100 |
111 |
110 |
BCA (100) |
101 |
100 |
111 |
110 |
001 |
000 |
011 |
010 |
So, given a sequence of moves, we can evaluate how it affects each of the 48 possible initial states (6 safes x 8 states per safe) by computing six tables like the ones above, and then counting which columns contain “111” (the safe was opened). We can exclude the safes that start in the “111” position (safe is already open), so we only need to check 42 possible states.
Brute-force search
The next step is to exhaustively check all possible sequences of moves, starting with shorter sequences and progressively making them longer until we find a way to make all 42 initial states eventually contain “111”. Such a search can be computationally difficult because of the “curse of dimensionality”. For example, there are $6^{12} \approx 2.18\times 10^9$ different sequences of length 12. There are several tricks we can use to reduce this burden and make the search more tractable. Here are the tricks I used:
- Symmetry: since all possible permutations of labels are present and all possible moves are permitted, we may assume without loss of generality that the first move is “ABC”.
- Repetition: there is never a reason for two consecutive moves to be the same, since this will simply undo what the previous move accomplished. So each time we add an extra move to the sequence, we only need to consider 5 of the 6 possible choices.
- Give up when there is no hope: we start with 42 possible states, and each time we make a move, some of those states get solved (the safe opens). But there are limits. Each safe starts in one of 7 different states. Each time we make a move, the states remain distinct. This means each move opens at most one state per safe. Moreover, no matter which move we make, two of the safes will be unchanged (e.g. the move “ABC” does not affect safes “BCA” and “CAB” because none of the keys match). Consequently, each move can crack at most 4 of the 42 states. This observation allows us to stop our search early if the first several moves aren’t good enough. For example, if we are testing sequences of length 12 and the first 8 moves crack 25 of the 42 states, then we must crack the remaining 17 states in the 4 moves we have left. This is impossible since we can crack at most 16 states in 4 moves. So these first 8 moves can’t be right and we can move on.
Using the strategies above, the 2 billion possible sequences reduces to a mere 1080, a very manageable quantity. After performing the search, I found a winning sequence of length 12:
{ABC,BCA,CAB,ABC,BCA,ABC,ACB,BAC,ACB,CBA,BAC,ACB}.
The search also reveals that it’s impossible to crack all 42 states in 11 moves, so 12 is the best we can do. Finding such a winning sequence is challenging to do without a computer. Two observations:
- It’s easy to shoot yourself in the foot by making a wrong move early. For example, if you start with {ABC,BAC,…} then it’s already impossible to solve the problem in 12 moves!
- Greedy strategies don’t work! Looking for maximal moves at every step (crack as many safes as possible all the time) turns out to be suboptimal. While such strategies lead to good initial progress, it is short lived and you end up needing far more than 12 moves to cover all cases.
- If we interpret the question to mean that the safe may be initially unlocked (starts in a “111” state) but we have no way of knowing so because we still need to open it somehow and we don’t know which keys to use, then there are now 48 possible safes and 12 moves is no longer sufficient. Using a similar approach again, we find that it can be solved with a sequence of length 13: {ABC,ABC,BCA,CAB,ABC,BCA,ABC,ACB,BAC,ACB,CBA,BAC,ACB}. This sequence is the official solution that was posted on the Riddler blog.