/* 

  Stamp licking puzzle in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles4.html, puzzle nr. 4.
  Description  : The gentle art of stamp-licking
  Source       : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

  """
  The Insurance Act is a most prolific source of entertaining puzzles, particularly 
  entertaining if you happen to be among the exempt. One's initiation into the 
  gentle art of stamp-licking suggests the following little poser: 
  
  If you have a card divided into sixteen spaces (4 × 4), and are provided with 
  plenty of stamps of the values 1d., 2d., 3d., 4d., and 5d., what is the greatest 
  value that you can stick on the card if the Chancellor of the Exchequer 
  forbids you to place any stamp in a straight line (that is, horizontally, 
  vertically, or diagonally) with another stamp of similar value? Of course, only 
  one stamp can be affixed in a space. The reader will probably find, when he 
  sees the solution, that, like the stamps themselves, he is licked 
  He will most likely be twopence short of the maximum. A friend asked the Post 
  Office how it was to be done; but they sent him to the Customs and Excise 
  officer, who sent him to the Insurance Commissioners, who sent him to an 
  approved society, who profanely sent him—but no matter.
  """

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

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

*/


% import mip. % 14.6s
import cp. % 0.2s
% import sat. % 5.2s


main => go.


go =>
  Size = 4,
  Stamp = 5,

  X = new_array(Size,Size,Stamp),
  X :: 0..1,
  A = new_array(Size,Size,Stamp),
  A :: 0..1,
  Y = new_array(Size,Size), % the result
  Y :: 1..Stamp,
  
  Z #= sum([K*X[I,J,K] : I in 1..Size,J in 1..Size, K in 1..Stamp]),

  foreach(I in 1..Size,J in 1..Size) 
     sum([X[I,J,K] : K in 1..Stamp]) #=< 1
  end,


  % a(i,j,k) = 1 if stamp on square (i,j) is in line with similar stamp
  foreach(I in 1..Size,J in 1..Size,K in 1..Stamp)
    sum([X[M,M-I+J,K] : M in 1..Size, M != I, M-I+J >= 1, M-I+J <= Size]) +
    sum([X[M,I+J-M,K] : M in 1..Size, M != I, I+J-M >= 1, I+J-M <= Size])+
    sum([X[M,J,K] : M in 1..Size, M != I]) + 
    sum([X[I,M,K] : M in 1..Size, M != J])  #<= 99*A[I,J,K]
  end,

  % square not both occupied and attacked by same stamp value
  foreach(I in 1..Size,J in 1..Size,K in 1..Stamp) 
        A[I,J,K]+X[I,J,K] #=< 1
  end,

  % calculate the output matrix
  foreach(I in 1..Size,J in 1..Size)
    Y[I,J] #= sum([(K*X[I,J,K]) : K in 1..Stamp]) 
  end,

  solve($[ffd,updown,max(Z)], X ++ A ++ Y),

  println(z=Z),
  println("Y:"),
  foreach(Row in Y)
    println(Row.to_list())
  end,
  
  nl.