July 2018 little math problem

[pier4r]

I should really collect all those little problems in one place :/

The problem should be solved ideally with pen and paper. Of course computing devices are allowed as last resort.

One has the numbers 1,2,3,4,5,6,7,8,9 and should arrange them in the following position without repetition.

Code:


a b c
    d
    e f g
        h
        i

The arrangement should be such that the four sides will have numbers that summed together, will produce the same value.

What are the arrangements? How many are there? Of course would be nice to know the way you picked to solve the problem.

Code:


you can give your answer

using spoilers like this




























RPL! RPL! RPL!

[Voldemar]

Code:


















 9 3 1
      8
      4 7 2
           6
           5

[Thomas Klemm]

I just used brute force.

Code:

Spoiler alert!










a b c d e f g h i | ∑
------------------+---
3 9 1 8 4 7 2 5 6 | 13
5 6 2 7 4 8 1 3 9 | 13
6 7 1 5 8 4 2 3 9 | 14
5 8 1 6 7 4 3 2 9 | 14
3 9 2 4 8 5 1 6 7 | 14
4 8 2 9 3 5 6 1 7 | 14
2 9 3 4 7 6 1 5 8 | 14
1 9 4 8 2 7 5 3 6 | 14
2 8 4 9 1 7 6 3 5 | 14
3 6 5 7 2 8 4 1 9 | 14
1 7 6 5 3 9 2 4 8 | 14
3 5 6 7 1 9 4 2 8 | 14
5 7 4 3 9 1 6 2 8 | 16
3 9 4 5 7 1 8 2 6 | 16
4 7 5 3 8 2 6 1 9 | 16
2 8 6 1 9 3 4 5 7 | 16
1 9 6 2 8 3 5 4 7 | 16
1 8 7 6 3 4 9 2 5 | 16
2 6 8 1 7 5 4 3 9 | 16
1 7 8 6 2 5 9 3 4 | 16
2 5 9 4 3 6 7 1 8 | 16
3 4 9 5 2 6 8 1 7 | 16
4 5 8 3 6 2 9 1 7 | 17
1 7 9 2 6 3 8 4 5 | 17

These are 24 solutions.
But we can swap a and b and swap h and i.
This leads to a total of 4*24 = 96 solutions.

Edit: Just noticed that we can mirror a solution.
Thus these are the 12 fundamental solutions with c < g:

a b c d e f g h i | ∑
------------------+---
3 9 1 8 4 7 2 5 6 | 13
2 8 4 9 1 7 6 3 5 | 14
1 9 4 8 2 7 5 3 6 | 14
4 8 2 9 3 5 6 1 7 | 14
5 8 1 6 7 4 3 2 9 | 14
6 7 1 5 8 4 2 3 9 | 14
1 7 8 6 2 5 9 3 4 | 16
1 8 7 6 3 4 9 2 5 | 16
3 9 4 5 7 1 8 2 6 | 16
4 7 5 3 8 2 6 1 9 | 16
5 7 4 3 9 1 6 2 8 | 16
4 5 8 3 6 2 9 1 7 | 17

[Albert Chan]

(07-25-2018 10:27 PM)Thomas Klemm Wrote:  I just used brute force.

I did solved Thomas third solution by hand.

If using computer is allowed, I would use Picat Programming Language
It is great for puzzle solving, and very fast (below code take 0.12 second to run)

Code:

import cp.                   % zigzag4.pi, 4 sums added to same number S
main => go, fail; true.      % fail forced Picat to search all solutions
go => Vars = [A,B,C,D,E,F,G,H,I],
      Vars :: 1..9,
      all_different(Vars),
      A + B + C #= S,
      E + D + C #= S,
      E + F + G #= S,
      I + H + G #= S,
      solve(Vars), 
      writeln(Vars).

