Challenging Christmas Puzzle

[TimberWolf]

Now I shall write to the manufacturer pointing out that the one solution they provided is just 1 of 836,864 and that perhaps they should improve their solution sheet should mention that there are other solutions

But I won't go as far as to suggest that print these other solutions on the sheet

What was their solution?

[Platypus]

What was their solution?

25413
51342
34521
42135
13254

i.e. a 1,2,3,4,5 in each row, column and both diagonals

Which I should stress is not a specified criteria of a valid solutions (the only criteria was that each row, column and both diagonals should sum to 15).

EDIT: small modification to program gives 960 solutions where each row, column and both diagonals contain 1,2,3,4,5

[OwlHoot]

Excellent work! I guess that’s the puzzle solved. ..

Yup, that sounds like the right answer - Congratulations. I've made enquiries on a couple of puzzle forums, so it'll be interesting to see if there are any replies from that, and I'll post any info that turns up.

I've checked my code and can't see anything obviously wrong, like using x23 instead of x12 or something after a copy and paste, although God knows there are double indexes all over the place as you can imagine and I may have missed one.

I think what may be happening is that one of my loop bounds is 2 - 10 instead of 4 - 20 or something like that (given how my approach is supposed to work).

I guess there's a moral there about software development in general - It isn't worth trying too hard to develop a complicated optimized algorithm for a one-off problem when a simpler approach gets the answer in a reasonable time (although when you mentioned a running time of 12 years, I thought that was necessary for this problem!)

[TimberWolf]

EDIT: small modification to program gives 960 solutions where each row, column and both diagonals contain 1,2,3,4,5

I can confirm 960.

[TimberWolf]

Yup, that sounds like the right answer - Congratulations. I've made enquiries on a couple of puzzle forums, so it'll be interesting to see if there are any replies from that, and I'll post any info that turns up.

I've checked my code and can't see anything obviously wrong, like using x23 instead of x12 or something after a copy and paste, although God knows there are double indexes all over the place as you can imagine and I may have missed one.

I think what may be happening is that one of my loop bounds is 2 - 10 instead of 4 - 20 or something like that (given how my approach is supposed to work).

I guess there's a moral there about software development in general - It isn't worth trying too hard to develop a complicated optimized algorithm for a one-off problem when a simpler approach gets the answer in a reasonable time (although when you mentioned a running time of 12 years, I thought that was necessary for this problem!)

Since we have more solutions than yourself (5 times as many), perhaps it would help if I pasted a few here. I can present them in a numerically sorted order, so if you are to also sort them, there's a chance the missing ones can be spotted. I'll post the first 10 solutions (and I've plenty more where they came from):

11355 14424 55212 42351 43323
11355 14433 55221 52242 33414
11355 14514 45321 52242 43233
11355 14514 54222 43251 43323
11355 14523 44223 52251 44313
11355 14523 44322 51342 45123
11355 14523 45231 52242 43314
11355 14523 45321 51243 44223
11355 14523 54213 42351 44223
11355 14532 54213 52341 34224


Or in an easier to read format, the same 10:

11355
14424
55212
42351
43323

11355
14433
55221
52242
33414

11355
14514
45321
52242
43233

11355
14514
54222
43251
43323

11355
14523
44223
52251
44313

11355
14523
44322
51342
45123

11355
14523
45231
52242
43314

11355
14523
45321
51243
44223

11355
14523
54213
42351
44223

11355
14532
54213
52341
34224

[TimberWolf]

Who fancies a go at this then?



Are you hard enough? It should keep brute force methods busy for a while. Rows sum to 21 in this 6*6 case.

Here's one solution:

2 3 1 6 3 6
6 4 4 2 4 1
3 2 4 1 6 5
5 5 5 4 1 1
3 3 1 3 5 6
2 4 6 5 2 2

I'm not going to try to brute force that grid to find all solutions, I'd prefer to see whether Owlhoot can crack his method (whatever it is) with the 5*5 grid first. Though even if that did work, the question would be whether 6*6 and above would be tractable, or whether it's just a slightly quicker brute force method.


Here's a summary of how (I believe) things stand for grid sizes up to 7:

Table   Rows sum     Platypus     Solutions
size       to         number

1*1        1            1            0 (or 1)
2*2        3            2            0
3*3        6            7            4
4*4       10           44          256
5*5       15          381      836,864
6*6       21        4,332            ?
7*7       28       60,691            ?

I did a quick run on table sizes 1*1 to 4*4 to find their numbers of solutions above. You can see how the number of solutions is climbing at an exponential rate, which if continued unbridled might be a killer even for optimised algorithms, as if there are trillions of trillions of solutions, they are going to take time to produce no matter how elegant the algorithm, unless that value can be found without going through them all and counting them one at a time.

[Platypus]

I suspect that your own contributions to a proposed solution offer the best hope. The final version of that did a mere 75 million checks compared with 3 odd billion for the "381^4" version.

I may have a noodle, but maybe later !

[OwlHoot]

No way can I afford to spend any more time on this problem. (Get thee behind me Satan!) So for that reason I'm out.

But if you enumerate the 6*6 solutions, why not submit the sequence 1, 0, 256, 836864, ? to the Sloane On-Line Encyclopedia of Integer Sequences™ (OEIS™) and get your name(s) in lights ?

The first count should definitely be 1, as a single element equal to 1 trivially satisfies all the conditions, and there's currently no OEIS sequence 1, 0, 4, 256

BTW I didn't get any very useful replies from my post elsewhere, except to confirm your 5*5 result

[TimberWolf]

But if you enumerate the 6*6 solutions, why not submit the sequence 1, 0, 256, 836864, ? to the Sloane On-Line Encyclopedia of Integer Sequences™ (OEIS™) and get your name(s) in lights ?

The honour is Platypus'.

As for the next count in that sequence, I've noticed that it's divisible by the last. 836,864 is divisible by 256, etc. At first I had 'aha, of course' moment, as one grid is inside another and can be combined inside the new extra squares making up a bigger grid, and combined again each time the new surrounding squares are rearranged. But after a bit more thought it became less obvious that that should be the case.

[Platypus]

Update for anyone WGAS

I'm trying to make my code run absolutely as fast as possible, while generalising it for grids larger than 5x5.

I've pruned several minutes, but the largest improvement has come from running it natively under MSVC (v6) rather than under the old 'MKS NuTCracker' environment (which is what I was using).

At this point, I can solve the 5x5 problem in approx 4:20 minutes (from a possible 21 billion combinations). However, a 6x6 grid offers 4332^5 combinations (assuming the last row is calculated). Which is 72 million times more.

So maybe I can solve 6x6 in 72 million x 5 minutes = 688 years

On the other hand, one can slide and dice this calculation various ways, so I'm going to write the code for a 6x6 and see what happens.

I'll post the result, hopefully in less than 688 years.

I am just going outside and may be some time ...