A crypt-arithmetic problem is defined by one (or several) equations, where the digits are represented by letters. One has to find the value associated with each letter so that the operation is true; different letters must have different values. Moreover, the first letter of each number must be different from zero. The crypt-additions, where the only operation is the addition, are a special case of these problems. One of the more popular crypt-addition is:
DONALD+GERALD=ROBERT
Frederic Bartlett was a pioneer of the study of human problem solving. In the 1950s, he asked his subjects to solve this problem; for facilitating their task, the value of letter ‘D’ was given. In spite of this, many of them failed. If the value of ‘D’ is not known, this problem is much more difficult. The unique solution is: 526485+197485=723970.
CAIA has received the description of a general crypt-addition. It is important to know what formulation has been chosen for describing a problem. In that situation, I have chosen to introduce the carries. One must find an injection between the letters and the numbers from 0 to 9 that satisfies the constraints given by each column. For DONALD, that generates the following six main constraints; C0 to C6 are the carries, which can only take the values 0 and 1 for this addition:
C1+D+G=R+10*C0
C2+O+E=O+10*C1
C3+N+R=B+10*C2
C4+2*A=E+10*C3
C5+2*L=R+10*C4
C6+2*D=T+10*C5
and also: C6=C0=0, and D#0, G#0, R#0 (first letters of each line).
As computers are very fast, I can ask CAIA to write a combinatorial program. In one second, it writes this program, compiles and executes it: it contains 111 C instructions, but it can only solve the DONALD problem. It develops a tree with 262 leaves, and finds the unique solution. This is very satisfactory: the size of the search space is roughly 10 billions. When CAIA writes a combinatorial program, it does it cleverly. It is easy to check this solution, but it is more difficult to be sure that no solution is missing. We have seen that a meta-bug may create bugs in the generated program.
CAIA can also begin with a meta-combinatorial search, executing rules that modify the formulation of the problem. I call this approach ‘intelligent’ because its results look like those found by an intelligent human. In the present case, CAIA discovers that it has to find a bijection rather than an injection: there are 10 letters for 10 digits. This is very useful: for instance, if a digit D can be the value of only one letter L, then one is certain that the value of L is D. CAIA generates also new constraints, such as T is even, but the most useful is to state that E has only two possible values instead of 10: 0 and 9. Unfortunately, this meta-combinatorial search stops because all the rules have been applied.
In that situation, CAIA may decide to write a combinatorial program, leaving for good the meta-combinatorial search. It writes this program, including all the constraints that it has found, with particular attention to including the fact that it has now to find a bijection. It executes it, and it finds that there is only one solution after generating a tree, now with 192 leaves. The new program has almost the same size as the preceding one (118 C instructions), but both programs are completely different.
Another possibility for CAIA is to resume the combinatorial search after instantiating E with each of its two possible values. Then, it shows that E=0 leads to a contradiction, while E=9 leads to the solution. In both cases, it directly finds the result: now, the tree has only two leaves.
One may wonder whether it is worth using the intelligent approach: the computer times are almost the same, the time necessary to generate and execute the combinatorial program is approximately the same as the time for enriching the formulation of the problem. However, the results of the meta-combinatorial search may be checked and explained. Moreover, for other problems, the time required for the combinatorial approach is unacceptable.
The solution found by CAIA was a pleasant surprise. ALICE, probably the first AI system using a meta-combinatorial search, found a solution with 6 leaves. Jean-Louis Laurière improved it to only 4 leaves. He subsequently asked hundreds of students to study this solution, and no one ever suggested that it was possible to generate a smaller tree. For its part, CAIA made unexpected decisions: a crucial step in the solution was the use by CAIA of the new constraint:
10*E+C3+N+D+G=99*C1+B
which was essential for the discovery of the contradiction in the case E=0.
It is often useful to mix both approaches: one begins with the meta-combinatorial search, and one finishes with the combinatorial search. In some situations, the best way is to examine many situations as fast as possible. Therefore, CAIA must become meta-intelligent: It will acknowledge that, sometimes, it is better not to be too intelligent, but rather to stop the meta-combinatorial search. This happens when one can foresee that the time spent in a meta-combinatorial search will not lead to a significant improvement of the formulation. Then, the best move is to write a combinatorial program, but one must generate this program in a very intelligent way.