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.
Huh. You say “I don’t believe there is an efficient way to solve the problem” and “Finding such a winning sequence is challenging to do without a computer.”
But I think I have an elegant solution that avoids a brute force search, both for the way I interpreted the problem (we need to check the initial state) and the way you did.
As you point out, there are eight states of the locks, and six possible key patterns. The key patterns can be divided into two sets, each set containing the circular-shifted versions of its elements. In other words, Set 1 = {ABC, BCA, CAB} and Set 2 = {ACB, CBA, BAC}. Assume without loss of generality that ABC is the correct pattern of keys for the locks. That means that ABC will toggle all three locks. But the other two patterns in Set 1 (BCA and CAB) will not work in any lock, and so using these patterns — both of which are circular-shifted versions of ABC, the correct pattern — will not toggle ANY lock, thereby leaving the state unchanged. Meanwhile, each of the three patterns in Set 2 will toggle EXACTLY one lock: ACB will toggle lock 1, CBA lock 2, and BAC lock 3. (Again, this works w/o loss of generality.)
As for the states: instead of assigning 000 to be all three locks locked and 111 all three unlocked, we can arbitrarily assign 000 to be the initial state of the three locks (whatever it happens to be). Then our task is simply to step through all 8 of the states; we really don’t care which pattern happens to correspond to a fully unlocked state.
It should be obvious that Set 1 can reach ONLY states 000 (initial state) and 111 (all locks toggled). By contrast, each key pattern in Set 2 toggles EXACTLY one lock at a time. That’s useful, and the only way we can get to the other 6 states.
So let’s assume we correctly pick Set 2, i.e., the set of circular-shifted key patterns each of which toggles exactly one lock. A 3-bit Gray Code is the obvious way to traverse the states while toggling exactly one lock at a time. But we don’t actually need or want a true Gray Code, i.e., one in which the final state is also just one toggle away from the initial state. Rather, for reasons that will become clear later, we want to END our pattern on 111 and traverse only 7 states — i.e. we do NOT want to check the initial state, state 000, at this stage. So we modify the last three states of a traditional 3-bit Gray Code to get our traversal pattern: 000, 001, 011, 010, 110, 100, 101, 111.
So here are the steps:
1. BAC (takes us to 001)
2. CBA (takes us to 011)
3. BAC (takes us to 010)
4. ACB (takes us to 110)
5. CBA (takes us to 100)
6. BAC (takes us to 101)
7. CBA (takes us to 111)
Now we’ve gone through 7 states in 7 steps! The only state we have not checked is the initial state, 000. Also note that as long as we’ve picked Set 2 (i.e., the set containing the pattern of keys each of which toggles exactly one lock), this pattern can be generalized:
1. [pick any pattern] — it’ll toggle exactly one lock, call it lock alpha
2. RIGHT circular-shift — it’ll toggle a different one, call it lock beta
3. LEFT circular-shift — it’ll toggle alpha again
4. LEFT circular-shift — toggle lock gamma
5. LEFT circular-shift — toggle beta
6. LEFT circular-shift — toggle alpha
7. RIGHT circular-shift — toggle beta
As you can see, as long as we’ve picked Set 2, we can traverse all 7 states and end with each of the three locks toggled with respect to their initial states; i.e., we will end in state 111.
But what if we picked the “wrong” set, i.e., Set 1? Then instead of having traversed 7 states, we will have simply gone back and forth between 000 and 111, ending in state 111. (We know this because each pattern was used an odd number of times — either 3 times or once.) So then we need to grab the other set and go through the pattern again, although this time we need to check only 6 states, not 7 (because we know, by virtue of having picked the wrong Set the first time, that we’ve already checked 000 and 111). And as it turns out, we can use the same pattern because we’re just toggling (or, as you put it, XORing) the various locks, so the same pattern above that took us from 000 to 111 will take us from 111 to 000. This is one reason we want the pattern to end on 111. Another is that it means the last state to be checked (000) has already been checked by our first go-round using Set 1, so we can truncate this attempt at the 6th step. These 6 steps, plus the initial 7 steps, means 13 steps total.
There is a corner case: What if we picked the right set (Set 2) the first time, but the safe was actually unlocked to begin with (i.e., state 000 was the correct one)? This is another reason it’s important that we end our 7-step pattern on state 111. After we complete the 7 steps, and the safe doesn’t open, we would then pick the other set (Set 1) and repeat the pattern, as described above. But remember Set 1 simply toggles all three locks or none at all. So ending on 111 the first time around (with Set 2) guarantees that we will eventually hit 000 when going through the pattern above using Set 1 (by no later than the fourth step). So if we picked the right set, we will reach a solution in 11 steps.
To summarize, here is the algorithm to solve this in 13 steps, assuming we do need to check the initial state:
1. [pick any pattern]
2. RIGHT circular-shift
3. LEFT circular-shift
4. LEFT circular-shift
5. LEFT circular-shift
6. LEFT circular-shift
7. RIGHT circular-shift
8. [pattern in #1, but with the last two keys swapped. So if #1 was ABC, now use ACB]
9. RIGHT circular-shift
10. LEFT circular-shift
11. LEFT circular-shift
12. LEFT circular-shift
13. LEFT circular-shift
—
What if we don’t need to check the initial state? Can we modify the algorithm above to do it in 12 steps? Yes!
The key here is that if we know we never need to check 000, then we should exploit the quality of Set 1 — that it can toggle all 3 locks — to test states OTHER than 000 or 111. In other words, we should modify our state-traversal pattern so that it covers only 6 of the 7 states we need to cover and ends on a state that, when all three locks are toggled, results in a state we did NOT already traverse. This one will suffice: 000, 001, 011, 111, 110, 100, 101. The only state we don’t check is 010 — the inverse of the state we end on.
So our pattern for this is:
1. BAC [takes us to 001]
2. CBA [takes us to 011]
3. ACB [takes us to 111]
4. BAC [takes us to 110]
5. CBA [takes us to 100]
6. BAC [takes us to 101]
Then, when we use Set 1, as long as we try each key pattern, we will eventually hit 010, thus covering all the states.
But what if we accidentally picked Set 1 to start? Then we will toggle between states 000 and 111, ending in one of those two states. This time we don’t know which one because one of the key patterns is used an even number of times. (Is there a state-traversal pattern that could solve this? Maybe! But as we’ll see it won’t matter.)
Since we’re in either 000 or 111, and we need to cover the other 6 states, we can actually just reuse the state-traversal pattern we developed in the first version of the problem.
So the full pattern is:
1. [pick arbitrary pattern]
2. RIGHT circular-shift
3. RIGHT circular-shift
4. RIGHT circular-shift
5. RIGHT circular-shift
6. LEFT circular-shift
7. [pattern in #1, but with the last two keys swapped. So if #1 was ABC, now use ACB]
8. RIGHT circular-shift
9. LEFT circular-shift
10. LEFT circular-shift
11. LEFT circular-shift
12. LEFT circular-shift
And that’s how you can get the answer without brute force.
In fact it appears the solutions above will each generate 6 answers (one for each starting condition). If in the step where you switch Sets you swap the first and second keys or the first and third keys (instead of the second and third keys), you get 12 more solutions. And I believe that you can invert all the RIGHT and LEFT circular shifts to get a symmetric set of solutions, and that the RIGHT/LEFT inversion can be applied independently to each Set. So that means there should be a family of 72 solutions.
In fact to generate your solution, we should: start with pattern ABC, invert the RIGHT/LEFT for the first six steps, swap the second and third keys for the pattern in step 7, and maintain the RIGHT/LEFT as I have it for steps 8-12.
Beautiful solution, sopanj!
Fantastic analysis and very clear presentation! Thank you very much for this!! Regards, Jason