Last time, I described a solution to the following “skeleton multiplication puzzle” from Don Knuth’s The Art of Computer Programming:

N N N (1)

x N N N N (2)

---------

N N N 7 (3)

N N N N (4)

N N N N (5)

N N N (6)

-----------

7 7 7 7 7 7 (N != 7)

The answer found by Knuth is the following:

5 3 9 (1) x 1 4 4 3 (2) --------- 1 6 1 7 (3) 2 1 5 6 (4) 2 1 5 6 (5) 5 3 9 (6) ----------- 7 7 7 7 7 7

I was able to find a second solution where there was a leading zero in row (4). To find it, I considered all the prime factors of 777777 and reasoned about which pairs could fit the pattern of the puzzle.

In this post I want to show you how I originally found this solution.

I wrote a bit of code in Python to express part of the problem as a constraint programming (CSP) model. Instead of trying to work out the solution myself, I write down the conditions that must be true, and let the constraint programming solver do the work.

The basic approach for solving a puzzle using a solver is:

- Write down the variables (unknowns) that I want the solver to find.
- Write down all of the constraints (logical conditions) that need to be true.
- Turn the above into the right API calls for the solver I am using.

Here’s how it works (and here’s a link to my code). I used the *python_constraint* package as my CSP solver. To specify the puzzle we need a *Problem*() object:

problem = Problem()

In a CSP I first define variables that I want the solver to find. The variables I care most about are *n_1* and *n_2*. I know that *n_1* < 1000 and *n_2* < 10000. *addVariable*‘s first argument is the name of the variable and the second is the domain.

problem.addVariable("n_1", list(range(100, 999+1))) problem.addVariable("n_2", list(range(1000, 9999+1)))

I also am interested in the digits of each number. I will call the digits for the first (*d_11*, *d_12*, *d_13*), and the second (*d_21*, *d_22*, *d_23*, *d_24*). Remember that none of these digits can be a seven.

not_seven = [0, 1, 2, 3, 4, 5, 6, 8, 9] # no sevens allowed! # n_1 = d_13 d_12 d_11 problem.addVariable("d_13", not_seven) problem.addVariable("d_12", not_seven) problem.addVariable("d_11", not_seven) # n_2 = d_24 d_23 d_22 d_21 problem.addVariable("d_24", not_seven) problem.addVariable("d_23", not_seven) problem.addVariable("d_22", not_seven) problem.addVariable("d_21", not_seven)

Now I start writing down conditions that I know to be true. The first is that the product is a bunch of sevens:

problem.addConstraint(lambda n_1, n_2: n_1 * n_2 == 777777, ['n_1', 'n_2'])

Even if you know Python this may be confusing because you may not be familiar with the* python_constraint *package. The point is that I am providing an anonymous (lambda) function that evaluates the product of *n_1* and *n_2* as the first argument, and the names of the variables I defined earlier as the second.

Next, if I put the digits d_1x together, I get n_1:

problem.addConstraint(lambda d_11, d_12, d_13, n_1: 100 * d_13 + 10 * d_12 + d_11 == n_0, ['d_11', 'd_12', 'd_13', 'n_1'])

Same for n_2:

problem.addConstraint(lambda d_21, d_22, d_23, d_24, n_2: 1000 * d_24 + 100 * d_23 + 10 * d_22 + d_21 == n_2, ['d_21', 'd_22', 'd_23', 'd_24', 'n_2'])

Also, as considered earlier, when I multiply the last two digits of n_1 and n_2, the result must end in 7:

problem.addConstraint(lambda d_11, d_21: (d_11 * d_21) % 10 == 7, ['d_11', 'd_21'])

Now, if I wanted to be complete, I would write down a bunch more conditions for all of the Xs that appear in rows 3-6, using the rules of long multiplication. But why would I want to do that? The point is to be lazy.

Let’s just solve the problem, ask for all the solutions, and print them out.

s = problem.getSolutions() # s is a list of solutions. Each solution is a dict of variable values. for t in s: print(f"{t['n_0']} x {t['n_1']} = {t['n_0'] * t['n_1']}")

Wow! The same four that I discovered above. This was “easier” for me in the sense that I already knew how to use the *python_constraint* package, so I could just do the coding above without having to “think”. Doing it “the old fashioned way” was in the end more fun, but requires more deliberation and focus for me.