/* Skyskraper puzzle in Picat. http://www.puzzlepicnic.com/genre?flats http://www.puzzlepicnic.com/puzzle?909 http://www.puzzlemix.com/Skyscraper Compare with a pure (and naive) logic programming approach: http://www.hakank.org/picat/skyscraper_lp.pi The SAT solver is much faster than CP, especially on the harder problems, such as SICStus Prolog's instances 582 and 707. The SAT solver solves all 19 instances in about 0.19s. The CP solver take 0.80s just on instance 582 and "forever" on 707. 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. import sat. % much faster main => go. % Problems without cell hints (first set) % The second set (from SICStus Prolog) is tested in go4/0. go => 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 % go2 => 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. % % "Waffle problem" % Problem from http://www.hpcodewars.org/past/cw16/problems/Prob20--WaffleStacking.pdf % Where the instance is placed in a text file. % (It's the same instance as problem 4 below.) % go3 => Waffle = [split(Line).map(to_integer) : Line in read_file_lines("skyscraper_waffle.txt")], [CU,CL] = [Waffle.first(),Waffle.last()], [RL,RR] = [Waffle[I] : I in 2..Waffle.length-1].transpose(), println([cu=CU,rl=RL,rr=RR,cl=CL]), skyscraper(CU,CL,RL,RR,X), print_solution(CU,CL,RL,RR,X), 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. % % solve a single instance % one_problem(P) => problem(P,CU,CL,RL,RR), skyscraper(CU,CL,RL,RR,X), print_solution(CU,CL,RL,RR,X), nl. % % Solve a Skyscraper problem. X is the solution. % skyscraper(CU,CL,RL,RR, X) => N = CU.length, X = new_array(N,N), X :: 1..N, foreach(I in 1..N) % rows all_different([X[I,J] : J in 1..N]), 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]), all_different([X[J,I] : J in 1..N]), 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, solve($[max,split],X). 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) => N = length(Y), NPos :: 1..N, element(NPos,Y,N), % identify position of N Num #=< NPos, Num #=< N-Y[1]+1, % Now count all the positions where Y[I] is larger than all Y[1..I-1] Num #= 1+ sum([ sum([Y[I] #> Y[J] : J in 1..I-1]) #= I-1 : I in 2..N]). % % 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]. % % 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,_]).