Challenging Christmas Puzzle

[OwlHoot]

Cracked it, I think!

The trick is to keep adding a flipped array to itself, to make more and more values in the result equal until you end up with something manageable, and then work backwards from each of the fairly small number of possible solutions of the "merged" array to obtain all solutions of the original.

Specifically, if we start with a symbolic solution, which I won't try and type as it is rather fiddly, then add to this its vertical flip about the middle row, the result is an array of numbers between 2 and 10 inclusive whose rows, columns, and diagonals sum to 30. And this array is symmetric about the middle row.

Now add to the new array its horizontal flip about the middle column, and you get an array of numbers between 4 and 20 inclusive, whose rows, columns, and diagonals now sum to 60.

Finally, add to _this_ new array its flip about the right diagonal to give an array of numbers between 8 and 40 inclusive, whose rows, columns, and diagonals sum to 120.

Each time one flips and merges, values double in the "pivot" row, column, or diagonal. Bearing that in mind, the resulting array has the following form, in which there are now only the 6 possibly distinct integers a1, a2, a3, b2, b3, c3 :

(2 a1)   a2     (2 a3)    a2    (2 a1)

  a2    (2 b2)  (2 b3)  (2 b2)    a2

(2 a3)  (2 b3)  (8 c3)  (2 b3)  (2 a3)

  a2    (2 b2)  (2 b3)  (2 b2)    a2

(2 a1)   a2     (2 a3)    a2    (2 a1)

After dividing out common factors, the equations expressing the sums of each row, column, and diagonal being equal to 120 are:

2 a1 + a2 + a3 = 60

a2 + 2 b2 + b3 = 60

a3 + b3 + 2 c3 = 30

a1 + b2 + 2 c3 = 30

Adding the first two shows that a3 + b3 must be even, say equal 2 t, and then a bit of fiddling around yields the following general solution in the parameters t and a1 :

a2 = 3 (20 - t)

a3 = 3 t - 2 a1

b2 = 2 t - a1

b3 = 2 a1 - t

c3 = 15 - t

where the condition 1 <= c3 <= 5 is equivalent to 10 <= t <= 14, and of course 2 a1, a2, 2 a3, etc (all terms in the above array) must be between 8 and 40 inclusive

Other conditions:

* 8 <= a2 = 3 (20 - t) <= 40 implies (since t is an integer) 3 <= 20 - t <= 13, i.e. 7 <= t <= 17. So the previous bounds are stronger on both sides.

* 4 <= a3 = 3 t - 2 a1 <= 20 implies 3 t - 20 <= 2 a1 <= 3 t - 4

* 4 <= b2 = 2 t - a1 <= 20 implies 2 t - 20 <= a1 <= 2t - 4

* 4 <= b3 = 2 a1 - t <= 20 implies t + 4 <= 2 a1 <= t + 20

Combining the last three gives the following best bounds for a1

  t    min(a1) max(a1)

 10     10      13
 11     12      14
 12     14      16
 13     16      16
 14     18      17  <-- impossible

I whumped up a simple script to produce all possible triple-merged solutions as above, parametrized by t and a1 subject to the above bounds, and the results are as follows:

  t   a1   a2   a3   b2   b3   c3
 10   10   30   10   10   10    5
 10   11   30    8    9   12    5
 10   12   30    6    8   14    5
 10   13   30    4    7   16    5
 11   12   27    9   10   13    4
 11   13   27    7    9   15    4
 11   14   27    5    8   17    4
 12   14   24    8   10   16    3
 12   15   24    6    9   18    3
 12   16   24    4    8   20    3
 13   16   21    7   10   19    2

Another mega-post below details a simple and quick method to work backwards from these flipped-and-merged arrays, to split them recursively into "solution + flipped solution" and thereby construct every possible original array satisfying the conditions of the problem.

[Platypus]

Cracked it, I think!
.
.
.

I'll need to re-read this a few times, but this looks like a very interesting approach.

My own late-night brain-wave was to refine the brute force method by using only rows which I've already calculated add up to 15:

Consider the top row, there are 3125 possible combinations of numbers, but only 381 of these add up to 15.

So I can dramatically reduce the number of combinations I check by using only 'pre-selected' rows.

I've already found more than 90,000 solutions using this method, but the process will still take too long to run to be useful, so I'm going to faff about with the columns as well.

[TimberWolf]

I'll need to re-read this a few times, but this looks like a very interesting approach.

My own late-night brain-wave was to refine the brute force method by using only rows which I've already calculated add up to 15:

Consider the top row, there are 3125 possible combinations of numbers, but only 381 of these add up to 15.

So I can dramatically reduce the number of combinations I check by using only 'pre-selected' rows.

I've already found more than 90,000 solutions using this method, but the process will still take too long to run to be useful, so I'm going to faff about with the columns as well.

So each row (& col & diag) is one of those 381 possible rows. In calculating the number of combinations you'd need to try, there's no need to include the 5th row as it's dictated by the other 4 rows (15-r1-r2-r3-r4). In fact it will be a "check digit row". So that's 381^4 combinations to try, or 2*10^10 combinations. Quite a few. Mind you many swathes could be rejected quite early, with a lot more programming.

