/* 

  Latin spiral in Picat.

  For an NxN matrix, ensure that it's both a latin square as well
  as a spiral matrix with increasing N chunks for the values 1..M (for some M,>= 3).

  Here are the 4 solutions for N=5 and m=3, i.e. the 5-chunks of the spiral 
  should have 1..3 as increasing values:

   [1,2,4,5,3]
   [2,5,3,4,1]
   [4,1,2,3,5]
   [3,4,5,1,2]
   [5,3,1,2,4]

   [1,2,4,5,3]
   [2,5,3,4,1]
   [5,1,2,3,4]
   [3,4,5,1,2]
   [4,3,1,2,5]

   [1,2,5,4,3]
   [2,4,3,5,1]
   [4,1,2,3,5]
   [3,5,4,1,2]
   [5,3,1,2,4]

   [1,2,5,4,3]
   [2,4,3,5,1]
   [5,1,2,3,4]
   [3,5,4,1,2]
   [4,3,1,2,5]


  Here's the spiral of a 5x5 matrix (see go3/0):
    1  2  3  4  5
   16 17 18 19  6
   15 24 25 20  7
   14 23 22 21  8
   13 12 11 10  9


  Here are three solutions of the 7104 solutions for N=6 and N=3:

   [1,2,4,5,6,3]
   [4,5,2,6,3,1]
   [2,6,1,3,4,5]
   [3,1,6,4,5,2]
   [5,4,3,2,1,6]
   [6,3,5,1,2,4]

   [1,2,4,5,6,3]
   [4,5,2,6,3,1]
   [2,6,1,3,4,5]
   [3,1,6,4,5,2]
   [6,3,5,2,1,4]
   [5,4,3,1,2,6]

   [1,2,4,5,6,3]
   [4,5,2,6,3,1]
   [2,6,1,3,4,5]
   [6,1,3,4,5,2]
   [3,4,5,2,1,6]
   [5,3,6,1,2,4]


  The spiral for N=6 is
    1  2  3  4  5  6
   20 21 22 23 24  7
   19 32 33 34 25  8
   18 31 36 35 26  9
   17 30 29 28 27 10
   16 15 14 13 12 11

  According to this model, there are solutions for N = 8..48 and M in N..-1..3.


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

*/

import util.
import sat.

main => go.

/*
  Print one solution for each N and M:

  [n = 5,m = 3]
  [1,2,4,5,3]
  [2,5,3,4,1]
  [5,1,2,3,4]
  [3,4,5,1,2]
  [4,3,1,2,5]

  n = 6
  [n = 6,m = 3]
  [6,1,5,2,4,3]
  [2,6,4,5,3,1]
  [1,5,2,3,6,4]
  [3,2,6,4,1,5]
  [4,3,1,6,5,2]
  [5,4,3,1,2,6]

  n = 7
  [n = 7,m = 4]
  [7,5,6,1,2,3,4]
  [5,2,3,7,4,1,6]
  [2,4,5,6,3,7,1]
  [1,3,7,4,6,5,2]
  [6,1,4,3,7,2,5]
  [4,7,1,2,5,6,3]
  [3,6,2,5,1,4,7]


 Use sat for this.

*/
go =>
  nolog,
  member(N,5..48),
  println(n=N),
  member(M,N..-1..N-3),
  M >= 3,

  once(latin_spiral(N,M, X)),
  println([n=N,m=M]),
  foreach(Row in X)
    println(Row.to_list)
  end,
  nl,
  fail,
  nl.

/*
  
  Count the number of solutions

  [n = 5,m = 3,c = 4]
  [n = 6,m = 3,c = 7104]
  [n = 7,m = 4,c = ?]

  Use cp for this.
*/
go2 =>
  nolog,
  member(N,5..20),
  println(n=N),
  member(M,N..-1..N-3),
  M >= 3,

  if C = count_all(latin_spiral(N,M, X)), C > 0 then
    println([n=N,m=M,c=C])
  end,
  fail,
  nl.

/*
  Print the spiral order

  See spiral_order.pi

*/
go3 =>
  % N = 5,
  N = 6,
  X = (1..N*N).chunks_of(N),
  print_spiral(X),
  nl.
  

latin_spiral(N,M, X) =>

  X = new_array(N,N),
  X :: 1..N,
  
  foreach(I in 1..N)
    all_different([X[I,J] : J in 1..N]),
    all_different([X[J,I] : J in 1..N])
  end,

  % Get the spiral of X and split it into N chunks of N elements.
  % The values 1..M should be increasing 
  XSpiralChunks = spiralOrder(X.array_matrix_to_list_matrix).chunks_of(N),

  foreach(S in XSpiralChunks)
    increasing_values(S,1..M)
  end,

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

%
% increasing_values(X, Values)
% Ensure that values that are in Values should be increasing in X.
%
% It's a generalization (and the oppsite of) the
% global constraint increasing_except_0(X).
% 
% See increasing_values.pi
%
increasing_values(X,Values) =>
  Len = X.length,
  foreach(I in 1..Len, J in 1..Len, I < J)
    ( sum( [X[I] #= V : V in Values] ) #> 0 #/\ sum([X[J] #= V : V in Values]) #> 0) #=> X[I] #=< X[J] 
  end.


%
% Return the spiral order of X.
% Adapted from https://www.enjoyalgorithms.com/blog/print-matrix-in-spiral-order
%
% See spiral_order.pi
% 
spiralOrder(X) = Spiral =>
  M = X.len,
  N = X[1].len,
  RowStart = 1,
  RowEnd = M,
  ColStart = 1,
  ColEnd = N,
  Spiral = [],
  while (RowStart <= RowEnd, ColStart <= ColEnd)
    foreach(I in ColStart..ColEnd)
      Spiral := Spiral ++ [X[RowStart,I]]
    end,
    RowStart := RowStart + 1,
    foreach(I in RowStart..RowEnd)
      Spiral := Spiral ++ [X[I,ColEnd]]
    end,
    ColEnd := ColEnd - 1,
    if RowStart <= RowEnd then
      foreach(I in ColEnd..-1..ColStart)
        Spiral := Spiral ++ [X[RowEnd,I]]
      end,
      RowEnd := RowEnd - 1
    end,
    if ColStart <= ColEnd then
      foreach(I in RowEnd..-1..RowStart)
        Spiral := Spiral ++ [X[I,ColStart]]      
      end,
      ColStart := ColStart + 1
    end
  end.

% See spiral_order.pi
print_spiral(X) =>
  N = X.len,
  SpiralOrder = spiralOrder(X),
  println(spiralOrder=SpiralOrder),
  M = new_array(N,N),
  foreach({V,K} in zip(SpiralOrder,1..N*N))
    [I2,J2] = [[I,J] : I in 1..N, J in 1..N, X[I,J] == V].first,
    M[I2,J2] := K
  end,
  Format = "% " ++ ((N*N).to_string.len+1).to_string ++ "d", 
  foreach(I in 1..N)
    foreach(J in 1..N)
      printf(Format,M[I,J])
    end,
    nl
  end,
  nl.