Puzzle 1

The Problem

Some time ago the following puzzle was posed in the newsgroup sci.math.symbolic.

Let E, F, H, N, O, R, T, U, and W be unique, positive, single-digit integers. They fulfill the following conditions:

ONE must be a square, and
TWO or THREE or FOUR must be a square, and
ONE+1 or TWO+1 or THREE+1 or FOUR+1 must be a square, and
ONE+2 or TWO+2 or THREE+2 or FOUR+2 must be a square.

In this puzzle the expression "THREE+1" is defined as the sum , the remaining constraints being defined in the same way.

Determine E, F, H, N, O, R, T, U, and W.

The Solution

A brute force solution would be to check for all possible values of  E, F, H, N, O, R, T, U, and W (each ranging independently from 0 to 9) to fulfill the conditions. This would mean to check nearly one billion cases. Although certainly doable on a 1999-vintage computer, it is not a solution that can be efficiently generalized to more variables. In the following, we will implement a solution that is not specifically tailored to this problem, but which can be used to solve any problem of this kind.

Let us first calculate all possible sets of conditions arising from the puzzle. Every row in the following table is one possibility for the four conditions to be fulfilled.

These are 48 possible combinations.

The function allSquares generates all square numbers between imin and imax.

Here is an example of all nonnegative integer square numbers between 0 and 1234.

squares[0,1234]

Given an expression of the form word + integer, the function allPossibleDigitRealizations generates all possible realizations for the digits, taking into account the condition that every letter represents a different digit. The result of allPossibleDigitRealizations is a list of possible realizations in the form of replacement rules.

Here is an example.

allPossibleDigitRealizations[OON + 4]

Both realizations for the letters give a square.

The function compatibleDigitRealizations calculates the compatible letter realization for the two letter realizations and .  Inside this routine, the "actual" work is done later. We use the HoldAll attribute here to keep the arguments from being evaluated in case one argument is empty, to avoid unnecessary computations.

Let us again look at an example. Here are the possible digit realizations for one+1 to be a square or two+3 to be a square.

The following 14-digit realizations are the compatible realizations.

Now we can take a set of conditions from allConditionCombinations and recursively determine the compatible digit realizations. Here, the 30th row of allConditionCombinations chooses

We get a nontrivial solution. Now let us check all other combinations of allConditionCombinations, too.

No other solutions have been found. (The last evaluation effectively searched the entire solution space of the puzzle in less than a second, on a 1999-vintage computer.)  Let us finish by substituting the calculated result into the original condition to check that the solution is OK.

ONE 28

TWO THREE 138 FOUR

61

13