/* 

  Nine barrels puzzle (Dudeney) in Picat.

  """
  In how many different ways may these nine barrels be arranged in three
  tiers of three so that no barrel shall have a smaller number than its own
  below it or to the right of it? The first correct arrangement that will occur
  to you is 1 2 3 at the top, then 4 5 6 in the second row, and 7 8 9 at the bottom, 
  and my sketch gives a second arrangement. How many are there altogether?

    [
     1 2 3       1 3 6
     4 5 6       2 5 7
     7 8 9       4 8 9
    ]

  """


  This is puzzle #138 from Dudeney's "536 Puzzles and Curious Problems".

  For N=9 there is 42 solutions. Here are some of them:
    {1,2,3}
    {4,5,6}
    {7,8,9}

    {1,2,3}
    {4,5,7}
    {6,8,9}

    {1,2,3}
    {4,5,8}
    {6,7,9}

    {1,2,3}
    {4,6,7}
    {5,8,9}

  


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

*/

import util.
import cp.

main => go.

go ?=>
  N = 9, % N barrels
  n_barrels(N,X),
  foreach(Row in X)
    println(Row)
  end,
  nl,
  fail,

  nl.

go => true.

%
% How many solutions are there for different NxN square?
% We only test square numbers (N = M*M).

% N   #sols
% --------
% 1       1
% 4       2
% 9      42
% 16  24024
%
% This is - of course - the number of N x N Young tableaux
% https://oeis.org/A039622:
% 1, 1, 2, 42, 24024, 701149020, 1671643033734960, 475073684264389879228560
%
% Cf young_tableuax.pi 
% 
go2 ?=>
  foreach(N in 1..4)
    NN = N*N,
    Count = count_all(n_barrels(NN,_X)),
    println(NN=Count)
  end,
  nl.
go2 => true.

%
% Solve the general version of Nine Barrels puzzle
%
n_barrels(N,X) =>

  M = ceiling(sqrt(N)),

  X = new_array(M,M),
  X :: 1..N,

  all_different(X.vars),

  foreach(I in 1..M)
    increasing_strict(X[I]),
    increasing_strict([X[J,I] : J in 1..M])
  end,

  solve($[ff,split],X).
  

lex2(X) =>
  Len = X[1].length,
  foreach(I in 2..X.length) 
     lex_lt(X[I-1], X[I])
   end.