% Solving a cryptoarithmetic puzzle, using CLP(FD) of SICStus % W. Drabent :- use_module(library(clpfd)). /* The puzzle _ _ _ _ * _ _ _ ---------- 2 _ _ _ _ - 2 0 _ _ 3 _ _ _ 0 -------------- _ 0 _ _ 0 3 _ Each 0, 2, 3 already marked. */ puzzle2( Solution ) :- Solution = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,P,Q,R,S,T,U,V], allowed_digits2( Solution ), % SWI: Solution ins 1 \/ 4..9 digits_number( [A,B,C,D], Line1 ), % E F G digits_number( [2,H,I,J,K], Line3 ), digits_number( [L,2,0,M,N], Line4 ), digits_number([3,P,Q,R,0], Line5 ), digits_number([S,0,T,U,0,3,V], Line6 ), Line3 #= G*Line1, Line4 #= F*Line1, Line5 #= E*Line1, Line6 #= Line3 + 10*Line4 + 100*Line5, % To show the variable bindings before labeling: write( Solution ), nl, nl, labeling( [], Solution ), write( [' ',' ',' ',A,B,C,D] ),nl, write([' ',' ',' ',' ',E,F,G] ),nl, write( [' ',' ',2,H,I,J,K] ),nl, write( [' ',L,2,0,M,N] ),nl, write( [3,P,Q,R,0] ),nl, write( [S,0,T,U,0,3,V] ),nl, true. allowed_digits2( [] ). allowed_digits2( [X|L] ) :- X in {1} \/ (4..9), % SWI: X in 1 \/ 4..9. allowed_digits2( L ). % SICStus: X in {1} \/ (4..9). % digits_number( Digit_list, Numerical_value ). % The first element of the list may be a number >9 % Eg. [1,2,3,4,5], [123,4,5], [12345] have the same Numerical_value digits_number( [D], D ). digits_number( [D1,D2|Lc], NR ) :- NR1 #= 10*D1 + D2, digits_number( [NR1|Lc], NR ). /* A test run produces the single answer ?- puzzle2( Solution ). [_G8,_G11,_G14,_G17,_G20,_G23,_G26,_G29,_G32,_G35,_G38,_G41,_G44,_G47,_G50,_G53,_G56,4,_G62,_G65,_G68] [ , , ,6,8,9,4] [ , , , ,5,9,4] [ , ,2,7,5,7,6] [ ,6,2,0,4,6] [3,4,4,7,0] [4,0,9,5,0,3,6] Solution = [6, 8, 9, 4, 5, 9, 4, 7, 5|...] ; false. */ % To run it without labeling, use clause body below as a query. a_query_to_be_asked :- Solution = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,P,Q,R,S,T,U,V], allowed_digits2( Solution ), digits_number( [A,B,C,D], Line1 ), digits_number( [2,H,I,J,K], Line3 ), digits_number( [L,2,0,M,N], Line4 ), digits_number([3,P,Q,R,0], Line5 ), digits_number([S,0,T,U,0,3,V], Line6 ), Line3 #= G*Line1, Line4 #= F*Line1, Line5 #= E*Line1, Line6 #= Line3 + 10*Line4 + 100*Line5. /* Full answer below; shows the variable domains and the constraints. The "most constrained" variables are S = 4, L in 4..6, E in 5..7, F in 6..9, G in 4..6, P in 4..6 */ /* SWI: | | | | | | | | | | Solution = [A, B, C, D, E, F, G, H, I|...], S = 4, A in 4..7, -10*A+ -1*B+_G7208#=0, B in 1\/4..9, _G7208 in 48..73, -1*C+ -10*_G7208+_G7256#=0, C in 1\/4..9, _G7256 in 487..731, -1*D+ -10*_G7256+Line1#=0, D in 1\/4..9, Line1 in 4873..7314, E*Line1#=Line5, F*Line1#=Line4, G*Line1#=Line3, E in 5..7, Line5 in 34110..36570, -1*Line3+ -10*Line4+ -100*Line5+Line6#=0, -10*_G7442+Line5#=0, Line3 in 21111..29999, -1*K+ -10*_G7475+Line3#=0, K in 1\/4..9, _G7475 in 2111..2999, -1*J+ -10*_G7523+_G7475#=0, J in 1\/4..9, _G7523 in 211..299, -1*I+ -10*_G7571+_G7523#=0, I in 1\/4..9, _G7571 in 21\/24..29, 20+H#=_G7571, H in 1\/4..9, G in 4..6, Line4 in 42011..62099, -1*N+ -10*_G7673+Line4#=0, N in 1\/4..9, _G7673 in 4201..6209, -1*M+ -10*_G7721+_G7673#=0, M in 1\/4..9, _G7721 in 420..620, -10*_G7763+_G7721#=0, _G7763 in 42..62, -10*L+_G7763#=2, L in 4..6, F in 6..9, Line6 in 4011031..4099039, -1*V+ -10*_G7847+Line6#=0, V in 1\/4..9, _G7847 in 401103..409903, -10*_G7889+_G7847#=3, _G7889 in 40110..40990, -10*_G7916+_G7889#=0, _G7916 in 4011..4099, -1*U+ -10*_G7949+_G7916#=0, U in 1\/4..9, _G7949 in 401\/404..409, 400+T#=_G7949, T in 1\/4..9, _G7442 in 3411..3657, -1*R+ -10*_G8039+_G7442#=0, R in 1\/4..9, _G8039 in 341..365, -1*Q+ -10*_G8087+_G8039#=0, Q in 1\/4..9, _G8087 in 34..36, 30+P#=_G8087, P in 4..6 ; false. ?- */ /* Answer in SICStus: S = 4, Solution = [A,B,C,D,E,F,G,H,I,J|...], Line6 in 4011031..4099039, Line5 in 34110..36570, Line4 in 42011..62099, Line3 in 21111..29999, A in 4..7, B in{1}\/(4..9), C in{1}\/(4..9), D in{1}\/(4..9), E in 5..7, F in 6..9, G in 4..6, H in{1}\/(4..9), I in{1}\/(4..9), J in{1}\/(4..9), K in{1}\/(4..9), L in 4..6, M in{1}\/(4..9), N in{1}\/(4..9), P in 4..6, Q in{1}\/(4..9), R in{1}\/(4..9), T in{1}\/(4..9), U in{1}\/(4..9), V in{1}\/(4..9), Line1 in 4873..7314 ? ; no */