/* 

  Crowded Chessboard puzzle in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles4.html puzzle nr 5
  Description  : The crowded board
  Source       : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
  """
  5. The Crowded Chessboard
  You are given a chessboard together with 8 queens, 8 rooks, 14 bishops, and 21 knights. The puzzle is to
  arrange the 51 pieces on the chessboard so that no queen shall attack another queen, no rook attack another
  rook, no bishop attack another bishop, and no knight attack another knight. No notice is to be taken of the
  intervention of pieces of another type from that under consideration - that is, two queens will be
  considered to attack one another although there may be, say, a rook, a bishop, and a knight between them.
  It is not difficult to dispose of each type of piece seperately; the difficulty comes in when you have to
  find room for all the arrangements on the board simultaneously. 

  (Dudeney 1917)
  """

  This model was inspired by the XPress Mosel model created by Martin Chlond:
  http://www.chlond.demon.co.uk/puzzles/sol4s5.html

  (And this is - in turn - a port from the MiniZinc model:
   http://www.hakank.org/minizinc/crowd.mzn )

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
import sat. % 59.3s
% import mip. % slower
% import cp.


main => go.

go =>
  Size = 8,
  Piece = 4, % 1 - Queen, 2 - Bishop, 3 - Knight, 4 - Rook
  % S = 1..Size+4,
  P = 1..Piece+4,
  R = 3..Size+2,  % real part of board
  % Note: The Mosel model defines P only for 1..4 but is 1..8 here
  N = [8,14,21,8,0,0,0,0],
  
  % decision variables 
  X = new_array(Size+4,Size+4,Piece+4), 
  X :: 0..1,


   % for the output
   Res = new_array(Size,Size),
   Res :: 0..4,

   Z #= sum([X[I,J,K] : I in R, J in R, K in P]),

   foreach(K in P) 
        sum([X[I,J,K] : I in R, J in R]) #= N[K]
   end,

   foreach(I in R,J in R) 
      sum([X[I,J,K] : K in P]) #<= 1
   end,

   % No queens attack each other
 
   foreach(I in R)
        sum([X[I,J,1] : J in R])  #<= 1
   end,
  
   foreach(J in R)
        sum([X[I,J,1] : I in R])  #<= 1     
   end,

   foreach (I in 2..Size+3)
           sum([X[K,I-K+1,1] : K in 1..I])  #<= 1
   end,

   foreach(J in 1..Size+3)
        sum([X[K,Size+4-K+J,1] : K in J..Size+4])  #<= 1  
   end,

   foreach(J in 1..Size+3)
       sum([X[K,J+K-1,1] : K in 1..Size-J+5])  #<= 1
   end,

   foreach(I in 2..Size+3)
        sum([X[K,K-I+1,1] : K in I..Size+4])  #<= 1
   end,

   % No bishops attack each other
 
   foreach(I in 2..Size+3)
        sum([X[K,I-K+1,2] : K in 1..I])  #<= 1
   end,

   foreach(J in 1..Size+3)
        sum([X[K,Size+4-K+J,2] : K in J..Size+4])  #<= 1
   end, 

   foreach(J in 1..Size+3)
        sum([ X[K,J+K-1,2] : K in 1..Size-J+5]) #<= 1
   end,

   foreach(I in 2..Size+3)
        sum([X[K,K-I+1,2] : K in I..Size+4]) #<= 1
   end,

   % No rooks attack each other
   foreach(I in R)
        sum([X[I,J,4] : J in 3..Size+2]) #<= 1
   end,
   foreach(J in R)
        sum([X[I,J,4] : I in 3..Size+2])  #<= 1
   end,

   %  a(i,j,3] = 0 if square {i,i} attacked by knight 
 
   foreach(I in R,J in R)
        X[I-2,J-1,3] + X[I-1,J-2,3] + X[I+1,J-2,3] + X[I+2,J-1,3] + 
        X[I+2,J+1,3] + X[I+1,J+2,3] + X[I-1,J+2,3] + X[I-2,I+1,3] + 99*X[I,J,3] #<= 99
   end,


   % Dummy squares not occupied 
    sum([X[I,J,K] : I in 1..Size+4,J in 1..Size+4,K in 1..4, 
                      (I < 3; I > Size+2; J < 3; J > Size+2)])  #=  0,

   % calculate res (the output)
   foreach(I in 1..Size, J in 1..Size)
      Res[I,J] #= sum([K*X[I+2,J+2,K] : K in P]) 
   end,

   % Vars = X.to_list() ++ Res.to_list() ++ [Z],  % 63s with sat
   % Vars = Res.to_list() ++ [Z],  % 68s with sat
   % Vars = [Z] ++ Res.to_list(),  % 59.9s with sat
   % Vars = [Z] ++ X.to_list() ++ Res.to_list(),  % 57.8s with sat
   Vars = [Z] ++ Res.to_list(), % 56.2s with sat

   solve($[min(Z), $report(printf("z=%w\n", Z))], Vars),

   % writeln(x=X),
   writeln(z=Z),

   foreach(Row in Res) writeln(Row) end,

   nl.