[Platypus]

there's no need to include the 5th row as it's dictated by the other 4 rows (15-r1-r2-r3-r4).

DOH! Of course

With that improvement alone, I think I can calculate all solutions in less than an hour

UPDATE: it's flying now !

UPDATE 2: teenage daughter points out fatal flaw in the results !

[OwlHoot]

One can unravel the "flip merges" by simple algebra, as follows.

Here is the next step, to go from any given horizontal-vertical-diagonal (HVD) triple-merge back to every possible horizontal-vertical (HV) double-merge that can produce it.

If you recall, the HVD merge gives an array of the following form, with lots of luvverly symmetry which means one can easily find every possible integer solution for which the rows, columns, and diagonals sum to 120.

(2 a1)   a2     (2 a3)    a2    (2 a1)

  a2    (2 b2)  (2 b3)  (2 b2)    a2

(2 a3)  (2 b3)  (8 c3)  (2 b3)  (2 a3)

  a2    (2 b2)  (2 b3)  (2 b2)    a2

(2 a1)   a2     (2 a3)    a2    (2 a1)

and the object of the exercise is to express:

(2 a1)   a2     (2 a3)

  a2    (2 b2)  (2 b3)

(2 a3)  (2 b3)  (8 c3)

in the form:

    2 x11        (x12 + x21)    2(x13 + x31)

 (x12 + x21)      2 x22         2(x23 + x32)

2(x13 + x31)    2(x32 + x23)        8 x33

i.e. the result of flip-merging the following about its right diagonal :

   x11     x12    2 x13    x12     x11

   x21     x22    2 x23    x22     x21

  2 x31   2 x32   4 x33   2 x32   2 x31

   x21     x22    2 x23    x22     x21

   x11     x12    2 x13    x12     x11

with suitable conditions on the "x_ij" so that the latter is an HV double-merge with rows, columns, and diagonals summing to 60, i.e. so that we have gone back a step.

The conditions are as follows, using results for the a_i, b_j, c_k from the previous post :

x11 = a1

x22 = b2 = 2 t - a1

x33 = c3 = 15 - t


x12 + x21 = a2 = 3(20 - t)

x13 + x31 = a3 = 3 t - 2 a1

x23 + x32 = b3 = 2 a1 - t


x11 + x12 + x13 = 30

x21 + x22 + x23 = 30

x31 + x32 + x33 = 15

(The column sum conditions are satisfied automatically because the "a_i", "b_j", "c_k" row and column sums are equal.)

This set of equations is slightly underdetermined, because the sum of the first and second triplets equals the sum of the third triplet. So we expect another slack variable to pop up, and sure enough the general solution can be expressed in terms of parameters t, a1, x13 (in addition to the expressions for x11, x22, x33 given by the first triplet above) :

To keep the equations and bounds as simple as possible, by inspection it appears best to replace u = a1 + x13, whereupon the last lot of equations becomes:

x12 = 30 - u

x13 = u - a1

x21 = 30 - 3 t + u

x23 = t + a1 - u

x31 = 3 t - a1 - u

x32 = a1 + u - 2 t

and u can be bounded in various ways as follows:

1. 4 <= x12 = 30 - u <= 20 is equivalent to: 10 <= u <= 26

2. 2 <= x13 = u - a1 <= 10 is equivalent to: a1 + 2 <= u <= a1 + 10 (implies (1) for all valid values of a1, i.e. (1) is weaker)

3. 4 <= x21 = 30 - 3t + u <= 20 is equivalent to: 3 t - 26 <= u <= 3 t - 10.

So bearing in mind that 10 <= t <= 13, (3) gives stronger bounds than (1) as follows:

u <= 20 if t = 10
u <= 23 if t = 11
13 <= u if t = 13

Well that concludes our enumeration of all HV-arrays. My script found 40 HV arrays.

The next step is to work back from HV-arrays to H-arrays.

I anticipated the final two stages would be horribly intricate. But they are actually much easier, because each unknown occurs in only one equation so there's no "cross-talk" between equations.

To backtrack from an HV double-flip to an H single-flip simply involves finding a set of integers "y_ij" for which the array:

   x11     x12    2 x13    x12     x11

   x21     x22    2 x23    x22     x21

  2 x31   2 x32   4 x33   2 x32   2 x31

is term-by-term equal to the result of flipping and adding the following about its middle column:

   y11     y12    y13    y14    y15

   y21     y22    y23    y24    y25

  2 y31   2 y32  2 y33  2 y34  2 y35

and that result is :

   y11 + y15      y12 + y14    2 y13     y12 + y14      y11 + y15

   y21 + y25      y22 + y24    2 y23     y22 + y24      y21 + y25

 2(y31 + y35)   2(y32 + y34)   4 y33   2(y32 + y34)   2(y31 + y35)

So from each sum of two "y" elements, you can just pick one and express that in terms of the other and "x"s, which we already know, for example:

