Brute-Forcing a Museum's Math Puzzle with Python

by Brenden Hyde

TL;DR: A seemingly simple math puzzle stumped me, so I brute-forced it with a Python program.

Background

During a visit to a museum called OMSI, I noticed a puzzle that had a 3x3 grid and some wooden blocks labeled 1 through 9.

The grid looked like this:

[A] - [B] = [C]
             x
[D] ÷ [E] = [F]
             =
[G] + [H] = [I]

The puzzle was called "Four Equations," and the goal of it was to arrange the blocks to meet these constraints:

All four equations had to be solved at the same time, and you could use each number only once.

Here's a picture of the puzzle with its blocks jumbled:

Motivation

As you might infer from the picture of the wooden blocks and simple, gigantic print on the sign, this was a puzzle for all ages including children, and yet I couldn't solve it in the 5-10 minutes I tried.

Slightly annoyed, I gave up, sanitized my hands, and vowed I'd solve it later with a computer.

Number of Possible Solutions

The way to calculate the total number of possible block arrangements in this puzzle is with factorials.

There are 9 starting blocks to choose from.

After you choose one, there are 8 remaining blocks.

After you choose another, there are 7 remaining, and so on until you run out.

That means that the number of possible arrangements is 9! or "nine factorial."

This can be written as: 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

The number 9! is equal to 362,880.

That's the number of naive guesses it would take to guarantee that you either get the answer or prove there isn't one.  I say "naive" because not every permutation in our huge list is a potential solution.

The possibilities shrink when you consider the mathematical relationships among the numbers.  For example, the second row is a division problem.

Because 2, 3, 5, and 7 are prime numbers, none of them can be the first number (dividend).

The ninth box is the product of two numbers, so none of the primes can go there either, as we don't have any duplicates, and a prime number only has two factors: one and the prime itself.

You could solve the Four Equations problem like a Sudoku, given that it has so many logical constraints to eliminate most solutions.

But, I have a computer, and I don't have the patience for that!

Solving It With Python

I chose the Python programming language to build my puzzle solver, since it's powerful and easy to use.  If you don't care about the code, you can safely skip to the section entitled "Solving the Puzzle."

There are two main pieces to my Python program:

  1. Get a list of all possible permutations of the numbers 1 through 9.
  2. See if any of them solves the puzzle, and print it if so.

Getting All Possible Permutations

I want to find every way that the numbers 1 through 9 can be scrambled.

Rather than reinvent the wheel, I used the permutations function from Python's itertools module.  This function returns all possible permutations of a list of numbers.

Here's some example code that achieves this:

from itertools import permutations

one_thru_nine = list(range(1, 10))
all_perms = list(permutations(one_thru_nine))

In the above code, I first generate a list of all numbers 1 through 9 with Python's range function.

range takes two arguments here: the lower bound (starting number) and upper bound (ending number).

Confusingly, range is inclusive on the lower bound and exclusive on the upper bound.  That means that if I run range(1, 5), it'll give me the numbers 1, 2, 3, and 4, but not 5.

Therefore, I use range(1, 10) in the example to get 1 through 9.

After I get the list of numbers, I use permutations plus a built-in function called list to create the possible solutions.

Constraint Checking

Equipped with a list of possible solutions (and many erroneous ones), it's time to solve the puzzle.

To check if a permutation solves the puzzle, the code uses Python assertions.  An assertion is just a statement that is either true or false.  If the statement's true, Python does nothing and moves on to the next line of code.  However, if the statement is false, Python raises an error to tell us this isn't a solution.  This error is called an AssertionError.

Here's a snippet that uses an assertion to check if the difference of the first two elements equals the third element:

def check_solution(p):
    try:
        assert p[0] - p[1] == p[2]
    except AssertionError:
        return False
    else:
        return True

In the above code, we make a function called check_solution that takes a list called p as an argument.

