Money Revisited

We show how a letter puzzle can be solved with the bundled finite domain constraint solver. The letter puzzle is already found in the language reference of the Jekejeke Prolog runtime library. There the puzzle was solved via the method of generate and test. This method uses goals G1, .., Gn to enumerate exemplars of a collection and goals T1,..,Tm to verify a condition. The problem is then solved via backtracking over the following query:

    G1, .., Gn, T1, .., Tm

For constraint solving the problem is posed the same way. But the constraint solver will not perform any backtracking during the setup phase. Only in the solving phase the constraint solver will then intelligently pick and rearrange the goals. The heuristic search component is responsible for picking the first generator Gi. The forward checking component will then cross out relevant tests Tj, .., Tk:

    Gi, Tj, .., Tk

If a test fails backtracking is issued until the recent generator is exhausted. The process might then even backtrack to previous generators but later pick again totally different generators. If all tests succeed a further generator and tests are picked. The search succeeds when all generators and relevant tests have been processed.

Let’s turn to the letter puzzle. To be able to use the finite domain constraint solver parser in a Prolog text one has first to load the clpfd library. Loading the clpfd library will define the predicates and syntax operators of the finite domain constraint solver. Loading the clpfd library requires the Jekejeke Minlog capability and is done as follows:

:- use_module(library(finite/clpfd)).

Since our finite domain constraint solver allows the use native Prolog variables we can use these to represent individual letters. The part that generates the permutations will therefore read as follows. The predicate ins/2 states that the letters will have values in the range of 0..9. The next predicate all_different/1 then states that the letters should be distinct:

puzzle(X) :-
X = [S,E,N,D,M,O,R,Y],
X ins 0..9,
all_different(X),

The code then continues by phrasing the condition that needs to be verified. These conditions read as in the original example except that the Prolog relations (=:=)/2 and (=/=)/2 are replaced by the relations (#=)/2 and (#\=)/2 of the finite domain constraint solver.

   M #\= 0,
S #\= 0,
           1000*S + 100*E + 10*N + D +
           1000*M + 100*O + 10*R + E #=
10000*M + 1000*O + 100*N + 10*E + Y,

The predicate label/1 will then start the constraint solver. There is no need to retrieve the variable values via the predicate indomains/2 since labeling will only succeed with all the given variables instantiated to a constant.

   label(X).

The source code of the puzzle/1 predicate is found in the appendix. It can be ensure loaded from the top-level. To then call the puzzle/1 predicate from the top-level we do not need to load the clpfd library again, since querying the puzzle/1 doesn’t require any predicates or syntax operators from the finite domain constraint solver:

?- puzzle(Z).
Z = [9,5,6,7,1,0,8,2] ;
No

For certain problems the constraint solver can considerably reduce the search space and thus perform much quicker than the standard backtracking solution. For the letter puzzle the standard Jekejeke Prolog backtracking solution takes around 3000ms, whereas the Jekejeke Minlog constraint solving solution only needs around 30ms in the average.

Kommentare