/* Tents puzzle in Picat. See for example http://www.crauswords.com/tents.html """ A Tents puzzle consists of a square or rectangular array of squares in which some of the squares contain a tree, with the remainder containing only grass. The puzzle is solved by placing tents into selected grassy squares so that each tree has its own tent (either horizontally or vertically), and each tent has its own tree (either horizontally or vertically). The squares in which tents are placed must not touch on either the sides or the corners. Numbers located to the side and to the bottom of the puzzle tell you how many tents are in each row and column. Problem: T: Tree _ T _ _ _ _ 1 _ _ _ _ T _ 2 _ _ T _ _ _ 0 _ T _ T _ _ 3 T _ _ _ T _ 0 _ _ T _ _ _ 2 2 1 2 0 2 1 Solution (e: tEnt) e T _ _ _ _ 1 _ _ e _ T e 2 _ _ T _ _ _ 0 e T e T e _ 3 T _ _ _ T _ 0 _ e T _ e _ 2 2 1 2 0 2 1 """ Also see: - https://www.brainbashers.com/tents.asp - https://www.brainbashers.com/tentshelp.asp This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go ?=> nolog, problem(2,N,Puzzle,Rows,Cols), tents(N,Puzzle,Rows,Cols, X), print_solution(N,X), fail, nl. go => true. print_solution(N,X) => Map = new_map([0='_',1='t',2='^']), foreach(I in 1..N) foreach(J in 1..N) print(Map.get(X[I,J])) end, nl end, nl. tents(N,Puzzle,Rows,Cols, X) => T = 1, % Tree E = 2, % tEnt X = new_array(N,N), X :: 0..E, % Handle number of tents for rows and columns foreach(I in 1..N) sum([X[I,J] #= E : J in 1..N]) #= Rows[I], sum([X[J,I] #= E : J in 1..N]) #= Cols[I] end, foreach(I in 1..N, J in 1..N) if Puzzle[I,J] == T then X[I,J] #= T, % each tree has its tent sum([X[I+A,J+B] #= E : A in -1..1, member(A+I,1..N), B in -1..1, member(B+J,1..N), abs(A+B)==1]) #> 0 else X[I,J] #!= T end, % (note that we have to use #= and #=> here since we are testing against a decision variable) X[I,J] #= E #=> % each tent has its tree sum([X[I+A,J+B] #= T : A in -1..1, member(A+I,1..N), B in -1..1, member(B+J,1..N), abs(A+B)==1]) #> 0 #/\ % no two tents must touch sum([X[I+A,J+B] #= E : A in -1..1, member(A+I,1..N), B in -1..1, member(B+J,1..N), (A != 0; B != 0)]) #= 0 end, % same number of Trees and Tents sum([X[I,J] #= E : I in 1..N, J in 1..N]) #= sum([X[I,J] #= T : I in 1..N, J in 1..N]), Vars = X, println(solve), solve($[],Vars). % % Problems % % % From http://www.crauswords.com/tents.html % % Solution (t=tree, e=tent): % eT____ % __e_Te % __T___ % eTeTe_ % T___T_ % _eT_e_ % problem(1,N,Puzzle,Rows,Cols) => N = 6, T = 1, Puzzle = [ [0, T, 0, 0, 0, 0], [0, 0, 0, 0, T, 0], [0, 0, T, 0, 0, 0], [0, T, 0, T, 0, 0], [T, 0, 0, 0, T, 0], [0, 0, T, 0, 0, 0] ], Rows = [1,2,0,3,0,2], Cols = [2,1,2,0,2,1]. % % From https://www.brainbashers.com/showtents.asp?date=1231&diff=Medium&size=16 % % Solution (T: tree, e: tent) % eT___eTe_e_e_eTe % _______T_T_T_TT_ % _eTe_T_Te___T_e_ % _T___e___Te_e___ % e_eT_____T____T_ % T____eTeTe_eT_e_ % e____________T__ % T_________Te_eTe % e_eT__e_Te______ % T__Te_T______e__ % Te____e__T_e_T_e % T____TT__e_T___T % e__e_e_e_T_Te__T % ___T___T_e_____e % T__e_eTe_T_____T % e__T_T___eTeTe_e % problem(2,N,Puzzle,Rows,Cols) => N = 16, T = 1, Puzzle = [ % 6 2 2 3 1 5 2 4 1 6 1 5 2 4 2 5 [0, T, 0, 0, 0, 0, T, 0, 0, 0, 0, 0, 0, 0, T, 0], % 7 [0, 0, 0, 0, 0, 0, 0, T, 0, T, 0, T, 0, T, T, 0], % 0 [0, 0, T, 0, 0, T, 0, T, 0, 0, 0, 0, T, 0, 0, 0], % 4 [0, T, 0, 0, 0, 0, 0, 0, 0, T, 0, 0, 0, 0, 0, 0], % 3 [0, 0, 0, T, 0, 0, 0, 0, 0, T, 0, 0, 0, 0, T, 0], % 2 [T, 0, 0, 0, 0, 0, T, 0, T, 0, 0, 0, T, 0, 0, 0], % 5 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, T, 0, 0], % 1 [T, 0, 0, 0, 0, 0, 0, 0, 0, 0, T, 0, 0, 0, T, 0], % 3 [0, 0, 0, T, 0, 0, 0, 0, T, 0, 0, 0, 0, 0, 0, 0], % 4 [T, 0, 0, T, 0, 0, T, 0, 0, 0, 0, 0, 0, 0, 0, 0], % 2 [T, 0, 0, 0, 0, 0, 0, 0, 0, T, 0, 0, 0, T, 0, 0], % 4 [T, 0, 0, 0, 0, T, T, 0, 0, 0, 0, T, 0, 0, 0, T], % 1 [0, 0, 0, 0, 0, 0, 0, 0, 0, T, 0, T, 0, 0, 0, T], % 5 [0, 0, 0, T, 0, 0, 0, T, 0, 0, 0, 0, 0, 0, 0, 0], % 2 [T, 0, 0, 0, 0, 0, T, 0, 0, T, 0, 0, 0, 0, 0, T], % 3 [0, 0, 0, T, 0, T, 0, 0, 0, 0, T, 0, T, 0, 0, 0] % 5 ], Rows = [7,0,4,3,2,5,1,3,4,2,4,1,5,2,3,5], Cols = [6,2,2,3,1,5,2,4,1,6,1,5,2,4,2,5].