/* Skyskraper puzzle in Picat. http://www.puzzlepicnic.com/genre?flats http://www.puzzlepicnic.com/puzzle?909 http://www.puzzlemix.com/Skyscraper Compare with the CP approach: http://www.hakank.org/picat/skyscraper.pi This program use a "pure" logic programming (LP) approach, where the latin square is generated by permutation/2. For problems without cell hints the LP approach is almost as fast as the CP aproach, both for first solution and for proving unicity of the solution. The times for the 6x6 instance with cell hints has comparable solving time. However, for the 7x7 problem with cell hints, this program LP is much slower Without cell hints: Problem Size CP (all) LP (one solution) LP (all solutions) -------------------------------------------------------------- 1 4x4 0.0s 0.0s 0.004s 2 5x5 0.004s 0.004s 0.004s 3 4x4 0.0s 0.004s 0.004s 4 5x5 0.004s 0.0s 0.0.6s 5 5x5 0.0s 0.12s 0.14s 6 5x5 0.004s 0.13s 0.0s With cell hints (only faster approach) Problem Size CP (all) LP (one solution) LP (all solutions) -------------------------------------------------------------- 1 6x6 0.0s 0.012s 0.016s 2 7x7 0.09s 20990.2s (~6h) - For the SICStus Prolog instances this approach is much slower than the SAT solver in skyscraper.pi (all 19 instances are solved in 0.19s). This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. % import cp. main => go. % Problems without cell hints % Search for first solution. go => NumProblems = 6, foreach(P in 1..NumProblems) println(problem=P), time(one_problem(P)), nl end, nl. % Search for all solutions go1 => NumProblems = 6, foreach(P in 1..NumProblems) println(problem=P), time2(All=findall(_,one_problem(P))), println(num_solutions=All.length), nl end, nl. % % Problems with cell hints % One solution. go2 => println("Cell with hints: First solution"), Problems = [hint1,hint2], foreach(Problem in Problems) println(problem=Problem), problem(Problem,CU,CL,RL,RR,X), time(skyscraper(CU,CL,RL,RR,X)), print_solution(CU,CL,RL,RR,X), nl end, nl. % Problems with cell hints: Prove uniqueness. go3 => Problems = [hint1,hint2], foreach(Problem in Problems) println(problem=Problem), problem(Problem,CU,CL,RL,RR,X), time2(All = findall([CU,CL,RL,RR,X], skyscraper(CU,CL,RL,RR,X))), foreach([CUX,CLX,RLX,RRX,XX] in All) print_solution(CUX,CLX,RLX,RRX,XX) end, println(num_solutions=All.length), nl end, nl. % % Testing SICStus Prolog's instances. % go4 ?=> nolog, Instances = findall(Name, data(Name,Size, _,_,_,_)), member(Name,Instances), println(name=Name), % CU: Column Upper (SICStus: top) % CL: Column lower (SICStus: bottom) % RL: Row left (SICStus: left) % RR: Row right (SICStus: right) data(Name,Size,CU,RL,CL,RR), time(skyscraper(CU,CL,RL,RR,X)), % prove unicity print_solution(CU,CL,RL,RR,X), nl, fail, nl. go4 => true. one_problem(P) => problem(P,CU,CL,RL,RR), println(cu=CU), println(cl=CL), println(rl=RL), println(rr=RR), skyscraper(CU,CL,RL,RR,X), % foreach(Row in X) println(Row) end, print_solution(CU,CL,RL,RR,X), nl. % faster generator of latin squares latin_square([_]) => true. latin_square([A,B|T]) => permutation(A,B), isSafe(A,B), latin_square([B|T]). isSafe([], []) => true. isSafe([H1|T1], [H2|T2]) => H1 != H2, isSafe(T1, T2). skyscraper(CU,CL,RL,RR, X) => N = CU.length, println(n=N), if var(X) then X = new_array(N,N) end, L = 1..N, foreach(I in 1..N) % rows permutation([X[I,J]: J in 1..N], L), RL_A = [X[I,J]: J in 1..N], num_skyscrapes(RL_A, RL[I]), RR_A = reverse(RL_A), num_skyscrapes(RR_A, RR[I]), % column permutation([X[J,I]: J in 1..N], L), CU_A = [X[J,I]: J in 1..N], num_skyscrapes(CU_A, CU[I]), CL_A = reverse(CU_A), num_skyscrapes(CL_A, CL[I]) end. print_solution(CU,CL,RL,RR,X) => N = CU.length, println("Solution:"), print(" "), foreach(I in 1..N) printf("%w ",cc(CU[I])) end, nl, foreach(I in 1..N) printf(" %w %w %w\n", cc(RL[I]),[X[I,J] : J in 1..N], cc(RR[I])) end, print(" "), foreach(I in 1..N) printf("%w ",cc(CL[I])) end, nl. cc(V) = cond(var(V), "_", V). % % number of seen skyscrapes % num_skyscrapes(Y, Num) => if not(var(Num)) then N = length(Y), nth(NPos,Y,N), % identify position of N Num =< NPos, Num =< N-Y[1]+1, % Now count all the positions where Y[I] is larger then all Y[1..I-1] Num = 1+ sum([1 : I in 2..N, sum([ 1 :J in 1..I-1, Y[I] > Y[J]]) = I-1]) end. % % Puzzle: % 1 2 2 3 % 1 4 % 3 2 % 2 2 % 3 1 % 3 2 2 1 % % Solution: % 1 2 2 3 % 1 4 3 2 1 4 % 3 1 2 4 3 2 % 2 3 4 1 2 2 % 3 2 1 3 4 1 % 3 2 2 1 % problem(1,CU,CL,RL,RR) => CU = [1,2,2,3], CL = [3,2,2,1], RL = [1,3,2,3], RR = [4,2,2,1]. % http://www.puzzlepicnic.com/puzzle?900 problem(2,CU,CL,RL,RR) => CU = [_,_,_,_,_], CL = [_,_,_,_,_], RL = [5,2,3,1,2], RR = [1,4,2,4,2]. % http://logicgames.blogspot.com/2008/06/skyscraper.html problem(3,CU,CL,RL,RR) => CU = [_,1,2,_], CL = [_,_,_,_], RL = [_,3,3,_], RR = [_,_,2,_]. % From % http://stackoverflow.com/questions/22096963/waffle-stacking-puzzle-algorithm problem(4, CU,CL,RL,RR) => CU = [2,2,3,2,1], CL = [3,2,1,3,4], RL = [4,1,3,2,3], RR = [1,4,2,2,2]. % From % http://www.puzzlemix.com/Skyscraper problem(5, CU,CL,RL,RR) => CU = [4,2,1,2,3], CL = [1,4,3,2,2], RL = [3,2,3,2,1], RR = [3,4,1,2,2]. % From % http://www.puzzlemix.com/playgrid.php?id=74166&type=sky&share=1 % (Skyscraper-5 87) problem(6, CU,CL,RL,RR) => CU = [4,_,_,_,4], CL = [_,2,3,_,_], RL = [_,_,_,_,_], RR = [3,_,_,_,2]. % From http://www.brainbashers.com/showskyscraper.asp % Nov 03 - Hard 7x7 (random) problem(7,CU,CL,RL,RR) => CU = [_,3,_,_,4,4,3], CL = [5,4,_,3,_,_,2], RL = [_,_,_,_,_,_,_], RR = [_,_,_,_,_,_,_]. % % Instances with hints. % % From http://www.brainbashers.com/showskyscraper.asp % Apr 12 Easy 6x6 % % Note: This instance has also hints. % problem(hint1,CU,CL,RL,RR,Hints) => CU = [4,2,1,2,2,3], CL = [2,2,4,3,2,1], RL = [3,2,2,2,1,4], RR = [4,2,3,3,3,1], Hints = { {_,_,_,_,2,_}, {_,_,2,_,_,_}, {1,_,_,_,_,_}, {_,_,_,6,_,_}, {_,_,4,_,_,_}, {_,_,1,_,_,_} }. % http://www.brainbashers.com/showskyscraper.asp % Nov 03 Hard 7x7 [Random] problem(hint2,CU,CL,RL,RR,Hints) => CU = [_,3,_,_,4,4,3], CL = [5,4,_,3,_,_,2], RL = [2,_,_,7,_,3,_], RR = [_,3,3,_,2,_,_], Hints = { {_,_,_,_,_,_,_}, {_,_,_,_,_,3,_}, {_,_,_,_,_,_,_}, {_,_,_,_,_,_,_}, {_,_,_,_,_,_,_}, {_,_,_,2,_,_,_}, {_,_,_,_,_,_,_} }. % % The following no cell hints problems are % from the SICStus Prolog model skyscrapers.pl % data(a, 4, [_,1,2,_], % top [_,2,_,3], % left [_,_,1,_], % bottom [_,1,3,_]). % right data(572, 4, [_,_,_,4], [_,_,3,2], [_,_,_,_], [_,_,_,_]). data(537, 4, [1,3,3,2], [1,4,2,3], [3,2,1,3], [2,1,2,2]). data(718, 5, [_,_,_,_,_], [_,_,_,_,_], [_,_,_,_,_], [4,3,2,_,5]). data(463, 4, [_,2,_,2], [_,_,2,2], [2,_,2,_], [_,_,2,2]). data(461, 5, [3,1,2,2,2], [2,3,2,1,4], [2,4,3,1,2], [3,3,1,3,2]). data(688, 5, [2,2,1,2,3], [3,1,3,2,3], [3,2,4,2,1], [3,2,2,4,1]). data(573, 5, [2,4,3,1,2], [4,1,3,3,2], [2,1,3,3,2], [2,3,3,1,2]). data(900, 5, [_,_,_,_,_], [5,2,3,1,2], [_,_,_,_,_], [1,4,2,4,2]). data(1049, 5, [_,2,_,2,3], [3,2,_,4,_], [2,4,3,_,_], [_,2,3,_,2]). data(909, 6, [_,_,_,4,2,_], [_,_,2,3,_,_], [_,_,3,_,4,5], [_,3,_,_,_,3]). data(1174, 6, [_,4,_,3,_,3], [_,_,_,4,_,3], [_,_,_,_,4,2], [_,3,5,_,2,_]). data(1489, 6, [3,2,3,2,4,1], [3,3,2,1,3,2], [2,1,4,3,2,3], [1,3,4,3,2,4]). data(575, 6, [1,2,2,4,3,3], [1,2,2,4,4,4], [5,3,5,3,1,2], [4,2,5,3,1,2]). data(602, 6, [_,_,3,_,5,_], [_,_,4,1,4,_], [_,2,_,3,_,_], [_,2,2,3,_,4]). data(627, 6, [1,3,3,3,2,2], [1,3,2,2,3,3], [5,2,3,1,2,2], [3,2,3,4,1,2]). data(576, 7, [1,4,4,3,2,3,4], [1,5,2,2,3,4,4], [4,4,3,5,4,2,1], [4,3,4,2,3,2,1]). data(582, 7, [4,4,2,3,2,1,3], [3,3,3,5,2,1,2], [2,1,2,3,3,3,2], [2,3,2,1,2,4,2]). data(707, 8, [4,_,1,4,6,_,_,_], [_,_,2,2,_,4,_,4], [4,_,6,5,_,3,4,_], [_,_,1,_,_,3,3,_]).