I like to show why Complement Symmetry work, and why it sometimes does not.
I use a simpler 3-sided zigzag to illustrate.
Instead of using numbers 1 to 7, think of it shifted, from -3 to 3.
So, complement symmetry is just changing the sign of all numbers.
If a solution with a non-zero sum S, complement symmetrical solution has sum -S
Swapping values, reversing ... is not going to change the new sum back to S
Thus, the complement solution is unique.
If all cases were like that, we could return half as many solutions, and let user build the other half.
If the solution had zero sum, it's complement symmetrical solution also had zero sum.
Example: [-2,3,-1,0,1,-3,2]
Above solution, complement (sign change) + reversing digits = itself.
The 2 symmetries overlap (*) :-(
In order to "cut" primary in half, above situation cannot happen.
We required half of solutions to be able to derive from the other half.
Mini-Challenge:
(*) 2 symmetries does not overlap for sides = 4, 6, 8, 10, 12, 14, ... Why ?
In other words, for even sided zigzag, we can indeed reduce primary solutions in half.
You do not need a calculator to prove this ...
Thanks to all who are sharing their various analyses of this deceivingly simple-looking puzzle! It's a great example of how the application of deductive reasoning can greatly reduce the work needed to solve a problem.
(07-26-2018 03:43 PM)Thomas Klemm Wrote: [ -> ]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.
...
So far I've made it up to Thomas' optimizations, which I've translated into an RPL/ListExt implementation.
As expected, this brought the run time down considerably from the previous versions.
Real 50g: 63.9s
Emu48+ on laptop: 1.68s
I'm still trying to wrap my ahead around Albert's and Valentin's approach, especially in terms of how they might translate to a more familiar language.
This has proven to be an intriguing problem!
Code:
Spoiler...
\<<
9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s
\<<
dig
1.
\<<
{ e } STO
CRMNT
2.
\<<
IF
DUP EVAL <
THEN
{ c g } STO
c e g 45. + + + DUP 's' STO
IF
4. MOD NOT
THEN
s 4. / DUPDUP 's' STO
c e + - DUP 'd' STO
SWAP e g + - DUP 'f' STO
IF
DUP2 MIN 0. >
UNROT MAX 10. <
AND
THEN
IF
{ c d e f g } LRCL LDDUP SIZE 5. SAME
THEN
dig { c d e f g } LRCL LRMOV
4.
\<<
{ a b h i } STO
IF
a b c + + s SAME
g h i + + s SAME
AND
THEN
{ a b c d e f g h i } LRCL R\->I
DUP REV
END
\>>
DOPERM EVAL
END
END
END
ELSE
DROP
END
\>>
DOPERM EVAL
\>>
DOPERM
\>>
\>>
The same code, with comments added:
\<<
@ create digits list and declare locals
9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s
\<<
@ permute all single digits
@ I'm using DOPERM here instead of a FOR loop
@ so that I can take advantage of CRMNT to easily obtain remaining digits
dig
1.
\<<
@ save e
{ e } STO
@ permute all remaining digits, in combinations of 2
CRMNT
2.
\<<
IF
@ only proceed if c < g
DUP EVAL <
THEN
@ save c,g
{ c g } STO
@ determine whether s would be valid with this c,e,g
c e g 45. + + + DUP 's' STO
IF
@ only proceed if trial s is evenly divisible by 4
4. MOD NOT
THEN
@ convert trial s (4s) to final s
s 4. / DUPDUP 's' STO
@ compute d and f
c e + - DUP 'd' STO
SWAP e g + - DUP 'f' STO
IF
@ only proceed if d and f are valid digits
DUP2 MIN 0. >
UNROT MAX 10. <
AND
THEN
IF
@ only proceed if c,d,e,f,g are all unique
{ c d e f g } DUP SIZE SWAP LRCL LDDUP SIZE SAME
THEN
@ select remaining digits for a b h i, then
@ check all permutations
dig { c d e f g } LRCL LRMOV
4.
\<<
@ store a,b,h,i
{ a b h i } STO
IF
@ only proceed if sum(a,b,c) and sum(g,h,i) = s
a b c + + s SAME
g h i + + s SAME
AND
THEN
@ all checks passed, add digits and their
@ mirrored form to result
@ (R->I simply added to remove fraction marks)
{ a b c d e f g h i } LRCL R\->I
DUP REV
END
\>>
DOPERM EVAL
END
END
END
ELSE
DROP
END
\>>
DOPERM EVAL
\>>
DOPERM
\>>
\>>
(07-28-2018 04:22 PM)DavidM Wrote: [ -> ]I'm still trying to wrap my ahead around Albert's and Valentin's approach,
especially in terms of how they might translate to a more familiar language.
This has proven to be an intriguing problem!
Hi, DavidM:
With comments, I can finally understand the code. Thanks.
I do not own any HP calculators (except a hand-me-down HP-12C)
I tried coding in
Python, and possibilities is not as high as 252
Brute force all possible values of sum, and it only need 144
Even if sum of 15 is added (why?), it will only reach 180
With complement symmetry, it could be reduced to 72
4 s = 45 + c + e + g
= (45 + 1 + 2 + 3) to (45 + 7 + 8 + 9)
= 51 to 69
= 52, 56, 60, 64, 68
--> s = 13, 14, 15, 16, 17
when s = c + d + e =15, c + e + g = 4 s - 45 = 15, which imply d=g, thus
s != 15
Code:
for s in [13, 14, 16, 17]:
ceg = 4*s - 45
for c in range(1,9):
for g in range(c+1, 10):
e = ceg - c - g
d = s - e - c
f = s - e - g
valid = range(10); # all single digits
try: valid[c] = valid[d] = valid[e] = valid[f] = valid[g] = 0
except IndexError: continue
if valid.count(0) != 6: continue
head = s - c # almost done!, now confirm
valid = filter(None, valid) # remove the zeroes
for x in valid:
if head - x == x: continue
if head - x in valid: head = [x, head-x]; break
if type(head) == int: break # head no good ?
tail = [x for x in valid if x not in head]
print head, c, d, e, f, g, tail
And, the expected result ...
[3, 9] 1 8 4 7 2 [5, 6]
[6, 7] 1 5 8 4 2 [3, 9]
[5, 8] 1 6 7 4 3 [2, 9]
[4, 8] 2 9 3 5 6 [1, 7]
[1, 9] 4 8 2 7 5 [3, 6]
[2, 8] 4 9 1 7 6 [3, 5]
[5, 7] 4 3 9 1 6 [2, 8]
[3, 9] 4 5 7 1 8 [2, 6]
[4, 7] 5 3 8 2 6 [1, 9]
[1, 8] 7 6 3 4 9 [2, 5]
[1, 7] 8 6 2 5 9 [3, 4]
[4, 5] 8 3 6 2 9 [1, 7]
(07-28-2018 01:15 PM)Albert Chan Wrote: [ -> ]Mini-Challenge:
(*) 2 symmetries does not overlap for sides = 4, 6, 8, 10, 12, 14, ... Why ?
In other words, for even sided zigzag, we can indeed reduce primary solutions in half.
You do not need a calculator to prove this ...
The problem of complement symmetry was its overlap with reversing digits symmetry.
This led to its inability to generate unique symmetrical solutions.
Prove by contradiction:
To follow the notation of the 4-sided zigzag, let e be middle number of an
even-sided zigzag.
Let's shift the numbers, so available digits = -side to side
Assume 2 symmetries overlap, middle zigzag look like this:
(c d e f g) => (c d 0 -d -c)
For the center, sum = 0, e = 0, we have:
(c d e f g) => (c -c 0 f -f)
so, for both equation g = -c = -f, or c = f
But, all numbers must be different, assumption was wrong =>
2 symmetries have no overlap.
For even-sided zigzag, we can cut primary solutions in half.
QED
Slight changes to my posted Python code (post 23) dramatically reduce checks down to 17 cases
Only patch is to change the loop range:
s range = [13, 14]
c range = range(max(1, ceg-8-9), min(9, ceg//2))
g range = range(c+1, min(10, 10 - s + ceg))
s range is reduced by taking advantage of 10-Complement Symmetry
c range is reduce because of this: c + e + g = ceg
min(c) = ceg - max(e + g) = ceg - 8 - 9
max(c) = ceg - min(e) - min(g) = ceg - 1 - (max(c) + 1)
max(c) * 2 = ceg - 2
max(c) < floor(ceg / 2)
g range is reduced because d = s - c - e = (s - ceg) + g
Since g is increasing inside loop, d is also increasing, remove invalid d, we get:
max(d) = (s - ceg) + max(g) < 10
max(g) < 10 - s + ceg
With above ranges, these are the only cases checked:
#1: 1 8 4 7 2 => [3, 9] 1 8 4 7 2 [5, 6]
#2: 1 9 3 7 3
#3: 2 9 2 8 3
#4: 1 5 8 4 2 => [6, 7] 1 5 8 4 2 [3, 9]
#5: 1 6 7 4 3 => [5, 8] 1 6 7 4 3 [2, 9]
#6: 1 7 6 4 4
#7: 1 8 5 4 5
#8: 1 9 4 4 6
#9: 2 6 6 5 3
#10: 2 7 5 5 4
#11: 2 8 4 5 5
#12: 2 9 3 5 6 => [4, 8] 2 9 3 5 6 [1, 7]
#13: 3 7 4 6 4
#14: 3 8 3 6 5
#15: 3 9 2 6 6
#16: 4 8 2 7 5 => [1, 9] 4 8 2 7 5 [3, 6]
#17: 4 9 1 7 6 => [2, 8] 4 9 1 7 6 [3, 5]
16X Symmetries: head swap, tail swap, reversing digits, 10-complement
Solutions = 6 primary solutions * 16 = 96
Cyrille de Brebisson, could you explain your algorithm?
Hi, Komanguy
I did a Python version of the zigzag Hp Prime program. With comments, perhaps this is easier to follow:
Code:
def zigzag_prime(slot, filled):
if filled >= 5: # 2 or more sums to match
sum = slot[1] + slot[2] + slot[3]
if filled == 5:
if sum != slot[3] + slot[4] + slot[5]: return
elif filled == 7:
if sum != slot[5] + slot[6] + slot[7]: return
elif filled == 8: # same as filled == 9, but faster
if sum == slot[7] + slot[8] + slot[9]: print slot[1:]
return # success or not, quit
next = filled + 1 # validated, add next digit
old = slot[next]
for i in range(next, 10): # slot[1 to filled] is FIXED
new = slot[i]
slot[next], slot[i] = new, old # try it all
zigzag_prime(slot, next) # recurse
slot[next], slot[i] = old, new # restore slot
zigzag_prime(range(10), 0) # nothing filled yet
Thanks a lot, Albert.
Cheers.
Albert kudos for the effort and sharing!
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)
Here's my straight-forward Turbo Pascal version. It's just depth-first tree traversal with bail-out checks at each vertex. Takes about 12 seconds to find 96 solutions to the 4-sided 1-9 puzzle on my 200LX.
Code:
Program Zigzag;
Var
Used : Array[1..9] Of Boolean;
Nums : Array[1..9] Of ShortInt;
Total : ShortInt;
Solutions, FillCalls : Integer;
Procedure WriteNums;
Var
i : ShortInt;
Begin
For i := 1 To 9 Do
Begin
If i > 1 Then Write(', ');
Write(Nums[i]);
End;
WriteLn(' (', Total, ')');
Inc(Solutions);
End;
Procedure Fill(Pos : ShortInt);
Var
i : ShortInt;
Label
Skip;
Begin
Inc(FillCalls);
For i := 1 To 9 Do
Begin
If Not Used[i] Then
Begin
Used[i] := True;
Nums[Pos] := i;
If Pos = 3 Then
Total := Nums[1] + Nums[2] + Nums[3]
Else If (Pos = 5) Or (Pos = 7) Or (Pos = 9) Then
Begin
If Nums[Pos] + Nums[Pos - 1] + Nums[Pos - 2] <> Total Then
Goto Skip;
End;
If Pos = 9 Then
WriteNums
Else
Fill(Pos + 1);
Skip:
Used[i] := False;
Nums[Pos] := 0;
End;
End;
End;
Begin
FillChar(Used, Sizeof(Used), #0);
FillChar(Nums, Sizeof(Nums), #0);
Total := 0;
Solutions := 0;
FillCalls := 0;
Fill(1);
WriteLn;
WriteLn('Total solutions: ', Solutions);
WriteLn('Recursive calls: ', FillCalls);
End.