Seventh time lucky: solved

A recent New Scientist issue had this puzzle in it:

Septa wants to use a cash machine, but she has forgotten the PIN for her bank card. She has made six guesses so far, with no success:
5 7 2 6
7 3 5 8
1 1 9 1
7 6 2 8
4 8 8 2
9 3 0 7
Suddenly, she remembers that her PIN’s four digits are different. Her bank has a rule of “seven strikes and you’re out”, so she has just one more attempt before the machine swallows her card. As it happens, she had one correct digit in the right position in each of her guesses. What is her PIN?

I'm sure there's a clever solution to the puzzle, but I'm a computer scientist so I reached for a computational solution to the problem. And once I solved it, I thought I'd investigate alternative sets of attempts, to see what the space of problems and solutions looked like.

Solving the given puzzle

The first thing is to represent the attempts that Septa makes. I'll represent them as tuples of digits, but enter them as strings.

attempts_string = [
      '5726'
    , '7358'
    , '1191'
    , '7628'
    , '4882'
    , '9307'
    ]

attempts = [tuple(int(d) for d in t) for t in attempts_string] 

As there are only 10⁴ candidates, I can test them all in a reasonable time and hopefully there will be only one that fits the bill. This generate-and-test approach for solving this type of puzzle is one I first saw in The Art of Prolog, solving the game Mastermind.

The idea is to generate all the possible PINs and, for each one, test if it is a solution to the puzzle. Those that pass the test are the solutions. It's essentially a filter over the set of all PINs.

The itertools library makes generating all the possible PINs easy:

def candidates():
    return itertools.product(range(10), repeat=4)

I call a candidate valid if it meets the two tests given in the puzzle:

1. All the digits in the candidate are different
2. It matches exactly one digit (value and position) in each of the attempts.

def valid(candidate, attempts):
    return all_different(candidate) and \
           one_correct_in_all_attempts(candidate, attempts)

To check all the digits are different, convert the candidate to a set and check it's the same length as the original:

def all_different(candidate):
    return len(set(candidate)) == len(candidate)

To check there's one correct digit in all attempts, I specify how to count how many correct digits there are in one attempt:

def count_correct(candidate, attempt):
    return sum(1 for c, t in zip(candidate, attempt) if c == t)

This joins up pairs of digits from the candidate and attempt, filters to preserve only the same, and counts how many matches there were.

I can use that to check that a candidate has one correct digit in all attempts:

def one_correct_in_all_attempts(candidate, attempts):
    return all(count_correct(candidate, attempt) == 1 for attempt in attempts)

All that's left is to combine the generate and test parts:

def valids(attempts):
    return [c for c in candidates() if valid(c, attempts)]

>>> valids(attempts)
[(4, 3, 2, 1)]

There's one solution, 4321.

Which is the most discriminating attempt?

Each attempt eliminates some candidates, with the combination of attempts meaning there's only one solution. But if I drop one of the attempts, how many solutions would the puzzle have?

To find the set of "all but one" attempt sets, I need to split the attempts into a prefix and a suffix, drop the first element of the suffix, and combine what's left. For example, I could split the attempts into
5726 7358 | 1191 7628 4882 9307

drop the head of the suffix (1191) and combine the rest back into
5726 7358 | 7628 4882 9307

This, of course, only works if the suffix is non-empty.

That means the sub_attempts are [a + b[1:] for a, b in splits(attempts) if b]. All that's left is to write splits:

def split_at(xs, i):
    return xs[:i], xs[i:]

def splits(xs):
    return [split_at(xs, i) for i in range(len(xs) + 1)]  

And finally, I can count the number of solutions if I miss out one of the listed attempts.

>>> [(i, sum(1 for c in candidates() if valid(c, sa))) for i, sa in enumerate(sub_attempts)]
[(0, 4), (1, 4), (2, 6), (3, 5), (4, 11), (5, 4)]

Or, more prettily in a table:

which shows that the '4882' clue is the most important single attempt in the puzzle.

Generating random puzzles

The puzzle above was carefully constructed to reveal an answer. But if I randomly generated six failed attempts (following the rules above), what are the chances the puzzle would have only one solution?

To create random puzzles, I have to create random attempts. Each attempt must have one, and just one, correct digit. A straightforward way to create an attempt is to pick which digit must be correct, then build the attempt digit-by-digit. If it's the correct digit, use that; if not, pick a random digit instead, retrying if it happens to be the correct one.

def create_miss(target):
    pos_correct = random.randrange(len(target))
    miss = []
    for i in range(len(target)):
        if i == pos_correct:
            miss.append(target[i])
        else:
            d = random.randrange(10)
            while d == target[i]:
                d = random.randrange(10)
            miss.append(d)
    return tuple(miss)

Note that I build the miss as a list, because Python allows me to append to a list but not a tuple.

I can then create a new puzzle and see how many solutions it has.

>>> new_target = (1,2,3,4)
>>> new_attempts = [create_miss(new_target) for _ in range(6)]
>>> [merge_digits(a) for a in new_attempts], len(valids(new_attempts))
(['4250', '1921', '3200', '4032', '7201', '1561'], 7)

That's just one random puzzle instance. To generate more, write a function to do it. This will create repeats random puzzle instances, each using a given number of attempts, and count how many solutions each puzzle has. The results are counted and returned.

def random_valid_counts(target, number_of_attempts, repeats=10000):
    return collections.Counter(
        len(valids([create_miss(target) for _ in range(number_of_attempts)]))
        for _ in range(repeats)
    )

A call of random_valid_counts(new_target, 6) generates a broad distribution of results. About 7% of random puzzles have a unique solution; about 11% of puzzles have two valid PINs. The chart below shows a wide range of number of solutions.

In other words, it was quite unusual for Septa's failed attempts to describe exactly her PIN.

Now I can generate random puzzle instances, I'm not limited to only six attempts in the puzzle.

How many clues are needed to generate a puzzle with a unique solution? The chart below shows the puzzles typically need more than five clues to have a unique solution. With 8 clues, a random puzzle has a roughly 50% chance of a unique solution. 13 clues give a 90% chance of uniqueness, and 15 clues give a 95% chance.

Just looking a up to 10 clues, and just small numbers of solutions, we can see how the chance of different numbers of solutions shifts as the number of clues changes. (The missing part of each bar is the "more than five solutions" area.)

Credit

Photo by Eduardo Soares on Unsplash.