%
% *** solutions below ***
% 
     1    [1,7,6,5,3,9,2,4,8]
     2    [1,7,6,5,3,9,2,8,4]
     3    [1,7,8,6,2,5,9,3,4]
     4    [1,7,8,6,2,5,9,4,3]
     5    [1,7,9,2,6,3,8,4,5]
     6    [1,7,9,2,6,3,8,5,4]
     7    [1,8,7,6,3,4,9,2,5]
     8    [1,8,7,6,3,4,9,5,2]
     9    [1,9,4,8,2,7,5,3,6]
    10    [1,9,4,8,2,7,5,6,3]
    11    [1,9,6,2,8,3,5,4,7]
    12    [1,9,6,2,8,3,5,7,4]
    13    [2,5,9,4,3,6,7,1,8]
    14    [2,5,9,4,3,6,7,8,1]
    15    [2,6,8,1,7,5,4,3,9]
    16    [2,6,8,1,7,5,4,9,3]
    17    [2,8,4,9,1,7,6,3,5]
    18    [2,8,4,9,1,7,6,5,3]
    19    [2,8,6,1,9,3,4,5,7]
    20    [2,8,6,1,9,3,4,7,5]
    21    [2,9,3,4,7,6,1,5,8]
    22    [2,9,3,4,7,6,1,8,5]
    23    [3,4,9,5,2,6,8,1,7]
    24    [3,4,9,5,2,6,8,7,1]
    25    [3,5,6,7,1,9,4,2,8]
    26    [3,5,6,7,1,9,4,8,2]
    27    [3,6,5,7,2,8,4,1,9]
    28    [3,6,5,7,2,8,4,9,1]
    29    [3,9,1,8,4,7,2,5,6]
    30    [3,9,1,8,4,7,2,6,5]
    31    [3,9,2,4,8,5,1,6,7]
    32    [3,9,2,4,8,5,1,7,6]
    33    [3,9,4,5,7,1,8,2,6]
    34    [3,9,4,5,7,1,8,6,2]
    35    [4,3,9,5,2,6,8,1,7]
    36    [4,3,9,5,2,6,8,7,1]
    37    [4,5,8,3,6,2,9,1,7]
    38    [4,5,8,3,6,2,9,7,1]
    39    [4,7,5,3,8,2,6,1,9]
    40    [4,7,5,3,8,2,6,9,1]
    41    [4,8,2,9,3,5,6,1,7]
    42    [4,8,2,9,3,5,6,7,1]
    43    [5,2,9,4,3,6,7,1,8]
    44    [5,2,9,4,3,6,7,8,1]
    45    [5,3,6,7,1,9,4,2,8]
    46    [5,3,6,7,1,9,4,8,2]
    47    [5,4,8,3,6,2,9,1,7]
    48    [5,4,8,3,6,2,9,7,1]
    49    [5,6,2,7,4,8,1,3,9]
    50    [5,6,2,7,4,8,1,9,3]
    51    [5,7,4,3,9,1,6,2,8]
    52    [5,7,4,3,9,1,6,8,2]
    53    [5,8,1,6,7,4,3,2,9]
    54    [5,8,1,6,7,4,3,9,2]
    55    [6,2,8,1,7,5,4,3,9]
    56    [6,2,8,1,7,5,4,9,3]
    57    [6,3,5,7,2,8,4,1,9]
    58    [6,3,5,7,2,8,4,9,1]
    59    [6,5,2,7,4,8,1,3,9]
    60    [6,5,2,7,4,8,1,9,3]
    61    [6,7,1,5,8,4,2,3,9]
    62    [6,7,1,5,8,4,2,9,3]
    63    [7,1,6,5,3,9,2,4,8]
    64    [7,1,6,5,3,9,2,8,4]
    65    [7,1,8,6,2,5,9,3,4]
    66    [7,1,8,6,2,5,9,4,3]
    67    [7,1,9,2,6,3,8,4,5]
    68    [7,1,9,2,6,3,8,5,4]
    69    [7,4,5,3,8,2,6,1,9]
    70    [7,4,5,3,8,2,6,9,1]
    71    [7,5,4,3,9,1,6,2,8]
    72    [7,5,4,3,9,1,6,8,2]
    73    [7,6,1,5,8,4,2,3,9]
    74    [7,6,1,5,8,4,2,9,3]
    75    [8,1,7,6,3,4,9,2,5]
    76    [8,1,7,6,3,4,9,5,2]
    77    [8,2,4,9,1,7,6,3,5]
    78    [8,2,4,9,1,7,6,5,3]
    79    [8,2,6,1,9,3,4,5,7]
    80    [8,2,6,1,9,3,4,7,5]
    81    [8,4,2,9,3,5,6,1,7]
    82    [8,4,2,9,3,5,6,7,1]
    83    [8,5,1,6,7,4,3,2,9]
    84    [8,5,1,6,7,4,3,9,2]
    85    [9,1,4,8,2,7,5,3,6]
    86    [9,1,4,8,2,7,5,6,3]
    87    [9,1,6,2,8,3,5,4,7]
    88    [9,1,6,2,8,3,5,7,4]
    89    [9,2,3,4,7,6,1,5,8]
    90    [9,2,3,4,7,6,1,8,5]
    91    [9,3,1,8,4,7,2,5,6]
    92    [9,3,1,8,4,7,2,6,5]
    93    [9,3,2,4,8,5,1,6,7]
    94    [9,3,2,4,8,5,1,7,6]
    95    [9,3,4,5,7,1,8,2,6]
    96    [9,3,4,5,7,1,8,6,2]

