Safecracking Puzzle

Question

There is a combination safe with four switches on the front, each with three positions (low, medium, and high). If the switches are set into an opening combination, then when you try to open the safe, it will open; otherwise, no dice. In general, there are 3^4 = 81 possible combinations. However, this is a cheap safe; and only two of the switches actually matter; if you set those two switches right, the safe will open. Unfortunately, you do not know which are the important switches or which positions work. What is the minimum number of combinations you must try that will guarantee to open the safe? What is your plan?

It's from here: http://intrologic.stanford.edu/puzzles/safecracking.html

How can I solve this?

Answer 1

There are many answers already, but here'a a fun way to find them: we can use the combined power of

hypercubes and sudoku.

Like so:

This grid represents the 4D hypercube formed by the possible options. Position of switch 1 corresponds to the column inside a 3x3 box, switch 2 is the row inside a box, switch 3 corresponds to the columns of boxes themselves (we might call them "hypercolumns"), and switch 4 selects among the (hyper-)rows of boxes.

To cover all the possible opening combinations, we must of course test every switch pair in all their combinations. To make our plan as efficient as possible, we'll want to never guess the same position combination for any pair of switches twice, if it can be avoided.

This means we'd like to place our guesses on the hypercube so that no two guesses are in the same orthogonal plane along the cardinal directions. There's no prior guarantee that this is possible, but if it turns out to be, it will certainly be optimal.

For clarity's sake, the four cardinal directions of our hypercube are

• vertically inside a box
• horizontally inside a box
• to the same position in another box in the same column, and
• to the same position in another box on the same row,

and the 6 orthogonal plane orientations are those where the coordinates in exactly two of those directions are held constant.

Here's what it looks like if we highlight all the orthogonal planes that go through "row 2, column 2", which is more properly called "row 2, column 2, hyper-row 1, hyper-column 1", or even more to the point, "switch combination Middle, Middle, High, High".

The shape in the middle is the combination of the six, and corresponds to the set of all four-switch guesses that would duplicate an already-guessed combination for some pair of switches, which is exactly what we want to avoid.

Armed with all this, then, we notice that optimally placing our guesses happens to correspond to placing occurrences of a digit on a sudoku grid under a slightly modified "disjoint groups" restriction. That is, the digit must occur exactly once in

• every row,
• every column,
• every 3x3 box, and
• in every possible position inside a 3x3 box,

and the necessary modifications to account for the two missing plane orientations in 4D are

• no boxes that share a column may have the digit on the same row inside them.
• no boxes that share a row may have the digit in the same column inside them.

Well, then, let's just solve it! Since we have no fixed digits in the grid, this has quite a few possible solutions. Let's just pick the first one we come across:

And now we can just read the coordinates of the selected boxes to get an answer. (Reading the coordinates in any order is fine, as long as it's the same order every time. I'll start at the top and go counterclockwise, which is the same order I chose at the beginning.)

HHHH
MMMH
LLLH
LMHM
HLMM
MHLM
MLHL
LHML
HMLL

And there we have it: a set of four-switch guesses that includes every position combination for all possible pairs of switches (so it's guaranteed to work) exactly once (so it's optimal).

Epilogue: Even though a set of guesses is an optimal solution to this puzzle if and only if it fulfils the criteria given above, I fully support OP's choice not to include the four-dimensional sudoku tags, surely those would have been a dead giveaway :-)

---

Editor's note: this still reads a bit messy, as I made everything up as I went along. I tried to polish the answer a bit after a night's sleep, but there's still quite a lot to improve in terms of making the narrative easier to follow. I'm afraid the next improvement would require dropping the hypercubes out of the argument entirely, the reasoning should work without them just fine, but since that was the route my brain decided to take to reach the sudoku idea, (and also because hypercubes are way too cool to be treated like that), I don't think I'll want to make that edit after all. Sorry about that :-)

Answer 2

Obviously, even if you knew the two relevant switches you'd have to try

all 9 combinations between them.

The task is to find as small as possible number of combinations of all four switches such when you ignore any two of them the remaining two

