July 2018 little math problem

[Albert Chan]

I revised zigzag.pi with better constraints

Code:

import cp.                  % Usage: picat zigzag.pi [Sides=4]
main => main(4).            % Default: 4-sided zigzag
main([Sides]) => main(to_integer(Sides)).
main( Sides ) => Sides > 2, (zigzag(Sides), fail; true).

zigzag(Sides) =>
  N = 2*Sides + 1,          % number of numbers (always Odd)
  A = new_list(N),          % unknown variables
  A :: 1..N,
  all_different(A),
  M = [N-1,N] ++ (1..N-2),  % head moved to back for speedup

  A[M[1]] #< A[M[2]],       % 2X solution by swap head pairs
  A[M[N-1]] #< A[M[N]],     % 2X solution by swap tail pairs
  A[M[3]] #< A[M[N-2]],     % 2X solution by flip the zigzag

  C = N + 1,                % C-complement Symmetry
  Center = C * 3 // 2,      % C-Complement Sum Center
  S #<= Center,             % Symmetry with slight over-count

  Total = N*(N+1) // 2,     % Speed-up with non-vertices constraint
  K = Sides//2 + 1,         % Remove as much vertices as possible
  (odd(Sides) ->            % For odd-Sided zigzag, no vertices left
   sum([A[M[I]]: I in N-3..-4..4]) #= Total - K*S ;
   sum([A[M[I]]: I in N-3..-4..4]) #= Total - K*S + A[M[3]]
  ),

  foreach(I in 1..2..N-4)   % All sides sum to S (tail side skipped)
    A[M[I]] + A[M[I+1]] + A[M[I+2]] #= S
  end,

  solve(A),
  writeln([A[I]: I in M]),

  % Add C-Complement Symmetry Solution
  S < Center, writeln([C-A[I]: I in M]).

For 10-sided zigzag, speed (vs. original) = 2.37X, or 137% faster (finished in 111 seconds)