/* 

  Checker puzzle in Picat.

  From http://mathoverflow.net/questions/1947/placing-checkers-with-some-restrictions
  Placing checkers with some restrictions
  """
  We are going to put n checkers on an (n x n) checkers board, 
   with the following restrictions:

  1) In each column there is EXACTLY one checker.
  
  2) For i=1,2,...,(n-1), the first i rows cannot have EXACTLY i checkers.
  
  The question is to count the number of ways to do so. I guess that the 
  answer is n^{n-1}, but I do not know how to prove it. Can anyone help?

  (If restriction 2) is removed, the answer is obviously n^n.)
  """
  

  Here is the result:
   n   #solutions
   --------------
   1        1
   2        2
   3        9
   4       64
   5      625  
   6     7776
   7   117649
   8  2097152
  
  which confirms the hypothesis:

  > [n^(n-1) | n<-[1..10]]
  [1,2,9,64,625,7776,117649,2097152,43046721,1000000000]

   for n = 3  there are 5 different patterns
    #  pattern
    1 [0, 0, 3]
    1 [0, 3, 0]
    1 [3, 0, 0]
    3 [0, 1, 2]
    3 [2, 1, 0]

  for n = 4 there are 14 different patterns
    1 [0, 0, 0, 4]
    1 [0, 0, 4, 0]
    1 [0, 4, 0, 0]
    1 [4, 0, 0, 0]
    4 [0, 0, 1, 3]
    4 [0, 1, 0, 3]
    4 [0, 1, 3, 0]
    4 [0, 3, 1, 0]
    4 [3, 0, 1, 0]
    4 [3, 1, 0, 0]
    6 [0, 0, 2, 2]
    6 [2, 2, 0, 0]
   12 [0, 1, 1, 2]
   12 [2, 1, 1, 0]


  for n = 5 there are  42 different patterns
      n = 6           132
      n = 7           429
      n = 8          1430 

  And this seems to be the Catalan numbers...
  http://en.wikipedia.org/wiki/Catalan_number
  
  1,2,5,14,42,132,429,...


  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 = 3,
  checker(N, X,SumRows),
  foreach(Row in X) println(Row) end,
  println(sumRows=SumRows),
  nl,
  fail,
  
  nl.

go => true.

%
% Number of solutions for certain N.
% (See above.)
%
go2 =>
  Sols = [],
  foreach(N in 1..8)
    garbage_collect(300_000_000),
    Count = count_all(checker(N,X,_SumRows)),
    Sols := Sols ++ [Count],
    println(N=Count)
  end,
  println(sols=Sols),
  nl.


%
% The different patterns of SumRows for different N.
% (See above.)
%
go3 =>
  garbage_collect(300_000_000),
  foreach(N in 1..8)
    println(n=N),
    Map = new_map(),
    All = find_all(SumRows,checker(N,_X,SumRows)),
    foreach(A in All)
      Map.put(A,Map.get(A,0)+1)
    end,
    % println(map=Map)
    if N <= 5 then
      foreach(Pattern in Map.keys.sort)
        println(Pattern=Map.get(Pattern))
      end
    end,
    println(numPatterns=Map.keys.len),
    nl
  end,
  
  nl.


checker(N, X,SumRows) =>

  X = new_array(N,N),
  X :: 0..1,
  
  SumRows = new_list(N),
  SumRows :: 0..N,

  % We are going to put n checkers on an (n x n) checkers board, 
  sum([X[I,J] : I in 1..N, J in 1..N]) #= N,

  % In each column there is EXACTLY one checker.
  foreach(J in 1..N) 
    sum([X[I,J] : I in 1..N]) #= 1
  end,

  % For i=1,2,...,(n-1), the first i rows cannot have EXACTLY i checkers.
  foreach(I in 1..N) 
    % number of checker on each row 
    SumRows[I] #= sum([X[I,J] : J in 1..N])
  end,

  foreach(I in 1..N-1) 
    sum([SumRows[J] : J in 1..I]) #!= I
  end,

  Vars = X.vars ++ SumRows,
  solve([],Vars).