/* 

  The Athletics Committee problem in Picat.

  Puzzles that Solve Themselves — Peter Winkler
  https://www.youtube.com/watch?v=RQtCRpWvVuw&t=6s
  @ 2:03ff
  """
  Every professor wants to be on the Athlectics Committee -- free
  tickets to your favorite event!
  
  To keep the committee from becoming too cliquish, the college forbids
  anyone from serving who has 3 or more friends on the committee.
  
  That's OK, because if you have 3 or more friends on the committee, you
  get free tickets to your favorite event!

  Can the committee be chosen so that no one on it has 3 friends on the
  committee, but everyone _off_ the committee has 3 friends on it?
  """
  
  Assumptions: 
   - friends is a symmetric relation (i is a friend of j -> j is a friend of i)
   - a person is not a friend of him/herself
   - the last constraint means that everyone _off_ the committee has _exactly 3 friends
     in it.
   - there must be at least one person in the committee and one person outside it

  Number of solutions:
  1 =           0
  2 =           0
  3 =           0
  4 =          32
  5 =         980
  6 =       36140
  7 =     2075360
  8 =   206866912
  9 = 37299417288

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

*/


import cp.


main => go.


go ?=>
  N = 4,
  committee(N, Friends, X),
  println(x=X),
  foreach(Row in Friends)
    println(Row)
  end,
  nl,
  fail,
  nl.


go => true.

go2 => 
  foreach(N in 1..20)
    garbage_collect(300_000_000),
    (committee(N, _Friends, X), println(N=X)) ; println(N=nope)
  end,
  nl.


go3 => 
  foreach(N in 1..20)
    Count = count_all(committee(N, _Friends, _X)),
    println(N=Count)
  end,
  nl.


committee(N, Friends, X) =>
  Friends = new_array(N,N),
  Friends :: 0..1,
  
  X = new_list(N),
  X :: 0..1,

  foreach(I in 1..N)
    X[I] #= 1 #=> sum([Friends[I,J]*X[J] : J in 1..N]) #< 3,
    X[I] #= 0 #=> sum([Friends[I,J]*X[J] : J in 1..N]) #= 3,
    Friends[I,I] #= 0, % a person is not a friend of him/selfself
    % symmetry of friends
    foreach(J in 1..N)
      Friends[I,J] #= Friends[J,I]
    end
  end,
  sum(X) #> 0, % at least one person is on the committee
  sum([X[I] #= 0 : I in 1..N]) #> 0, % at least one person is outside the committee

  % symmetry breaking
  % increasing(X), 

  Vars = X ++ Friends.vars(),
  solve($[ff,split], Vars).