/* 

  Global constraint symmetric in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Csymmetric.html
  """
  Consider a digraph G described by the NODES collection. Select a subset of arcs 
  of G so that the corresponding graph is symmetric (i.e., if there is an arc from 
  i to j, there is also an arc from j to i).
  
  Example
    (
    <
     index-1 succ-{1,2,3},
     index-2 succ-{1,3}​,
     index-3 succ-{1,2}​,
     index-4 succ-{5,6}​,
     index-5 succ-{4},
     index-6 succ-{4}
     >
     )
      The symmetric constraint holds since the NODES collection depicts a symmetric graph.
  """

  Note: This constraint is set-based. Since Picat doesn't support constraint-based
  set this is translated to an 0/1-based matrix constraint.

  Number of solutions:
  1 = 2
  2 = 8
  3 = 64
  4 = 1024
  5 = 32768
  6 = 2097152
  7 = 268435456
  8 = 68719476736

  2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736
  OEIS: It's one of 
  - https://oeis.org/A006125 
    "a(n) = 2^(n*(n-1)/2)."
  - https://oeis.org/A139685 
    "Number of n X n symmetric binary matrices with no row sum greater than 9."
  - https://oeis.org/A139684
   "Number of n X n symmetric binary matrices with no row sum greater than 8."

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

*/

import cp.

main => go.

/*

  data(1,X):
  {1,1,1,0,0,0}
  {1,0,1,0,0,0}
  {1,1,0,0,0,0}
  {0,0,0,0,1,1}
  {0,0,0,1,0,0}
  {0,0,0,1,0,0}

  data(2,X):
 {1,1,1,0,0,0}
 {1,0,1,0,0,0}
 {1,1,0,0,0,0}
 {0,0,0,0,1,1}
 {0,0,0,1,0,0}
 {0,0,0,1,0,0}

 {1,1,1,0,0,0}
 {1,0,1,0,0,0}
 {1,1,0,0,0,0}
 {0,0,0,1,1,1}
 {0,0,0,1,0,0}
 {0,0,0,1,0,0}


*/
go =>
  N = 6,
  
  X = new_array(N,N),
  X :: 0..1,
  
  % data(1,X), % checking the example
  data(2,X), % 

  symmetric(X),

  solve(X.vars),

  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,

  nl.

go2 =>
  member(N,1..10),
  X = new_array(N,N),
  X :: 0..1,
  Count = count_all((symmetric(X),solve(X))),
  println(N=Count),
  fail,
  nl.

symmetric(X) =>
  N = X.len,
  foreach(I in 1..N, J in 1..N, I != J)
    X[I,J] #= 1 #<=> X[J,I] #= 1
  end.

/*
 From the example:
  1-{1,2,3},
  2-{1,3},
  3-{1,2},
  4-{5,6},
  5-{4},
  6-{4}
*/
data(1,M) =>
  M = {{1,1,1,0,0,0},
       {1,0,1,0,0,0},
       {1,1,0,0,0,0},
       {0,0,0,0,1,1},
       {0,0,0,1,0,0},
       {0,0,0,1,0,0}}.

% Same as above but with an unknown row
data(2,M) =>
  M = {{1,1,1,0,0,0},
       {1,0,1,0,0,0},
       {1,1,0,0,0,0},
       {_,_,_,_,_,_}, % unknown row
       {0,0,0,1,0,0},
       {0,0,0,1,0,0}}.