/* 

  Takuzu grid puzzle in Picat.

  From http://en.wikipedia.org/wiki/Takuzu
  """
  Takuzu is a logic-based number placement puzzle. The objective is to fill a 
  (usually 10x10) grid with 1s and 0s, where there is an equal number of 1s and 
  0s in each row and column and no more than two of either number adjacent to 
  each other. Additionally, there can be no identical rows or columns. 
  """

  Compare with binero.pi for another approach


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

*/

import cp.

main => go.

go =>
  member(P,1..4),
  println(problem=P),
  problem(P,N,X),
  takuzu(N,X),
  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,
  nl.


takuzu(N,X) =>

  M = N div 2,
  X :: 0..1,

  % equal number of 0s and 1s in each row and column
  foreach(I in 1..N) 
     sum([X[I,J] #= 0 : J in 1..N]) #= M,
     sum([X[J,I] #= 0 : J in 1..N]) #= M
  end,

  % no more than two of the same values adjacent
  foreach(I in 2..N-1)
    foreach(J in 1..N) 
      (X[I-1,J] #!= X[I,J] #\/ X[I,J] #!= X[I+1,J]),
      (X[J, I-1] #!= X[J,I] #\/ X[J,I] #!= X[J,I+1]) 
    end
  end,

  % no identical row or column
  foreach(I in 1..N, J in I+1..N)
    sum([X[I,K] #!= X[J,K] : K in 1..N]) #>= 1,
    sum([X[K,I] #!= X[K,J] : K in 1..N]) #>= 1
  end,

  solve(X).


%
% data
%
problem(1,N,Problem) => 
  N = 4,
  Problem = [[_,1,_,0],
             [_,_,0,_],
             [_,0,_,_],
             [1,1,_,0]].

%
% Problem instance from the Scampi data/binero1.txt
%
problem(2,N,Problem) => 
  N = 10,
  Problem = [[0,_,1,1,_,_,_,_,_,1],
             [_,_,1,_,_,_,_,0,_,0],
             [_,0,_,_,1,_,1,_,1,_],
             [_,1,_,_,_,_,_,_,_,_],
             [1,_,0,_,_,1,_,_,_,_],
             [_,0,_,_,0,_,_,_,1,1],
             [_,_,_,1,_,_,_,_,_,1],
             [0,_,_,1,_,1,_,0,_,_],
             [_,_,0,_,_,_,_,_,_,_],
             [1,1,_,_,_,_,1,1,_,0]].

%
% Problem instance from the Scampi problem/binero2.txt
%
problem(3,N,Problem) => 
  N = 10,
  Problem = [[_,0,_,0,_,_,_,1,_,_],
             [1,_,_,_,1,_,_,_,_,_],
             [_,0,_,0,_,_,_,_,_,_],
             [_,_,1,_,_,1,_,_,0,_],
             [_,_,_,0,_,_,_,1,_,_],
             [1,_,_,0,_,0,_,_,_,_],
             [_,_,1,_,_,_,_,0,_,0],
             [_,_,0,1,_,_,_,_,1,_],
             [1,_,_,_,_,_,0,_,_,_],
             [1,_,0,_,_,_,_,_,_,1]].


%
% Problem from http://www.cross-plus-a.com/puzzles.htm#Binairo
%
problem(4,N,Problem) =>
  N = 10,
  Problem = [[0,_,_,_,_,_,_,_,_,_],
             [_,_,1,_,_,_,1,1,_,_],
             [_,1,_,_,_,_,_,_,0,_],
             [_,_,_,0,_,0,_,_,_,_],
             [_,_,_,_,_,_,_,_,_,_],
             [0,_,_,_,_,_,_,1,_,0],
             [_,1,_,1,_,_,_,_,_,_],
             [0,_,_,_,0,0,_,1,_,_],
             [1,_,_,_,_,_,_,_,_,_],
             [_,1,_,1,1,_,_,_,_,0]].