will cover all possible 9 combinations between them.

This can in fact be done using only

9 combinations alltogether.

A simple way of constructing an optimal solution is

let a,b,c,d the switches and 0,1,2 the states a switch can be in. Choose the full set of combinations for the first two switches a = 0,1,2 and b = 0,1,2 and then use modular arithmetic and choose c = a+b mod 3 and d = a-b mod 3.

Written out:

     a       b       c       d

   0 0 0   0 1 2   0 1 2   0 2 1
   1 1 1   0 1 2   1 2 0   1 0 2
   2 2 2   0 1 2   2 0 1   2 1 0
 

Answer 3

Test the following 9 combinations. It covers each possibility exactly once and can be described as a 2-(3, 4, 1) orthogonal array

0000
0112
0221
1011
1120
1202
2022
2101
2210

Answer 4

Using the answer set programming solver Clingo with Python 3 the following program computes the optimal solution.

% Switch, num from 1 to 4
switch(1..4).
% A switch's position (1-3)
position(1..3).

% Declare all combinations (~52)
% A and B are an ordered pair of switches (1-4)
% AP and BP are the positions for switches A and B respectively
combo(A, B, AP, BP) :-
    switch(A),
    switch(B),
    A < B,
    position(AP),
    position(BP).

% An answer set can contain any subset of valid guesses
% A guess is a sequence of 4 positions
% X, Y, Z, W correspond to switches 1 through 4 respectively
{ guess(X, Y, Z, W) } :-
    position(X), position(Y), position(Z), position(W).

% Match combinations to guesses using Python code below
combo_guessed(A, B, AP, BP) :-
    guess(X, Y, Z, W),
    (A, B, AP, BP) = @guessed_combos(X, Y, Z, W).

% An answer set must contain guesses such that there is no combination left unguessed
:- combo(A, B, AP, BP), not combo_guessed(A, B, AP, BP).

% Convert a guess to a unique number using Python code below
guess_num(N) :-
    guess(X, Y, Z, W),
    N = @guess_num(X, Y, Z, W).

#script (python)
from clyngor.upapi import converted_types
from itertools import combinations

# Convert all guesses into unique integers
@converted_types
def guess_num(X: int, Y: int, Z: int, W: int):
    return X + (10 * Y) + (100 * Z) + (1000 * W)

# Give the 6 combinations that a guess guesses
@converted_types
def guessed_combos(X: int, Y: int, Z: int, W: int):
    slots = (None, X, Y, Z, W)
    for a, b in combinations(range(1, 5), 2):
        (a, b) = (a, b) if a < b else (b, a)
        yield (a, b, slots[a], slots[b])
#end.

% Optimize the answer set to contain the fewest number of guesses
#minimize { N : guess_num(N) }.

% Only print out the guesses
#show guess/4.

The solver reports that the optimal number of guesses is 9 and gives the following sequence of guesses in no particular order:

guess(2,3,1,1) guess(1,1,2,1) guess(3,2,3,1) guess(1,2,1,2) guess(3,3,2,2) guess(2,1,3,2) guess(3,1,1,3) guess(2,2,2,3) guess(1,3,3,3)

The program can be run via the command clingo file.lp inside a docker container created using the image linked here. The solver reported an optimal solution after running for ~200 seconds.

Answer 5

If only two switches actually matter then you can array those four switches into groups of two, such as

A B C D

• AB / AC / AD
• BA / BC / BD
• CA / CB / CD
• DA / DB / DC

Each group of has in total 9 combinations, 3^2, as there are 12 groups now the total number of combinations is 12*3^2 = 108. A slighly bigger number than before. But the group AB and BA are in fact the same group, the same goes for BC and CB, AC and CA, AD and DA, BD and DB and finnaly for CD and DC. The order does not matter, in the safe it is only important the correct combination, those duplicates groups are now gone.

• AB / AC / AD
• ** / BC / BD
• ** / ** / CD
• ** / ** / **

Now, the groups are 6, each has 9 combinations as we know, and the minimum number in order to crack the safe it is just 9*6 = 54.