<div class="notebook"> <div class="nb-cell markdown" name="md1"> # SEND+MORE=MONEY This example solves the famous puzzle below. Each letter mustb be replaced by a unique digit and the addition must be satisfied. ``` S E N D + M O R E = M O N E Y ``` The first solution was provided by an anonymous on SWISH. It has been made a little more readable by adding empty lines and simplifying the final equality check. I didn't run it to the end, but it looks correct. Why is it so slow? It is a generate-and-test solution that first does all the generation, 10^8 (or 100 million) possibilities. </div> <div class="nb-cell program" name="p1"> main(S,E,N,D,M,O,R,Y) :- di(S), di(E), di(N), di(D), di(M), di(O), di(R), di(Y), notNull(S), notNull(M), isSet([S,E,N,D,M,O,R,Y]), toInt([S,E,N,D], VL), toInt([M,O,R,E], VR), toInt([M,O,N,E,Y], VS), VS is VL+VR. toInt_([], 0). toInt_([H|T], R) :- toInt_(T, R1), R is H+R1 * 10. toInt(L,R) :- reverse(L,R1), toInt_(R1,R). reverse_([], A, A). reverse_([H|T], A, R) :- reverse_(T, [H|A], R). reverse(L,R) :- reverse_(L,[],R). notNull(0) :- !,false. notNull(_). di(0). di(1). di(2). di(3). di(4). di(5). di(6). di(7). di(8). di(9). isSet([]). isSet([H|T]) :- free(H,T), isSet(T). free(_,[]). free(V,[V|_]) :- !,false. free(V,[_|T]) :- free(V,T). </div> <div class="nb-cell query" data-tabled="true" name="q1"> main(S,E,N,D,M,O,R,Y). </div> <div class="nb-cell markdown" name="md2"> ## Merging the generate with the test An obvious way to improve is by performing the tests as early as possible, merging them with the generators and move the computation of S+E+N+D and M+O+R+E as far up as possible. This reduces the search space enough to make it bearable (3.8 sec). </div> <div class="nb-cell program" name="p3"> main(S,E,N,D,M,O,R,Y) :- di(S), S \== 0, di(E), S \== E, di(N), N \== S, N \== E, di(D), D \== N, D \== S, D \== E, to_int([S,E,N,D], VL), di(M), M \== 0, M \== D, M \== N, M \== E, M \== S, di(O), O \== M, O \== D, O \== N, O \== E, O \== S, di(R), R \== O, R \== M, R \== D, M \== N, M \== E, M \== S, to_int([M,O,R,E], VR), di(Y), Y \== R, Y \== O, Y \== M, Y \== D, Y \== N, Y \== E, Y \== S, to_int([M,O,N,E,Y], VS), VS is VL+VR. to_int([A,B,C,D], V) :- V is 1000*A+100*B+10*C+D. to_int([A,B,C,D,E], V) :- V is 10000*A+1000*B+100*C+D*10+E. di(0). di(1). di(2). di(3). di(4). di(5). di(6). di(7). di(8). di(9). </div> <div class="nb-cell query" data-tabled="true" name="q4"> main(S,E,N,D,M,O,R,Y). </div> <div class="nb-cell markdown" name="md3"> We could improve further on the above by _reordering_ the generators, putting those that have the fewest possible values first. In its extreme this means we solve the problem by hand! # Using constraints Where classical Prolog solves problems like this using generate-and-test, constraint programming posts the constraints and finally, optionally _labels_ them. The CLP(FD) library describes constraints over integers. It uses interval arithmetic and labeling variables in a strategic order to simplify this problem. </div> <div class="nb-cell program" name="p2"> :- use_module(library(clpfd)). puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :- Vars = [S,E,N,D,M,O,R,Y], Vars ins 0..9, all_different(Vars), S*1000 + E*100 + N*10 + D + M*1000 + O*100 + R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y, M #\= 0, S #\= 0. </div> <div class="nb-cell markdown" name="md4"> Although the problem has one single solution, clp(fd) cannot find that. It does find concrete values for some variables and reduced intervals for others. Other clp(fd) libraries may reduces the problem more or less, depending on how clever the implementation is. </div> <div class="nb-cell query" data-tabled="true" name="q2"> puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]). </div> <div class="nb-cell markdown" name="md5"> To find a (the) concrete solution we have to use label/1, for which the manual is below. It takes a list of variables to label. Depending on its stragegy it will take one of the variables, give it a concrete value from its domain and compute the consequences. If it finds a contradiction it retries with a different value from the domain. If the propagation binds all variables being labeled to a concrete value we are done. - [[label/1]] - [[labeling/2]] </div> <div class="nb-cell query" data-tabled="true" name="q3"> puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]), label([S,E,N,D,M,O,R,E,M,O,N,E,Y]). </div> <div class="nb-cell markdown" name="md6"> Note that we do not (always) need to label all variables. In this case `E` suffices, but some of the other variables will leave the puzzle in part unresolved. </div> <div class="nb-cell query" data-tabled="true" name="q5"> time((puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]), label([E]))). </div> </div>