/*

  Nickerson's variant of Langford's number problem in Picat.

  http://dialectrix.com/langford.html
  """
  Nickerson's Variant of Langford's Problem
  A variant of Langford's Problem has the second number of each k-pair occur in the kth place 
  after the first, so that there are k-1 other numbers between the two k's. The singular 
  variant solution for n=4 is 42324311. R. Nickerson proved this is possible whenever 
  n is of the form 4m or 4m+1. See Bibliography.

  Note the 1's are always together in the variant. [So the variant is like adding a 
  pair of 0's to the classic problem - no blocks between the two zeroes. Skolem variant?] 
  """


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

*/

import util.
import cp.

main => go.

go ?=>
    K = 4,
    printf("K: %d\n", K),
    time2(langford_nickerson(K, Solution, Position)),
    if nonvar(Solution) then
      printf("Solution: %w\n", Solution),
      printf("Position: %w\n", Position)
    end,
    fail,
    nl.

go => true.

%
% Get the first (if any) solutions for K in 2..40
%
go2 => 
    foreach(K in 2..40) 
       printf("K: %d\n", K),
       if time2(langford_nickerson(K, Solution, Position)) then
           if nonvar(Solution) then 
             printf("Solution: %w\n", Solution),
             printf("Position: %w\n", Position)
           else 
             printf("No solution\n")
           end,
          printf("\n")
       end
    end.

% Count the number of solutions
go3 => 
    Map = get_global_map(),
    foreach(K in 2..40) 
       println(k=K),
       Map.put(count,0),
       ((langford_nickerson(K, Solution, Position), Map.put(count, Map.get(count)+1), fail) ; true),
       printf("K: %d = %d solutions\n", K, Map.get(count))
    end.


 
langford_nickerson(K, Solution, Position) =>
  K2 = 2*K,
  Position = new_list(K2),
  Position :: 1..K2,

  Solution = new_list(K2),
  Solution :: 1..K,

  % all_different(Position),
  all_distinct(Position),

  foreach(I in 1..K)
      Position[K+I] #= Position[I] + I,
      element(Position[I],Solution,I),  
      element(Position[K+I],Solution,I)
  end,

  % symmetry breaking:
  Solution[1] #< Solution[K2],

  Vars = Solution ++ Position,
  % Vars = Position ++ Solution,
  solve([ffc,split], Vars).