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.
