/*

  Young tableaux (StackOverflow question) in Picat.

  See 
  http://mathworld.wolfram.com/YoungTableau.html
  and
  http://en.wikipedia.org/wiki/Young_tableau
  """
  The partitions of 4 are
   {4}, {3,1}, {2,2}, {2,1,1}, {1,1,1,1}
 
  And the corresponding standard Young tableaux are:
 
  1.   1 2 3 4
 
  2.   1 2 3         1 2 4    1 3 4
       4             3        2
 
  3.   1 2           1 3
       3 4           2 4
 
  4    1 2           1 3      1 4 
       3             2        2 
       4             4        3
 
  5.   1
       2
       3
       4
  """  

  This Stack Overflow question has some related questions
  "Young tableaux in C"
  http://stackoverflow.com/questions/15705001/young-tableaux-in-c
  """
  Consider a [6,3,2,1,1,1] Ferrers diagram:
  1) If 6 is fixed on the 6th box of the 1st row and 11 is fixed in the 
     last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?
  
  2) If 7 is fixed on the 6th box of the 1st row and 11 is fixed in the 
     last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?
  
  3) If 8 is fixed on the 6th box of the 1st row and 11 is fixed in 
     the last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?"
  """

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

*/

import util.
import cp.

main => go.

/*
  1) If 6 is fixed on the 6th box of the 1st row and 11 is fixed in the 
     last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?

  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  3  4  5  6 
    7 12 14 
    8 13 
    9 
   10 
   11 
        
  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  3  4  5  6 
    7 12 13 
    8 14 
    9 
   10 
   11 
        
It was 2 solutions.

*/
go =>
    check(6).

/*
  2) If 7 is fixed on the 6th box of the 1st row and 11 is fixed in the 
     last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?
     Answer: There are 10 such solutions

  Here are the first 2 solutions:

  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  3  5  6  7 
    4 12 14 
    8 13 
    9 
   10 
   11 
        
  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  3  5  6  7 
    4 12 13 
    8 14 
    9 
   10 
   11 
 
*/
go2 =>
    check(7).

/*
  3) If 8 is fixed on the 6th box of the 1st row and 11 is fixed in 
     the last box of the 1st column, in how many ways can you complete the 
     diagram in a standard way?"
     Answer: There are 30 such solutions

  Here are the first 2 solutions:

  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  5  6  7  8 
    3 12 14 
    4 13 
    9 
   10 
   11 
        
  p = [6,3,2,1,1,1,0,0,0,0,0,0,0,0]
    1  2  5  6  7  8 
    3 12 13 
    4 14 
    9 
   10 
   11 

*/
go3 =>
    check(8).


% Check the specific X[1,6].
check(S) => 
    N = 14,
    P = [6,3,2,1,1,1,0,0,0,0,0,0,0,0],
    X = new_array(N,N),
    X :: 1..N+1,
    X[1,6] #= S,
    L = findall(_, young_tableaux(N,X,P,1)),
    printf("It was %d solutions.\n\n", L.length).


%
% Ensure that all values in Xs are different (if they are not N).
% 
alldifferent_except_N(Xs,N) =>
    foreach(I in 1..Xs.length, J in 1..I-1)
         (Xs[I] #!= N #/\ Xs[J] #!= N) #=> (Xs[I] #!= Xs[J])
    end.


young_tableaux(N,X,P,Print) =>

    printf("Young tableaux and partitions of order %d\n", N),
  
    % for count and labeling
    Vars = array_matrix_to_list(X),

    % the partition structure
    % P = new_list(N),
    P :: 0..N+1,

    % 1..N is used exactly once (N+1 may be used many times)
    foreach(I in 1..N)
      1 #= count(I, Vars)
    end, 

    X[1,1] #= 1,
    
    % all rows and columns should be ordered
    foreach(I in 1..N)
        increasing([X[I,J] : J in 1..N]), % rows
        increasing([X[J,I] : J in 1..N])  % columns
    end,

    % calculate the structure (the partition)
    foreach(I in 1..N) P[I] #= sum([ (X[I,J] #=< N)  : J in 1..N]) end,

    % P should be ordered
    decreasing(P),
    N #= sum(P),

    % Extra constraint:
    % Ensure that 11 is the last box in first column
    % (and the rest of the column is N+1)
    sum([X[J,1] #= 11 #/\ sum([X[K,1] #= N+1 : K in J+1..N]) #= N-J : J in 1..N]) #= 1,

    Vars2 = X.vars ++ P,
    solve([degree,updown],Vars2),
    if Print == 1 then
         println(p=P),
         pretty_print(X)
    end.


pretty_print(X) =>
    N = X.length,
    foreach(I in 1..N)
       foreach(J in 1..N)
            XIJ = X[I,J],
            if XIJ =< N then
               printf("%3d", XIJ)
            end
       end,
       printf(" "),
       % don't show "empty" lines
       if X[I,1] =< N then printf("\n") end
    end,
    printf("\n").