Download
/*
Maximum density still life in Picat.
CSPLib 032: http://www.csplib.org/Problems/prob032
This model (or rather my earlier MiniZinc and Comet models) was
inspired by the OPL model from
Toni Mancini, Davide Micaletto, Fabio Patrizi, Marco Cadoli:
"Evaluating ASP and commercial solvers on the CSPLib"
http://www.dis.uniroma1.it/~tmancini/index.php?problemid=032&solver=OPL&spec=BASE&currItem=research.publications.webappendices.csplib2x.problemDetails#listing
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
import cp.
main => go.
go =>
Size = 6,
life(Size, Grid, Z),
print_grid(Grid),
writeln(z=Z),
nl.
print_grid(Grid) =>
foreach(G in Grid)
foreach(V in G) printf("%d", V) end, nl
end.
life(Size, Grid, Z) =>
GridSize = Size+4,
Grid = new_array(GridSize,GridSize),
Vars = vars(Grid),
Vars :: 0..1,
Z #= sum(Vars),
% C1: Cells in the first/last two rows/columns are all 0 (dead)
foreach(X in 1..GridSize)
Grid[1,X] #= 0,
Grid[2,X] #= 0,
Grid[Size+3,X] #= 0,
Grid[Size+4,X] #= 0,
Grid[X,1] #= 0,
Grid[X,2] #= 0,
Grid[X,Size+3] #= 0,
Grid[X,Size+4] #= 0
end,
foreach(R in 2..Size+3, C in 2..Size+3)
% C2: Each cell of the board (except those of the first/last row/column)
% that has exactly three live neighbors is alive.
% Together with constraint C1, this implies that cells in the
% second/last-but-one row/column cannot have three live neighbors.
( ( Grid[R-1,C-1] + Grid[R-1,C] + Grid[R-1,C+1] +
Grid[R,C-1] + Grid[R,C+1] +
Grid[R+1,C-1] + Grid[R+1,C] + Grid[R+1,C+1]
) #= 3
) #=> (Grid[R,C] #= 1)
,
% C3: Each live cell must have 2 or 3 live neighbors (cells of the first/last
% row/column may be ignored by this constraint)
(Grid[R,C] #= 1) #=>
2 #=<
( Grid[R-1,C-1] + Grid[R-1,C] + Grid[R-1,C+1] +
Grid[R,C-1] + Grid[R,C+1] +
Grid[R+1,C-1] + Grid[R+1,C] + Grid[R+1,C+1]
)
#/\
( Grid[R-1,C-1] + Grid[R-1,C] + Grid[R-1,C+1] +
Grid[R,C-1] + Grid[R,C+1] +
Grid[R+1,C-1] + Grid[R+1,C] + Grid[R+1,C+1]
) #=< 3
end,
% SBSO: Symmetry-breaking by selective ordering
% The assignment is forced to respect an ordering on the values that occur in corner entries
% of the board. In particular:
% - if the NW-corner cell is dead, the SE-corner cell
% must be dead too
% - if the NE-corner cell is dead, the SW-corner cell must be dead too
%
Grid[2,2] #>= Grid[Size+1,Size+1],
Grid[2,Size+1] #>= Grid[Size+1,2],
solve([$max(Z),min,updown], Vars).