/* Kakuro in Picat. Port of SICStus Prolog model kakuro.pl """ A matrix element is one of: !\! - black square A\! - black square, sum of cells below is A !\B - black square, sum of cells to the right is B A\B - black square, sum of cells below\to the right is A\B """ Tiny: | ?- kakuro(tiny),fail. !\! !\! 11\! 4\! !\! !\! !\! 14\5 2 3 10\! !\! !\17 9 5 1 2 3\! !\6 5 1 3\4 3 1 !\! !\10 3 1 4 2 !\! !\! !\3 2 1 !\! This model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import v3_utils. % import util. import cp. main => go. go ?=> % kakuro(tiny), % kakuro(kakuro17), kakuro(hard), fail, nl. go => true. go2 ?=> matrix(Id,_), println(id=Id), kakuro(Id), fail, nl. go2 => true. % A matrix element is one of: % !\! - black square % A\! - black square, sum of cells below is A % !\B - black square, sum of cells to the right is B % A\B - black square, sum of cells below\to the right is A\B kakuro(ID) :- matrix(ID, Matrix), term_variables(Matrix, Vars), Vars :: 1..9, foreach(Row in Matrix) constrain(row, Row) end, transpose(Matrix, Transpose), foreach(Col in Transpose) constrain(col, Col) end, % hakank: Picat's (or rather bp's) fmt don't give a pretty result, % So I format this manually instead. % length(Transpose, N), % fmt(N, Fmt, []), solve($[], Vars), foreach(R in Matrix) foreach(T in R) (T = $(\((A,B))) -> printf("%2w\\%2w\t", A,B) ; printf("%5w\t", T) ) end, nl end, nl. constrain(_, []) :- !. constrain(row, [_\Sum|Row]) :- integer(Sum), !, stretch(Stretch, Row, Row1), all_diff_sum(global, Stretch, Sum), constrain(row, Row1). constrain(col, [Sum\_|Row]) :- integer(Sum), !, stretch(Stretch, Row, Row1), all_diff_sum(global, Stretch, Sum), constrain(col, Row1). constrain(Mode, [_|Row]) :- constrain(Mode, Row). % hakank simple(X) :- integer(X) ; var(X). stretch([X|Xs]) --> [X], {simple(X)}, !, stretch(Xs). stretch([]) --> []. % hakank: Not used fmt(0) --> !, "\n\n". fmt(I) --> "~t~w~6+", {J is I-1}, fmt(J). % hakank: Note the '!'. all_diff_sum(_, L, Sum) :- sum(L) #= Sum, % hakank length(L, N), Series is N*(N+1)//2, ( Sum == Series -> L :: 1..N ; (Sum == 10*N - Series -> Min is 10-N, L :: Min..9 ; true ) ), % !, all_different(L). % hakank: These predicates are not used because of the !/0. % all_diff_sum(global, L, Sum) :- % plusify(L, Expr), % sum(L) #= Sum, % all_different(L). % all_diff_sum(gcc, L, _Sum) :- % same_length(L, Matrix), % ? % Matrix = [[1,2,3,4,5,6,7,8,9] : _ in 1..L.len], % sum(L) #= Sum, % all_different(L), % [B1,B2,B3,B4,B5,B6,B7,B8,B9] :: 0..1, % global_cardinality(L, $[1-B1,2-B2,3-B3,4-B4,5-B5,6-B6,7-B7,8-B8,9-B9]). % all_diff_sum(table, L, Sum) :- % Ts = [T.to_array() : T in findall(T, all_diff_sum_tuple(L,Sum,T))], % table_in(L.to_array(), Ts). % all_diff_sum_tuple(L, Sum, T) :- % same_length(L, T), % T :: 1..9, % sum(T) #= Sum, % all_different(T), % solve([], T). % plusify([], 0). % plusify([P|Ps], Conj) :- % plusify(Ps, P, Conj). % plusify([], P, P). % plusify([P|Ps], Q, Conj) :- % plusify(Ps, $Q+P, Conj). % % Instances % /* Solution: !\ ! !\ ! 11\ ! 4\ ! !\ ! !\ ! !\ ! 14\ 5 2 3 10\ ! !\ ! !\17 9 5 1 2 3\ ! !\ 6 5 1 3\ 4 3 1 !\ ! !\10 3 1 4 2 !\ ! !\ ! !\ 3 2 1 !\ ! */ matrix(tiny, [[ !\! , !\! ,11\! , 4\! , !\! , !\! ], [ !\! ,14\5 , _ , _ ,10\! , !\! ], [ !\17, _ , _ , _ , _ , 3\!], [ !\6 , 5 , 1 , 3\4 , 3 , 1], [ !\! , !\10, 3 , 1 , 4 , 2], [ !\! , !\! , !\3 , 2 , 1 , !\! ]]). /* Solution: !\ ! 16\ ! 17\ ! !\ ! !\ ! 16\ ! 22\ ! !\ ! 13\ ! 14\ ! !\17 9 8 17\ ! !\14 9 5 30\16 7 9 !\24 7 9 8 15\35 7 8 9 6 5 !\ ! 26\ ! 28\16 9 7 35\16 9 7 24\ ! 22\ ! !\ 4 1 3 !\17 8 9 16\24 8 9 7 !\14 6 8 !\ ! 6\35 5 7 6 8 9 !\ 3 2 1 30\21 4 8 9 !\ 3 2 1 !\32 9 7 8 2 6 17\ ! !\ 6 4 2 !\23 8 9 6 24\16 7 9 16\ 4 1 3 !\ ! 14\ ! 13\17 9 8 17\17 8 9 16\ ! 17\ ! !\35 5 6 7 9 8 !\24 7 9 8 !\16 9 7 !\16 7 9 !\ ! !\16 7 9 */ matrix(kakuro17, [[ !\! ,16\! ,17\! , !\! , !\! ,16\! ,22\! , !\! ,13\! ,14\! ], [ !\17, _ , _ ,17\! , !\14, _ , _ ,30\16, _ , _ ], [ !\24, _ , _ , _ ,15\35, _ , _ , _ , _ , _ ], [ !\! ,26\! ,28\16, _ , _ ,35\16, _ , _ ,24\! ,22\! ], [ !\4 , _ , _ , !\17, _ , _ ,16\24, _ , _ , _ ], [ !\14, _ , _ , !\! , 6\35, _ , _ , _ , _ , _ ], [ !\3 , _ , _ ,30\21, _ , _ , _ , !\3 , _ , _ ], [ !\32, _ , _ , _ , _ , _ ,17\! , !\6 , _ , _ ], [ !\23, _ , _ , _ ,24\16, _ , _ ,16\4 , _ , _ ], [ !\! ,14\! ,13\17, _ , _ ,17\17, _ , _ ,16\! ,17\! ], [ !\35, _ , _ , _ , _ , _ , !\24, _ , _ , _ ], [ !\16, _ , _ , !\16, _ , _ , !\! , !\16, _ , _ ]]). /* Author: Takei Daisuke Solution: !\ ! 7\ ! 11\ ! 28\ ! 12\ ! !\ ! 24\ ! 23\ ! 15\ ! !\ ! 4\ ! 41\ ! 14\ ! 7\ ! !\10 1 3 2 4 !\12 5 6 1 !\10 3 4 2 1 !\24 4 5 7 8 18\20 7 9 4 19\15 1 8 4 2 !\ 7 2 1 4 7\27 7 9 8 2 1 10\20 9 7 4 !\ ! !\16 2 6 4 1 3 !\31 8 9 6 7 1 !\ ! !\ ! !\ ! 19\ 9 3 1 5 35\ ! !\ ! 19\ 8 2 1 5 17\ ! !\ ! !\ ! 12\17 4 1 2 3 7 9\16 2 4 3 6 1 7\ ! !\ 8 1 2 5 !\16 2 6 1 4 3 !\ 6 2 3 1 !\17 8 9 34\ ! !\ ! 20\22 8 5 9 35\ ! !\ ! 23\ 8 6 2 !\13 3 1 9 16\20 2 5 3 1 9 18\ 9 3 2 4 !\ ! !\32 3 8 5 7 9 !\17 3 6 2 1 5 !\ ! !\ ! !\ ! 33\ 7 4 2 1 23\ ! !\ ! 33\24 7 9 8 15\ ! !\ ! !\ ! 23\34 8 6 9 4 7 10\32 8 5 7 9 3 6\ ! !\22 6 9 7 !\30 6 2 5 9 8 !\ 6 2 1 3 !\12 8 4 29\ ! !\ ! 29\ 9 1 3 5 31\ ! !\ ! 36\ 7 5 2 !\24 9 7 8 10\30 9 4 2 7 8 24\ 7 2 4 1 !\ ! !\35 5 6 7 8 9 !\19 4 1 9 3 2 !\ ! !\ ! !\ ! 28\ 7 2 1 4 26\ ! !\ ! 10\24 7 8 9 26\ ! !\ ! !\ ! 23\31 8 5 2 7 9 23\34 4 6 7 8 9 23\ ! !\19 9 7 3 10\26 1 6 8 2 9 12\24 7 8 9 !\28 8 9 4 7 !\10 3 6 1 !\30 9 6 7 8 !\14 6 4 1 3 !\20 8 9 3 !\12 3 1 2 6 */ matrix(hard, [[ !\! , 7\! ,11\! ,28\! ,12\! , !\! ,24\! ,23\! ,15\! , !\! , 4\! ,41\! ,14\! , 7\! ], [ !\10, _ , _ , _ , _ , !\12, _ , _ , _ , !\10, _ , _ , _ , _ ], [ !\24, _ , _ , _ , _ ,18\20, _ , _ , _ ,19\15, _ , _ , _ , _ ], [ !\7 , _ , _ , _ , 7\27, _ , _ , _ , _ , _ ,10\20, _ , _ , _ ], [ !\! , !\16, _ , _ , _ , _ , _ , !\31, _ , _ , _ , _ , _ , !\! ], [ !\! , !\! ,19\9 , _ , _ , _ ,35\! , !\! ,19\8 , _ , _ , _ ,17\! , !\! ], [ !\! ,12\17, _ , _ , _ , _ , _ , 9\16, _ , _ , _ , _ , _ , 7\! ], [ !\8 , _ , _ , _ , !\16, _ , _ , _ , _ , _ , !\6 , _ , _ , _ ], [ !\17, _ , _ ,34\! , !\! ,20\22, _ , _ , _ ,35\! , !\! ,23\8 , _ , _ ], [ !\13, _ , _ , _ ,16\20, _ , _ , _ , _ , _ ,18\9 , _ , _ , _ ], [ !\! , !\32, _ , _ , _ , _ , _ , !\17, _ , _ , _ , _ , _ , !\! ], [ !\! , !\! ,33\7 , _ , _ , _ ,23\! , !\! ,33\24, _ , _ , _ ,15\! , !\! ], [ !\! ,23\34, _ , _ , _ , _ , _ ,10\32, _ , _ , _ , _ , _ , 6\! ], [ !\22, _ , _ , _ , !\30, _ , _ , _ , _ , _ , !\6 , _ , _ , _ ], [ !\12, _ , _ ,29\! , !\! , 29\9, _ , _ , _ ,31\! , !\! ,36\7 , _ , _ ], [ !\24, _ , _ , _ ,10\30, _ , _ , _ , _ , _ ,24\7 , _ , _ , _ ], [ !\! , !\35, _ , _ , _ , _ , _ , !\19, _ , _ , _ , _ , _ , !\! ], [ !\! , !\! ,28\7 , _ , _ , _ ,26\! , !\! ,10\24, _ , _ , _ ,26\! , !\! ], [ !\! ,23\31, _ , _ , _ , _ , _ ,23\34, _ , _ , _ , _ , _ , 23\!], [ !\19, _ , _ , _ ,10\26, _ , _ , _ , _ , _ ,12\24, _ , _ , _ ], [ !\28, _ , _ , _ , _ , !\10, _ , _ , _ , !\30, _ , _ , _ , _ ], [ !\14, _ , _ , _ , _ , !\20, _ , _ , _ , !\12, _ , _ , _ , _ ]]). % hakank: Extract the (unique) variables % from the List of lists L. term_variables(L,Flatten) => Flatten1 = [], foreach(LL in L) foreach(LLL in LL) if var(LLL) then Flatten1 := Flatten1 ++ [LLL] end end end, Flatten2 = remove_dups(Flatten1), Flatten = Flatten2.