To grab an item out of a Python list, you refer to it by its index.  An index is the numerical label that represents the item's place in the list.  The first element has an index of 0, so if my list were [1,2,3], the number 1 would be at index 0, the number 2 would be at index 1, and 3 would be at index 2.

Our list is called p, so the first element in the list is called p[0], and the second one is p[1], etc.

In the code, we assert that p[0] - p[1] == p[2].

If this is true, as in the example case 6 - 4 == 2 then the function returns a value of True.

If that assertion is false, for example 4 - 2 == 7 then an AssertionError is raised by our function, and we handle it by returning False.

The above example only solves one of the four constraints, but we can test addition, division, and multiplication just like we did for subtraction.

Those assertions are included in the code, but I've omitted them here to stop the reader from falling asleep.

Solving the Puzzle

With all the math riff-raff out of the way, we can solve this puzzle.

Assuming you have Python 3.6 or greater installed, you can run my accompanying script from the CLI like so: python3 grid_puzzle.py

The answer will be rendered to the screen:

Solution found! ๐Ÿ”ฅ
---------
9 - 5 = 4
        x
6 ÷ 3 = 2
        =
1 + 7 = 8
---------
Solution found! ๐Ÿ”ฅ
---------
9 - 5 = 4
        x
6 ÷ 3 = 2
        =
7 + 1 = 8
---------
The total number of solutions is 2

Conclusion

To my surprise, there were two solutions to the problem.

My program started guessing with the number 1 in the first box, and the real solutions both started with a 9 in the first box, so it took a lot of attempts to get it right.

Specifically, it took 345,295 guesses to get the first solution and two more for the second!

It took about 45 minutes of coding and 50-70 lines of code to solve this problem.  The actual execution of the program takes less than a second!

While I could have made paper cutouts and solved this by hand, I enjoyed doing it more with code, as it let me be sure there were only two answers.

If this article makes it to publication in 2600, you can find the complete Python source code to solve the "Four Equations' puzzle at the following link: github.com/bxbrenden/four-equations-puzzle

I am now armed with the computational power to brute-force a children's puzzle.  The next time someone asks me if I'm smarter than a fifth grader, I can respond more confidently than ever with a resounding, "probably!"

from itertools import permutations


def render(l):
    """Render a 3x3 grid of a list `l`."""
    try:
        assert len(l) == 9
    except AssertionError:
        print(f"Expected list of length 9. Got length {len(l)}")

    first_row = f"{l[0]} - {l[1]} = {l[2]}"
    second_row = f"{l[3]} รท {l[4]} = {l[5]}"
    third_row = f"{l[6]} + {l[7]} = {l[8]}"
    leading_1 = " " * 8 + "x"
    leading_2 = " " * 8 + "="
    padding = '-' * len(first_row)

    rows = [padding, first_row, leading_1, second_row, leading_2, third_row, padding]
    for row in rows:
        print(row)


def generate_lists():
    """Generate all permutations of range(1, 10)."""
    all_perms = list(permutations(range(1, 10)))

    return all_perms


def check_solution(p):
    """Given a permutation of range(1, 10), return True if p solves the puzzle."""
    try:
        assert p[0] - p[1] == p[2]
    except AssertionError:
        return False

    try:
        assert p[3] / p[4] == p[5]
    except AssertionError:
        return False

    try:
        assert p[6] + p[7] == p[8]
    except AssertionError:
        return False

    try:
        assert p[2] * p[5] == p[8]
    except AssertionError:
        return False

    return True


def main():
    all_permutations = generate_lists()
    all_solutions = []
    for index, p in enumerate(all_permutations):
        solved = check_solution(p)
        # print(f'Trying permutation #{index + 1}...')
        if solved:
            print('Solution found! ๐Ÿ”ฅ')
            render(p)
            # print(f'Took {index + 1} guesses to solve.')
            all_solutions.append(p)

    print(f'The total number of solutions is {len(all_solutions)}')


if __name__ == '__main__':
    main()

Code: grid_puzzle.py
Return to $2600 Index