[John Keith]

(07-25-2018 10:27 PM)Thomas Klemm Wrote:  I just used brute force.

So did I!

Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

Edit: my original code was atrociously bad. New "brute force" code is shorter and trims execution time down to 1272 seconds.

Code:


Spoiler alert!












\<< 9. LSEQ 9.
  \<< DUP 3.
    \<< + + NSUB 2. MOD NOT DROPN
    \>> DOSUBS LEQ NOT DROPN
  \>> DOPERM
\>>

[Albert Chan]

Code:

I noticed the middle number e cannot be 5, below is the prove.
Prove by looking at the computer solutions does not count
If you like to prove it yourself, don't peek ...

s = a + b + c
s = e + d + c
s = e + f + g
s = i + h + g

add all of above, note that a+b+c+d+e+f+g+h+i = (1+9)(9)/2 = 45
4s = 45 + c + e + g

Prove by contradiction: assume e = 5

4s = 50 + c + g
min(50 + c + g) <= 4s <= max(50 + c + g)
53 <= 4s <= 67
Possible s = 14, 15, 16

For s = 14, c+g = 4s - 50 = 6 = 2 + 4 (only possibility)
d = s-e-c = 9-c = 7 (only possibility)
f = s-e-g = 9-g = 7 (only possibility)   --> impossible to have s = 14

For s = 15, c+g = 4s - 50 = 10
c + d = s - e = 10 --> imply d = g       --> impossible to have s = 15

For s = 16, c+g = 4s - 50 = 14 = 6 + 8 (only possibility)
d = s-e-c = 11-c = 3 (only possibility)
f = s-e-g = 11-g = 3 (only possibility)  --> impossible to have s = 16

No solution for e = 5

QED

[Thomas Klemm]

