032: Maximum density still life

% 
% Maximum density still life in MiniZinc.
% 
% 
% CSPLib 032: http://www.csplib.org/prob/prob032
%
%
% This model 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
%
%
% Compare with the Comet model:
% http://www.hakank.org/comet/maximum_density_still_life_cp.co
%
% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

% include "globals.mzn"; 
int: size = 7; % to change

set of int: objFunctionBoardCoord      = 2..size+1;
set of int: checkConstraintsBoardCoord = 1..size+2;
set of int: augmentedBoardCoord        = 0..size+3;

% Search space: The set of all possible assignments of 0s (dead) and 1s (live) 
% to the cells of the board section. However, to be able to easily express 
% constraints on "boundary" cells, we take as search space the set of 0/1 
% boards of size n+4 by n+4: the actual stable pattern appears in the sub-board 
% defined by ignoring the first/last two rows/columns.
array[augmentedBoardCoord,augmentedBoardCoord] of var 0..1: grid;

var int: z = sum(r in objFunctionBoardCoord, c in objFunctionBoardCoord) (grid[r,c]);

% Objective function: Maximize the number of live cells in the sub-board defined 
% by ignoring the first/last two/ rows/columns.


% solve maximize z;
solve :: int_search(
        [grid[i,j] | i,j in augmentedBoardCoord], 
        smallest, 
        indomain_max, 
        complete) 
    maximize z;

constraint

  % C1: Cells in the first/last two rows/columns are all 0 (dead)
  forall(x in augmentedBoardCoord) (
    grid[0,x] = 0 /\
    grid[1,x] = 0 /\
    grid[size+2,x] = 0 /\  
    grid[size+3,x] = 0 /\
    grid[x,0] == 0 /\       
    grid[x,1] == 0 /\
    grid[x,size+2] = 0 /\  
    grid[x,size+3] = 0 
  )
  /\
  forall(r in checkConstraintsBoardCoord,c in checkConstraintsBoardCoord) (
    % 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
                      )
    )
  )
  
  /\
  % 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]
;


output [
  if j = 0 then "\n" else " " endif ++
    show(grid[i,j])
  | i,j in augmentedBoardCoord
];