Challenging Christmas Puzzle

[VectraMan]

The real challenge would be to write a mathematical proof that demonstrates there are exactly n solutions.

Do we count each tile as seperate, or all the tiles with the same number as the same?

I.e. if you swap one 5 with another 5, does that could as two solutions?

[Freamon]

Do we count each tile as seperate, or all the tiles with the same number as the same?

I.e. if you swap one 5 with another 5, does that could as two solutions?

No.

[OwlHoot]

If you plan to try every combination, you can narrow down the possibilities up front, so to speak, by considering values mod 2.

In other words, start by enumerating every possible combination of a 5-by-5 array of 0s and 1s for which the numbers of 1s in every row, column, and main diagonal are all odd.

So, briefly:

(1) For a row or column with all five values odd, there is obviously only one possibility mod 2:

(1, 1, 1, 1, 1)

This must correspond to a permutation of one of (1, 1, 3, 5, 5), (1, 3, 3, 3, 5), or (3, 3, 3, 3, 3).


(2) For a row or column with three values odd, the possible permutations mod 2 are:

(1, 1, 1, 0, 0)
(1, 1, 0, 1, 0)
(1, 1, 0, 0, 1)
(1, 0, 1, 1, 0)
(1, 0, 1, 0, 1)
(1, 0, 0, 1, 1)
(0, 1, 1, 1, 0)
(0, 1, 1, 0, 1)
(0, 1, 0, 1, 1)
(0, 0, 1, 1, 1)

(2) Finally, for a row or column with one value odd, the possibilities mod 2 are obviously:

(1, 0, 0, 0, 0)
(0, 1, 0, 0, 0)
(0, 0, 1, 0, 0)
(0, 0, 0, 1, 0)
(0, 0, 0, 0, 1)

Each of these must correspond to permutations of one of (5, 4, 2, 2, 2), (3, 4, 4, 2, 2), or (1, 4, 4, 4, 2)

So it shouldn't be too hard to try all possible 16^5 combinations of mod 2 rows, and ditch all those which don't also have all columns and main diagonals also as one of the 16 mod 2 possibilities with an odd number of 1s. Oh, and one can also discard any which are left or right "diagonal flips" of those on the list (or vertical or horizontal flips)

[TimberWolf]

That's exactly what I'm wondering now !

A quick(ish) inspection by hand (which I thought would be quicker than writing a program to find one at least) gives a solution:

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

It's not totally jumbled, since a short-cut I used was to randomly make up the first two rows to 15 using any numbers (actually both rows in combination do use all the correct numbers), and then filled in the remainder being sure to use all 5 numbers 'correctly' in each of the rows, columns and diagonals.

[Platypus]

A quick(ish) inspection by hand (which I thought would be quicker than writing a program to find one at least) gives a solution:

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

It's not totally jumbled, since a short-cut I used was to randomly make up the first two rows to 15 using any numbers (actually both rows in combination do use all the correct numbers), and then filled in the remainder being sure to use all 5 numbers 'correctly' in each of the rows, columns and diagonals.

WOW!! Great work.

This must mean that there are many more solutions than I first thought.

Version 1 of my program assumed that each row and column must use one each of 1,2,3,4,5.
It produced a surprising number of solutions. (A lot more than 15).

Version 2 is crunching all combinations, but I expect this will take 12 years to run, so I need some short cuts!
Interesting insights from Owlhoot, which I'll look at, as I CBA to wait 12 years to post a triumphant final result.

Any (much cleverer than me) programmers out there able to calculate this in an hour or two?

[TimberWolf]

WOW!! Great work.

This must mean that there are many more solutions than I first thought.

Version 1 of my program assumed that each row and column must use one each of 1,2,3,4,5.
It produced a surprising number of solutions. (A lot more than 15).

Version 2 is crunching all combinations, but I expect this will take 12 years to run, so I need some short cuts!
Interesting insights from Owlhoot, which I'll look at, as I CBA to wait 12 years to post a triumphant final result.

Any (much cleverer than me) programmers out there able to calculate this in an hour or two?

It would take me longer than 2 hours to remember how to programme.

But some short-cuts/specifying what is known might cut the running time down a bit, if not the programming time:

• All rows columns & diagonals (R, C & D) sum to 15
• Each R, C & D contain an odd number of odd numbers (because their sum is odd) ,i.e. 1, 3 or all 5 in a line must be odd
• The total number of odd numbers used on the board must = 15
• One number cannot be used more than 5 times. In fact each number 1..5 must be used 5 times.

What Owlhoot said looks elegant, but I'd also be tempted by brute force and quickly giving up on dead-ends with the rules above (plus any more thought up) would cut out a lot of combinations quickly. Bit of a mare to programme though.

[OwlHoot]

Interesting insights from Owlhoot, which I'll look at, as I CBA to wait 12 years to post a triumphant final result.

I knocked together a perl script that checked for the mod 2 solutions, along the lines I suggested, and it found 9548 valid solutions

and it would have been 8 times that if I hadn't counted groups of 8 flips as one "equivalence class" :

abc
def
ghi

(vertical flip)

ghi
def
abc

(horizontal flip)

ihg
fed
cba

(vertical flip)

cba
fed
ihg

(flip about left diagonal)

gda
heb
ifc

(vertical flip)

ifc
heb
gda

(horizontal flip)

cfi
beh
adg

(vertical flip)

adg
beh
cfi

(using a 3 by 3 array instead of 5 by 5 just to illustrate the process)

Next step is to try for each of these all possible permutations of actual rows for the "1 odd element" and "5 odd element" cases I also mentioned, as luckily there aren't too many of these - It may be this will knock out a lot of possibilities if the sum of the remaining rows doesn't match the sum of the remaining values, if you see what I mean.

Darn, I was supposed to be mugging up on Java this week too.

[realityhack]

I hereby award 5 of my Xeno Geek Points to each contributor in this thread before this post.

[OwlHoot]

Right, I think the following should be a fairly efficient way of breaking down the problem.

If we ignore the sum of the diagonals to start with, then you can permute columns to ensure that at least one row (say the first) is in non-decreasing order, and that means only the following 12 possibilities for this first row:

33333
43332
44322
44331
44421
53322
53331
54222
54321
54411
55221
55311

Then for each of these recursively work out a "tree" of possibilities for the remaining rows, with each row and column summing to 15. I don't think there will be as many possibilities as one might imagine, especially once one has reached the bottom level of the tree and then checks the columns.

Finally, for each possible array whose rows and columns all sum to 15, search all permutions of the rows and columns searching for solutions with diagonals also summing to 15.

[TimberWolf]

I've found a pretty one:

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

Notice all the three's on the minor diagonal, and the 3x3 magic square in the middle.

I wrote a quick programme that randomly exchanges squares if that change has a better score (least square of the sums of the R, C & D's - 15), and it quickly finds solutions. No good for counting though.

For counting purposes I considered ignoring combinations and just starting with 55321, 55123,...54...., 53..., etc, cutting out many permutations as I went along. I'm satisfied with my random approach though.