:- use_module(library(clpfd)). :- use_module(library(lists)). % https://www.chegg.com/homework-help/questions-and-answers/please-make-one-c-program-include-4x4-9x9-sudoku-needs-input-file-complete-sudoku-input-fi-q14240275 killer_task(chegg, [ abbc, adec, fdeg, fhhg], [a-7,b-5,c-3,d-6,e-4,f-3,g-7,h-5]). % https://www.dailykillersudoku.com/search?n=211 % Difficulty (for humans): 1 on a scale 1..10 killer_task(dks211, [ 'abbbcdeef', 'agggcdhhf', 'aaiicdhjk', 'allmmnnjk', 'ooppmqqrr', 'stuummvvw', 'stxyzAAww', 'BxxyzCCCw', 'BDDyzEEEw'], [a-21,b-20,c-19,d-6,e-4,f-9,g-14,h-19,i-12, j-11,k-10,l-10,m-29,n-10,o-11,p-13,q-9, r-10,s-13,t-8,u-6,v-9,w-28,x-15,y-10,z-14, 'A'-8,'B'-12,'C'-21,'D'-7,'E'-17]). % https://www.dailykillersudoku.com/search?n=15 % Difficulty (for humans): 10 on a scale 1..10 killer_task(dks15, [ aaaabcccc, adeebffgc, hddebfggi, hjjkkklli, mnnkkkoop, mnqqqqqop, mmrrsttpp, uurrsttvv, uuuusvvvv], [a-23,b-12,c-27,d-13,e-16,f-18,g-17,h-13,i-9,j-13,k-27, l-4,m-20,n-16,o-15,p-20,q-35,r-19,s-14,t-19,u-23,v-32]). :- ensure_loaded(timing). timed_run(Test, Label) :- write('Timing test '), write(Test), nl, dsum_option(DSum), time(Test-DSum-Label, ( run(Test, DSum, Label), /* To get all solutions for this option: */ fail ) ), /* To run with all possible options: */ fail. timed_run(_Test, _Label) :- nl. run(Test, DSum, Label) :- call(Test, Grid, DSum), append(Grid, Vars), do_labeling(Label, Vars), print(Grid), nl. do_labeling(Label, Vars) :- ( Label = none -> true ; Label = shave_once(Label1) -> maplist(shave_all, Vars), do_labeling(Label1, Vars) ; labeling(Label, Vars) ). labeling_option1(none). labeling_option1([ffc]). labeling_option(Lab) :- labeling_option1(Lab0), ( Lab = Lab0 ; Lab = shave_once(Lab0) ). dsum_option(dsum0). % dsum_option(dsum1). dsum_option(dsum2). dsum_option(dsum3). run_all :- labeling_option(Lab), run_all(Lab), fail. run_all(Label) :- killer_task(Test, _, _), timed_run(Test, Label), fail. run_all(_Label). dsum0(L, Sum) :- sum(L, #=, Sum), all_distinct(L). dsum1(L, Sum) :- dsum0(L, Sum), minimum(Min, L), length(L, N), Gap is N*(N-1)//2, Sum #>= N*Min+Gap. dsum2(L, Sum) :- dsum0(L, Sum), maximum(Max, L), length(L, N), Gap is N*(N-1)//2, Sum #=< N*Max-Gap. dsum3(L, Sum) :- dsum0(L, Sum), minimum(Min, L), maximum(Max, L), length(L, N), Gap is (N-1)*(N-2)//2, Sum #=< Min+ (N-1)*Max-Gap, Sum #>= Max+ (N-1)*Min+Gap. chegg0([[A,B,C,D], [E,F,G,H], [I,J,K,L], [M,N,O,P]], DSum) :- domain([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P],1,4), all_distinct([A,B,C,D]), all_distinct([E,F,G,H]), all_distinct([I,J,K,L]), all_distinct([M,N,O,P]), all_distinct([A,E,I,M]), all_distinct([B,F,J,N]), all_distinct([C,G,K,O]), all_distinct([D,H,L,P]), all_distinct([A,E,B,F]), all_distinct([C,G,D,H]), all_distinct([I,M,J,N]), all_distinct([K,O,L,P]), call(DSum,[A,E],7), call(DSum,[B,C],5), call(DSum,[D,H],3), call(DSum,[F,J],6), call(DSum,[G,K],4), call(DSum,[I,M],3), call(DSum,[L,P],7), call(DSum,[N,O],5). chegg(Grid,DSum) :- Grid=[ [A1,A2,A3,A4], [B1,B2,B3,B4], [C1,C2,C3,C4], [D1,D2,D3,D4] ], append(Grid,Vars), domain(Vars,1,4), all_distinct([A1,A2,A3,A4]), all_distinct([B1,B2,B3,B4]), all_distinct([C1,C2,C3,C4]), all_distinct([D1,D2,D3,D4]), all_distinct([A1,B1,C1,D1]), all_distinct([A2,B2,C2,D2]), all_distinct([A3,B3,C3,D3]), all_distinct([A4,B4,C4,D4]), all_distinct([A1,B1,A2,B2]), all_distinct([A3,B3,A4,B4]), all_distinct([C1,D1,C2,D2]), all_distinct([C3,D3,C4,D4]), call(DSum,[A1,B1],7), call(DSum,[A2,A3],5), call(DSum,[A4,B4],3), call(DSum,[B2,C2],6), call(DSum,[B3,C3],4), call(DSum,[C1,D1],3), call(DSum,[C4,D4],7), call(DSum,[D2,D3],5). dks15(Grid,DSum) :- Grid=[ [A1,A2,A3,A4,A5,A6,A7,A8,A9], [B1,B2,B3,B4,B5,B6,B7,B8,B9], [C1,C2,C3,C4,C5,C6,C7,C8,C9], [D1,D2,D3,D4,D5,D6,D7,D8,D9], [E1,E2,E3,E4,E5,E6,E7,E8,E9], [F1,F2,F3,F4,F5,F6,F7,F8,F9], [G1,G2,G3,G4,G5,G6,G7,G8,G9], [H1,H2,H3,H4,H5,H6,H7,H8,H9], [I1,I2,I3,I4,I5,I6,I7,I8,I9] ], append(Grid,Vars), domain(Vars,1,9), all_distinct([A1,A2,A3,A4,A5,A6,A7,A8,A9]), all_distinct([B1,B2,B3,B4,B5,B6,B7,B8,B9]), all_distinct([C1,C2,C3,C4,C5,C6,C7,C8,C9]), all_distinct([D1,D2,D3,D4,D5,D6,D7,D8,D9]), all_distinct([E1,E2,E3,E4,E5,E6,E7,E8,E9]), all_distinct([F1,F2,F3,F4,F5,F6,F7,F8,F9]), all_distinct([G1,G2,G3,G4,G5,G6,G7,G8,G9]), all_distinct([H1,H2,H3,H4,H5,H6,H7,H8,H9]), all_distinct([I1,I2,I3,I4,I5,I6,I7,I8,I9]), all_distinct([A1,B1,C1,D1,E1,F1,G1,H1,I1]), all_distinct([A2,B2,C2,D2,E2,F2,G2,H2,I2]), all_distinct([A3,B3,C3,D3,E3,F3,G3,H3,I3]), all_distinct([A4,B4,C4,D4,E4,F4,G4,H4,I4]), all_distinct([A5,B5,C5,D5,E5,F5,G5,H5,I5]), all_distinct([A6,B6,C6,D6,E6,F6,G6,H6,I6]), all_distinct([A7,B7,C7,D7,E7,F7,G7,H7,I7]), all_distinct([A8,B8,C8,D8,E8,F8,G8,H8,I8]), all_distinct([A9,B9,C9,D9,E9,F9,G9,H9,I9]), all_distinct([A1,B1,C1,A2,B2,C2,A3,B3,C3]), all_distinct([A4,B4,C4,A5,B5,C5,A6,B6,C6]), all_distinct([A7,B7,C7,A8,B8,C8,A9,B9,C9]), all_distinct([D1,E1,F1,D2,E2,F2,D3,E3,F3]), all_distinct([D4,E4,F4,D5,E5,F5,D6,E6,F6]), all_distinct([D7,E7,F7,D8,E8,F8,D9,E9,F9]), all_distinct([G1,H1,I1,G2,H2,I2,G3,H3,I3]), all_distinct([G4,H4,I4,G5,H5,I5,G6,H6,I6]), all_distinct([G7,H7,I7,G8,H8,I8,G9,H9,I9]), call(DSum,[A1,A2,A3,A4,B1],23), call(DSum,[A5,B5,C5],12), call(DSum,[A6,A7,A8,A9,B9],27), call(DSum,[B2,C2,C3],13), call(DSum,[B3,B4,C4],16), call(DSum,[B6,B7,C6],18), call(DSum,[B8,C7,C8],17), call(DSum,[C1,D1],13), call(DSum,[C9,D9],9), call(DSum,[D2,D3],13), call(DSum,[D4,D5,D6,E4,E5,E6],27), call(DSum,[D7,D8],4), call(DSum,[E1,F1,G1,G2],20), call(DSum,[E2,E3,F2],16), call(DSum,[E7,E8,F8],15), call(DSum,[E9,F9,G8,G9],20), call(DSum,[F3,F4,F5,F6,F7],35), call(DSum,[G3,G4,H3,H4],19), call(DSum,[G5,H5,I5],14), call(DSum,[G6,G7,H6,H7],19), call(DSum,[H1,H2,I1,I2,I3,I4],23), call(DSum,[H8,H9,I6,I7,I8,I9],32). dks211(Grid,DSum) :- Grid=[ [A1,A2,A3,A4,A5,A6,A7,A8,A9], [B1,B2,B3,B4,B5,B6,B7,B8,B9], [C1,C2,C3,C4,C5,C6,C7,C8,C9], [D1,D2,D3,D4,D5,D6,D7,D8,D9], [E1,E2,E3,E4,E5,E6,E7,E8,E9], [F1,F2,F3,F4,F5,F6,F7,F8,F9], [G1,G2,G3,G4,G5,G6,G7,G8,G9], [H1,H2,H3,H4,H5,H6,H7,H8,H9], [I1,I2,I3,I4,I5,I6,I7,I8,I9] ], append(Grid,Vars), domain(Vars,1,9), all_distinct([A1,A2,A3,A4,A5,A6,A7,A8,A9]), all_distinct([B1,B2,B3,B4,B5,B6,B7,B8,B9]), all_distinct([C1,C2,C3,C4,C5,C6,C7,C8,C9]), all_distinct([D1,D2,D3,D4,D5,D6,D7,D8,D9]), all_distinct([E1,E2,E3,E4,E5,E6,E7,E8,E9]), all_distinct([F1,F2,F3,F4,F5,F6,F7,F8,F9]), all_distinct([G1,G2,G3,G4,G5,G6,G7,G8,G9]), all_distinct([H1,H2,H3,H4,H5,H6,H7,H8,H9]), all_distinct([I1,I2,I3,I4,I5,I6,I7,I8,I9]), all_distinct([A1,B1,C1,D1,E1,F1,G1,H1,I1]), all_distinct([A2,B2,C2,D2,E2,F2,G2,H2,I2]), all_distinct([A3,B3,C3,D3,E3,F3,G3,H3,I3]), all_distinct([A4,B4,C4,D4,E4,F4,G4,H4,I4]), all_distinct([A5,B5,C5,D5,E5,F5,G5,H5,I5]), all_distinct([A6,B6,C6,D6,E6,F6,G6,H6,I6]), all_distinct([A7,B7,C7,D7,E7,F7,G7,H7,I7]), all_distinct([A8,B8,C8,D8,E8,F8,G8,H8,I8]), all_distinct([A9,B9,C9,D9,E9,F9,G9,H9,I9]), all_distinct([A1,B1,C1,A2,B2,C2,A3,B3,C3]), all_distinct([A4,B4,C4,A5,B5,C5,A6,B6,C6]), all_distinct([A7,B7,C7,A8,B8,C8,A9,B9,C9]), all_distinct([D1,E1,F1,D2,E2,F2,D3,E3,F3]), all_distinct([D4,E4,F4,D5,E5,F5,D6,E6,F6]), all_distinct([D7,E7,F7,D8,E8,F8,D9,E9,F9]), all_distinct([G1,H1,I1,G2,H2,I2,G3,H3,I3]), all_distinct([G4,H4,I4,G5,H5,I5,G6,H6,I6]), all_distinct([G7,H7,I7,G8,H8,I8,G9,H9,I9]), call(DSum,[G6,G7],8), call(DSum,[H1,I1],12), call(DSum,[H6,H7,H8],21), call(DSum,[I2,I3],7), call(DSum,[I6,I7,I8],17), call(DSum,[A1,B1,C1,C2,D1],21), call(DSum,[A2,A3,A4],20), call(DSum,[A5,B5,C5],19), call(DSum,[A6,B6,C6],6), call(DSum,[A7,A8],4), call(DSum,[A9,B9],9), call(DSum,[B2,B3,B4],14), call(DSum,[B7,B8,C7],19), call(DSum,[C3,C4],12), call(DSum,[C8,D8],11), call(DSum,[C9,D9],10), call(DSum,[D2,D3],10), call(DSum,[D4,D5,E5,F5,F6],29), call(DSum,[D6,D7],10), call(DSum,[E1,E2],11), call(DSum,[E3,E4],13), call(DSum,[E6,E7],9), call(DSum,[E8,E9],10), call(DSum,[F1,G1],13), call(DSum,[F2,G2],8), call(DSum,[F3,F4],6), call(DSum,[F7,F8],9), call(DSum,[F9,G8,G9,H9,I9],28), call(DSum,[G3,H2,H3],15), call(DSum,[G4,H4,I4],10), call(DSum,[G5,H5,I5],14). :- multifile portray/1. user:portray(Matrix) :- nonvar(Matrix), Matrix = [R|_], nonvar(R), R = [_|_], length(Matrix, _), !, write('['), ( append(_, [Row|Rest], Matrix), nl, write(' '), print(Row), ( Rest = [] -> true ; write(','), fail ) -> write('\n]') ). % Shave off variable X all values within the domain of X. % Equivalent to cdisj([X=V1,...X=Vn], X), where the domain % of X is {V1,...,Vn}. shave_all(X) :- fd_set(X, FD), fdset_to_list(FD, L), findall(X, member(X,L), Vs), list_to_fdset(Vs, FD1), X in_set FD1.