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 15,292 leaves, and finds the unique solution. This is 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.

 The solution of a problem often depends upon a set of variables, whose all possible values are known; the combinatorial search considers which combinations of these values satisfy all the constraints of the problem. This can also be used when there is a finite number of legal actions, and one considers the situations after all the legal sequences of these actions. This search is widely used in AI, for instance for chess programs. It frequently gives useful results: with their speed, the computers can develop trees much larger than those that we could ever generate.

However, even when this method succeeds, we are not satisfied: the only way to understand a solution found in that way is to know that everything has been considered, and one has found nothing else. We cannot check such solutions. Moreover, it cannot be used when the search space is very large, and always when there is an infinite number of values; this often happens in solving arithmetic problems.

Instead of considering all the possible values for each variable, one can also consider a combination of the rules that can create new constraints, enriching the formulation of the problem. In many cases, the new problem may become very easy to solve.

In order to clarify this idea, let us consider how CAIA solves a particular arithmetic problem: to find all the integers m and n satisfying the equation 4m+3n²=34 .

One cannot use the combinatorial search, there are an infinity of possible values for m and n. Here is CAIA’s solution:

3n² is the difference of two even numbers, so it is even.

As 3n² is even, and 3 is odd, n² is even.

Therefore n est even.

Then n² is a multiple of 4,

and 3n² is a multiple of 4.

So, 4m+3n² is a multiple of 4.

As it must be equal to 34, which is not a multiple of 4, there is a contradiction: no solution.

Naturally, at each step, CAIA must find and apply an element of its set of rules, for instance: in an equation, if a member is a multiple of integer I, then the other member is also a multiple of I. Another useful rule is: the sum of two expressions that are multiple of integer I is also a multiple of I.

A huge advantage of the meta-combinatorial search over the combinatorial one is that one has not to consider all the possible applications of the rules: one has only to find a sequence that leads to the solution. Many other rules were perhaps considered; if they are not necessary for the proof, it is useless to indicate that one attempted to use them. For instance, it happened that CAIA found that, as the square n² is a positive or null integer, this is also true for 3n². Therefore, 4m=34-3n²<=34, and m<9. I do not included this result in the preceding proof, the contradiction has been proved without using it.

The combinatorial search could be used in a variant of this problem where the absolute values of both m and n are less than one billion. Then, one can consider all the possible values of n, and check that 34-3n² is a multiple of 4. A lot of time would be wasted to find that there is no solution. Proving first that n is even and m<9 would reduce the size of the search space. Indeed, it is often interesting to use both kinds of search: the meta-combinatorial search trims down the problem, then the combinatorial search solves when the size of the search space is reasonable. We will show in future posts how CAIA manages to use both methods.

The mathematician frequently uses a meta-combinatorial search. He may spend years finding the proof of a theorem, writing notebook after notebook, when the final solution takes only a few pages.

When our AI systems will have many methods for enriching the formulation of problems, they will efficiently use the meta-combinatorial search. Some day, the mathematicians will be as surprised as the chess players were some years ago: during many years, they were laughing at the poor performances of the programs, and at their ridiculous moves. For the present time, they are reduced to demand that their artificial opponent will be shackled by the interdiction to use all its capacities; this does not prevent them to lose.