% zamkeller.pi (by Neng-Fa Zhou, Sep. 29, 2013 % http://www.hakank.org/constraint_programming/cp2013_competition_20130919.pdf % % Use the following command to solve an instance File % % picat zamkeller < File % % or type 'test' to solve the included instance. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% import sat. main => read_int(stdin) = N, read_int(stdin) = K, zemkeller(N,K). test => zemkeller(20,3). zemkeller(N,K) => Ps = new_array(K), foreach(I in 1..K) Di = [E : E in 1..N, E mod I==0], Ps[I] = new_list(Di.length), Ps[I] :: Di, all_different(Ps[I]), if I>1 then gen_order_constr(Ps[1],Ps[I]) end end, MinAlter #= min([Alter : I in 1..K, alter(Ps[I],0,Alter)]), solve(\$[max(MinAlter),report(output(MinAlter,Ps))],(Ps,MinAlter)). % ensure that the order of any two numbers in P1 is preserved in Pi gen_order_constr(P1,[E1,E2|Pi]) => element(I1,P1,E1), element(I2,P1,E2), I1 #< I2, gen_order_constr(P1,[E2|Pi]). gen_order_constr(_,_) => true. alter([E1,E2,E3|P],Alter0,Alter) => B12 #<=> (E1# (E2#((B12 #/\ #~B23) #\/ (#~B12 #/\ B23)), alter([E2,E3|P],\$Alter0+B,Alter). alter(_,Alter0,Alter) => Alter=Alter0. output(MinAlter,Ps) => printf("p = %w;%n",Ps[1]), printf("obj = %w;%n",MinAlter), printf("%% method = \"SAT\";%n").