y13 = x13

y14 = x12 - y12

y15 = x11 - y11

y23 = x23

y24 = x22 - y22

y25 = x21 - y21

y33 = x33

y34 = x32 - y32

y35 = x31 - y31

Here the bounds are simply that every "y" (or "2y" for the middle row) is between 2 and 10 inclusive (recall that x12, x11, x22, x21, x32, x31 must all be between 4 and 20 inclusive, and x13, x23, x33 between 2 and 10 inclusive). So one obtains solutions from 6 lots of pairs independently, which means there is probably a very large number of solutions!

Finally, reversing the H-flip to backtrack to original arrays works exactly the same way, although it involves twice as many elements. Well that's that - A script could easily be written to churn out all the solutions pretty quickly, but I can't spare any more time on this pesky problem!

[TimberWolf]

DOH! Of course

With that improvement alone, I think I can calculate all solutions in less than an hour

UPDATE: it's flying now !

UPDATE 2: teenage daughter points out fatal flaw in the results !

Is it running or being debugged?

You could decrease processing time immensely, and seemingly quite easily, by rejecting rows as early as after row 2, because as you form the 3rd row, the first two digits (of the previous rows in a particular column) have to exist in one of your 381 valid combinations table. That table could itself have been sorted and binary-searched, or indexed, for a quick look up.

[Platypus]

Is it running or being debugged?

It's running now, ETA another hour (total running time expected to be about 2 hours)

You could decrease processing time immensely, and seemingly quite easily, by rejecting rows as early as after row 2, because as you form the 3rd row, the first two digits (of the previous rows in a particular column) have to exist in one of your 381 valid combinations table. That table could itself have been sorted and binary-searched, or indexed, for a quick look up.

Very true. I may try that. After a while it becomes a trade-off between how long you spend pruning possible solutions between just quickly throwing together solutions and checking them.

For example, after two rows, there's no point checking because every two-digit combination is valid.
After 3 rows 117 of the possible 125 combinations are valid
After 4 rows 381 of the possible 625 combinations are valid
The 5th row is always sure to work thanks to your previous tip about calculating it (this made a massive difference)

[TimberWolf]

It's running now, ETA another hour (total running time expected to be about 2 hours)



Very true. I may try that. After a while it becomes a trade-off between how long you spend pruning possible solutions between just quickly throwing together solutions and checking them.

For example, after two rows, there's no point checking because every two-digit combination is valid.
After 3 rows 117 of the possible 125 combinations are valid
After 4 rows 381 of the possible 625 combinations are valid
The 5th row is always sure to work thanks to your previous tip about calculating it (this made a massive difference)

Yeah, a trade-off between CPU time and programmer time. I suspect this program could execute in less than a second if (possibly a great deal of) time were spend furthering the method though.

For example the first row has to consist of any of the 381 row combinations that you identified (and which now looks like a great way of cracking the problem fairly quickly). So the 5 columns that hang of this row must start with that number as their first element. About 60 possibilities. And once the second row is in, the column possibilities (off two starting numbers) come down to about half a dozen.

For example

if starting with 11355

The first column must begin with 1 so that's any of:
11355 11445 11454 11535 11544 11553 12255 12345 12354 12435 12444 12453 12525 12534 12543 12552 13155 13245 13254 13335 13344 13353 13425 13434 13443 13452 13515 13524 13533 13542 13551 14145 14154 14235 14244 14253 14325 14334 14343 14352 14415 14424 14433 14442 14451 14514 14523 14532 14541 15135 15144 15153 15225 15234 15243 15252 15315 15324 15333 15342 15351 15414 15423 15432 15441 15513 15522 15531

and if two rows were in just:
11355 11445 11454 11535 11544 11553

But I agree it is better to let the CPU take the strain.

[Platypus]

For example the first row has to consist of any of the 381 row combinations that you identified (and which now looks like a great way of cracking the problem fairly quickly). So the 5 columns that hang of this row must start with that number as their first element. About 60 possibilities. And once the second row is in, the column possibilities (off two starting numbers) come down to about half a dozen.

For example

if starting with 11355

The first column must begin with 1 so that's any of:
11355 11445 11454 11535 11544 11553 12255 12345 12354 12435 12444 12453 12525 12534 12543 12552 13155 13245 13254 13335 13344 13353 13425 13434 13443 13452 13515 13524 13533 13542 13551 14145 14154 14235 14244 14253 14325 14334 14343 14352 14415 14424 14433 14442 14451 14514 14523 14532 14541 15135 15144 15153 15225 15234 15243 15252 15315 15324 15333 15342 15351 15414 15423 15432 15441 15513 15522 15531

and if two rows were in just:
11355 11445 11454 11535 11544 11553

I think this is very elegant, so much so that I now disagree with:

But I agree it is better to let the CPU take the strain.

EDIT: now pressed Ctrl-C, bored with the previous version!

[TimberWolf]

I think this is very elegant, so much so that I now disagree with:



EDIT: now pressed Ctrl-C, bored with the previous version!

D'oh! It will probably take at least an hour to code up