(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.

I just used Python:

Code:

from itertools import permutations

def check(a, b, c, d, e, f, g, h, i):
    return len(set([a+b+c, c+d+e, e+f+g, g+h+i])) == 1

print [x for x in permutations(range(1, 10), 9) if check(*x)]

[DavidM]

(07-26-2018 12:57 AM)John Keith Wrote:  So did I!

Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

...and yet another "brute force" method using ListExt with a slight twist on the check.

Code:


Spoiler alert!












\<<
  0. 8. NDUPN \-> a b c d e f g h i
  \<<
    9. DUP LSEQ
    SWAP
    \<<
      { a b c d e f g h i } STO

      a b + d e + SAME
      {
        c d + f g + SAME
        {
          e f + h i + SAME
          {
            { a b c d e f g h i } LRCL R\->I
          }
          IFT
        }
        IFT
      }
      IFT
    \>>
    DOPERM
  \>>
\>>

I assumed (hopefully correctly) that the following conditions had to hold:

a + b = d + e
c + d = f + g
e + f = h + i

So I nested the above tests to short-circuit them.  If a + b ≠ d + e, then there's
no reason to continue checking.  If it is, then if c + d ≠ f + g, there's no reason to
continue checking, etc.

The short-circuit made for a nice speed improvement over checking everything
each time through.

[pier4r]

(07-26-2018 12:57 AM)John Keith Wrote:  Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

one hour on an emulated system that will be at least a pentium 3 and more likely a pentium 4 or the like? Woah. I was expecting the 50g to be wicked fast, of course not entirely by brute force.

When I solved it by hand (a couple of solutions) I noticed a weak pattern (n1), if I find the time I will put it on the 50g to see how much it takes to find every solution.

(n1) I do believe there is a strong pattern. Mine is pretty weak but I didn't discover the strong one yet in the post, maybe because I did not stricly check the posted code.

[John Keith]

(07-26-2018 04:03 AM)DavidM Wrote:  ...and yet another "brute force" method using ListExt with a slight twist on the check.

Actually not brute force as it uses analysis of the problem. Also about 4 times as fast as mine.

[DavidM]

(07-26-2018 01:03 PM)John Keith Wrote:  Actually not brute force as it uses analysis of the problem.

Well, I was thinking that any method based on visiting every permutation would be considered "brute force", though I see your point.

Here's another method that doesn't visit every permutation. It only permutes the remaining variables if the currently selected branches qualify. You might say that it's a wee bit faster.

This one I would definitely not call "brute force".

edit: I just ran this on a real 50g, and it found the same 96 solutions in about 27 minutes. I'm sure this isn't the fastest possible approach on this platform, but it's certainly much better than my first attempt! The Prime (or a newRPL 50g) should be able to do something like this much faster.

Code:

Spoiler alert...











\<<
  0. 8. NDUPN \-> a b c d e f g h i
  \<<
    9. LSEQ
    4.
    \<<
      { a b d e } STO
      a b + d e + SAME
      \<<
        CRMNT
        3.
        \<<
          { c f g } STO
          c d + f g + SAME
          \<<
            CRMNT
            2.
            \<<
              { h i } STO
              e f + h i + SAME
              \<<
                { a b c d e f g h i } LRCL R\->I
              \>>
              IFT
            \>>
            DOPERM EVAL
          \>>
          IFT
        \>>
        DOPERM EVAL
      \>>
      IFT
    \>>
    DOPERM
  \>>
\>>

[Thomas Klemm]

(07-26-2018 12:36 PM)pier4r Wrote:  I do believe there is a strong pattern. Mine is pretty weak but I didn't yet see it, maybe because I did not strictly check the posted code.

We can start with \(e\in\{1\ldots9\}\). And then let \(c\) and \(g\) be different digits with \(c<g\). This gives us \(9\times\binom{8}{2}=252\) possibilities.

But since \(s=a+b+c=c+d+e=e+f+g=g+h+i\) and \(a+b+c+d+e+f+g+h+i=\sum_{k=1}^{9}k=45\) we know that their sum is \(4s=45+c+e+g\) which must be divisible by 4.
This reduces the possibilities further down to 60.

We can now calculate \(d=s-c-e\) and \(f=s-e-g\) and check that both are digits.
And of course each element of \(\{c,d,e,f,g\}\) must be unique.

With this we're down at 12 possibilities:

Code:

Spoiler alert!










c d e f g | s
----------+---
4 9 1 7 6 | 14
4 8 2 7 5 | 14
8 6 2 5 9 | 16
2 9 3 5 6 | 14
7 6 3 4 9 | 16
1 8 4 7 2 | 13
8 3 6 2 9 | 17
1 6 7 4 3 | 14
4 5 7 1 8 | 16
1 5 8 4 2 | 14
5 3 8 2 6 | 16
4 3 9 1 6 | 16

Now it's easy to find \(a\) and \(b\) so that \(a+b+c=s\) and similarly find \(h\) and \(i\) so that \(g+h+i=s\).

Code:

Spoiler alert!










from itertools import combinations

digits = set(range(1, 10))

for e in digits:
    E = digits.copy()
    E.remove(e)
    for c, g in combinations(E, 2):
        t = 45 + c + e + g
        if t % 4:
            continue
        s = t / 4
        d = s - c - e
        if d not in digits:
            continue
        f = s - e - g
        if f not in digits:
            continue
        used = set([c, d, e, f, g])
        if len(used) != 5:
            continue
        rest = digits - used
        for a, b in combinations(rest, 2):
            if a+b+c != s:
                continue
            h, i = rest - set([a, b])
            if g+h+i != s:
                continue
            print a, b, c, d, e, f, g, h, i

Checking only 252 instead of 9! = 362,880 possibilities speeds us up by the factor 1,440.
Even checking that 45+c+e+g is divisible by 4 is rather simple.

Thus here's a program for the HP-42S that lists possible tuples "c:d:e:f:g".
You have to weed some of them out though.
But that's still easier than doing the whole calculation manually.

Code:

Spoiler alert!










9
STO 00
LBL 00
9
STO 01
LBL 01
9
STO 02
LBL 02
RCL 01
RCL 02
X≤Y?
GTO 09
+
RCL+ 00
45
+
4
÷
RCL- 00
ENTER
IP
X≠Y?
GTO 09
RCL-02
X<>Y
RCL- 01
CLA
ARCL 01
 ⊦":"
ARCL ST X
 ⊦":"
ARCL 00
 ⊦":"
ARCL ST Y
 ⊦":"
ARCL 02
AVIEW
LBL 09
DSE 02
GTO 02
DSE 01
GTO 01
DSE 00
GTO 00

Make sure to have the display mode set to ALL.

This will lead to a list like this:

6:2:9:0:8 → discard since f=0 is not valid
5:3:9:-1:9 → discard since f=-1 is not valid
4:3:9:1:6 → this is a valid solution
...


Cheers
Thomas

[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 ...

[Albert Chan]

I have solved the puzzle by hand (no calculator)

Code:

To reduce the permutations, I force c < g, and ignore the edges a, b, h, i (for now)
This reduce permutations to at most 5! / 2 = 60

4 s = 45 + c + e + g
    = (45 + 1+2+3) to (45 + 7+8+9)
    = 51 to 69
    = 52, 56, 60, 64, or 68

--> s = 13, 14, 15, 16, 17

To simplify further, as in tic-tac-toe, try center first (impossible e bracketed)

For s = 13:
c + e + g = 7 = [1] + [2] + 4

1(8)4(7)2 <-- ok

For s = 14:
c + e + g = 11 
= [1] + [2] + 8 
= [1] + [3] + 7 
= 1 + 4 + 6 
= 2 + 3 + 6 
= 2 + 4 + 5

4(9)1(7)6 <-- ok
3 2(6)6
4(8)2(7)5 <-- ok
2(9)3(5)6 <-- ok
1 4(4)6
2 4(5)5
2 5(5)4
1 6(4)4
2(6)6 3
1(6)7(4)3 <-- ok
1(5)8(4)2 <-- ok

For s = 15, c + e + g = 15
But s = 15 also imply c + d + e = 15, which imply d = g, thus s != 15

For s = 16: c + e + g = 19
= 2 + [8] + [9]
= 3 + [7] + [9]
= 4 + 6 + 9
= 4 + 7 + 8 
= 5 + 6 + 8

8(6)2(5)9 <-- ok
7(6)3(4)9 <-- ok
6(6)4 9
7 4(4)8
6(5)5 8
4(6)6 9
5(5)6 8
4(5)7(1)8 <-- ok
4(4)8 7
5(3)8(2)6 <-- ok
4(3)9(1)6 <-- ok

For s = 17: c + e + g = 23 = 6 + [8] + [9]

8(3)6(2)9 <-- ok

Add back missing digits to confirm above 12 cases. All confirmed !
Each solution actually represent 8 solutions, by head swap, tail swap and reverse the digits.

SUM   SOLUTIONS
===   =========
13    391847256
14    284917635
14    194827536
14    482935617
14    581674329
14    671584239
16    178625934
16    187634925
16    394571826
16    475382619
16    574391628
17    458362917

[Valentin Albillo]

.
Hi, Albert Chan:

I'm on the very verge of going on a trip to start my summer vacations so I haven't had much time, if any, to devote to this nice problem by pier4r.

From the top of my head I just had the time to concoct a quik'n'dirty 6-lines of HP-71B code (main program) which calls another simple 6-line subprogram to perform an essentially brute-force search with a few refinements, which finds all solutions very quickly but I have no time to post it here right now, I must go.

Nevertheless, a cursory read of the already existing posts made me realize that yet another symmetry is lacking from all solutions so far (if I read the posts correctly, read them really fast).

Albert Chan Wrote:Add back missing digits to confirm above 12 cases. All confirmed ! Each solution actually represent 8 solutions, by head swap, tail swap and reverse the digits.

Close but no cigar. Actually there are only 6 primary solutions, not 12, each one of them representing 16 derived solutions, not 8.

You mention head swap, tail swap and reverse the digits but you missed 10's-complementing the digits:

• if (d1)(d2)...(d9) is a solution with sum S then (10-d1)(10-d2)...(10-d9) is a solution as well, with sum 30-S.

This halves the number of primary solutions from 12 to just 6, all the remaining 90 are directly derived from this 6.

Albert Chan Wrote:SUM SOLUTIONS
=== =========
13 391847256
14 284917635
14 194827536
14 482935617
14 581674329
14 671584239
16 178625934
16 187634925
16 394571826
16 475382619
16 574391628
17 458362917

Your first 6, say, can be considered the 6 primary solutions. But the remaining 6 are actually derived from them and so aren't primary. For instance, your first solution is:

      13 391847256

and your last (12th) solution can be derived from it by simply 10-complementing it (and in your case, reversing the digits), like this:

      [13, 391847256 ] -> [30-13, (10-3)(10-9)(10-1)...(10-2)(10-5)(10-6)] -> [17, 719263854]

and after reversing the digits we get: 17 458362917, which is your 12th solution indeed. In the same fashion you can derive your 11th solution from the 2nd primary, the 10th solution from the 3rd primary, and so on until deriving your 7th solution from the 6th primary.

Sorry but absolutely no time for more, will be back next September, have a nice summer.

Regards.
V.
.

[Albert Chan]

(07-27-2018 01:30 AM)Valentin Albillo Wrote:  your last (12th) solution can be derived from it by simply 10-complementing it (and in your case, reversing the digits), like this:

      [13, 391847256 ] -> [30-13, (10-3)(10-9)(10-1)...(10-2)(10-5)(10-6)] -> [17, 719263854]

and after reversing the digits we get: 17 458362917, which is your 12th solution indeed.

Hi, Valentin,

Nice catch. That shorten my hand calculations by half. :-)

For this puzzle, center (sum = 15) has no solution, so N-complement symmetry has a clean cut.

But, if center has solution, and other symmetries are involved, it is hard.

A sure way is to build all the center solutions first, go through the list, and remove its N-complement.
Unfortunately, it may be hard to spot, possibly mask by other symmetry.

Each center solution has to check if it's N-complement equivalent had already shown.
That may be more trouble than it is worth ...

Note: zigzag side must have the same length, otherwise N-complement symmetry is gone.

[cyrille de brébisson]

Hello,

Prime version: Brute force, executes in ~7s on my prime.

Code:


Spoiler alert











lstResult;

export recurse(l, p)
begin
  local p1;
  if (p>=6) then 
    p1:= l(1)+l(2)+l(3);
    if (p==6) and (p1 <> l(3)+l(4)+l(5)) then return; end;
    if (p==8) and (p1 <> l(5)+l(6)+l(7)) then return; end;
    if p==9 then
      if p1 == l(7)+l(8)+l(9) then print(string(l)+"->"+p1); lstResult(0):= l; end;
      return;
    end;
  end;

  for p1 from p to size(l) do
    local l2= l;
    l2(p):= l(p1); l2(p1):= l(p);
    recurse(l2, p+1);
  end;
end;

export mth()
begin
  lstResult:= {};
  print("Executed in "+time(recurse(makelist(X, X, 1, 9), 1)));
  print("found "+size(lstResult)+" solutions");
  lstResult;
end;

Cyrille

[pier4r]

(07-26-2018 03:43 PM)Thomas Klemm Wrote:  But since \(s=a+b+c=c+d+e=e+f+g=g+h+i\) and \(a+b+c+d+e+f+g+h+i=\sum_{k=1}^{9}k=45\) we know that their sum is \(4s=45+c+e+g\) which must be divisible by 4.
This reduces the possibilities further down to 60.

This was the same point I reached, then I worked on the multiples of 4. I was not expecting such an healthy thread (n1) for a problem apparently simple.

n1: thanks to this thread I also realize that even if someone posted already a super efficient solution, having other point of views - even with less efficient solutions - gives other perspective and increase the possibility to confront/compose ideas. Thus making the thread more enjoyable.

[Albert Chan]

Discover a way to add Complement Symmetry to solve zigzag puzzles.
Removing center solutions complement equivalent is hard, so the trick is ... not remove it !

This Picat program solve all zigzag puzzles, with sides > 2:
Each solution actually represent 8, by head swap, tail swap, or reversing digits.

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),
 
  A[1] #< A[2],             % 2X solutions by swap head pairs
  A[N-1] #< A[N],           % 2X solutions by swap tail pairs
  A[3] #< A[N-2],           % 2X solutions 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 by tighter constraint on S
  Total + sum([A[I]: I in 3..2..N-2]) #= S * Sides,

  foreach(I in 1..2..N-2)   % All sides sum to S
    A[I] + A[I+1] + A[I+2] #= S
  end,
  
  solve(A),
  writeln(A),
  
  % Add C-Complement Symmetry Solution
  S < Center, writeln([C-I: I in A]).

For a 4-sided zigzag: I still got 12, but Picat really solved only 6:
Complement Symmetry is internalized for a nice speedup.

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

I tried zigzag program with other sides:

Code:

Sides Time(s) solns x 8
3     0.12    56
4     0.12    96
5     0.12    480
6     0.18    1888
7     0.60    10688
8     3.71    46816
9     30.2    267616
10    263.    1502016

[Albert Chan]

Turns out, my not trying to untangle the complement symmetry was dead on.

If there are any solutions at the center, it is unlikely to reduce primary solutions in half.

While playing around with my zigzag.pi, I wanted to see if there is a simple way
to "cut" primary solution in half, as suggested by Valentin ... it cannot be done.

Code:

side  primary solutions at the center (sum = 3 * (side + 1)), all solutions is 8X
3     3
4     0
5     20
6     64
7     524
8     1186
9     7386
10    30746

3-sided zigzag is impossible to cut solutions in half. (3 is odd)

4-sided zigzag can apply complement symmetry because there is nothing in the center.
It is actually the exception case.

5-sided zigzag 20 center solutions can be reduced to 16, but not enough to cut in half.