July 2018 little math problem

[Albert Chan]

(07-26-2018 03:42 AM)Thomas Klemm Wrote:  

(07-26-2018 12:16 AM)Albert Chan Wrote:  If using computer is allowed, I would use Picat Programming Language

Interesting. Never heard of that language.

Picat is a declarative language, based on B-Prolog.
All you need is to describe the problem, and it take care of the rest.

Using symmetry, sum constraint, the program now run much faster.
Picat solved a 9-sided zigzag under 2 minutes: 33452 * 8 = 267616 solutions.

If result saved to file, Picat only take 51 seconds.

My computer pre-dated Win-XP, so is not fast (I later upgraded Win-XP on it)
My guess is Picat does not go brute force by visiting all permutations ...

Code:

import cp.                  % zigzag9.pi, all 9 sides sum to same S
main => go, fail; true.
go => Vars = [A1, A2, A3, A4, A5, A6, A7, A8, A9, A10,
              A11, A12, A13, A14, A15, A16, A17, A18, A19],
      Vars :: 1..19,        % zigzag with 9 sides
      Total := 19 * 10,     % sum(Vars)
      all_different(Vars),
      
      A1 #< A2,             % 2X solutions by swap head pairs
      A18 #< A19,           % 2X solutions by swap tail pairs
      A3 #< A17,            % 2X solutions by flip the zigzag
    
      % sum of below equations, speed up by tightten constraint on S
      Total + A3 + A5 + A7 + A9 + A11 + A13 + A15 + A17 #= 9*S,
      
      A1 + A2 + A3 #= S,
      A5 + A4 + A3 #= S,
      A5 + A6 + A7 #= S,
      A9 + A8 + A7 #= S,
      A9 + A10 + A11 #= S,
      A13 + A12 + A11 #= S,
      A13 + A14 + A15 #= S,
      A17 + A16 + A15 #= S,
      A17 + A18 + A19 #= S,
      solve(Vars),
      writeln(Vars).

% each solution is actually 8 (head swap, tail swap, flipping zigzag)
% this should be the first solution (side sum to 30)
%
% [1,10,19,5,6,13,11,17,2,16,12,14,4,18,8,15,7,3,20,9]

Edit:
Re-reading Thomas last post. My code had exactly the same idea.
Symmetry reduce the problem to one eighth its size ...