Challenging Christmas Puzzle

[OwlHoot]

The trouble is the count for n=6 may be so large that just incrementing a count from zero to the required size (and doing nothing else) might take months or years, and clearly that is an (unattainable) lower bound on any "try all cases" procedure.

But if not then my "fold and unfold" approach might come into its own for n=6, although some of the details would need generalizing and simplifying (even at the cost of making it sub-optimal).

edit: For n=6 (or any even n) the row and column "flip and adds" AKA merges don't leave an "unaffected apart from doubling" central row and column respectively, and that improves the array element equalization in these stages :

Original n=6 array:

 a11  a12  a13  a14  a15  a16

 a21  a22  a23  a24  a25  a26

 a31  a32  a33  a34  a35  a36

 a41  a42  a43  a44  a45  a46

 a51  a52  a53  a54  a55  a56

 a61  a62  a63  a64  a65  a66

After row flip-and-add :

 b11  b12  b13  b14  b15  b16

 b21  b22  b23  b24  b25  b26

 b31  b32  b33  b34  b35  b36

 b31  b32  b33  b34  b35  b36

 b21  b22  b23  b24  b25  b26

 b11  b12  b13  b14  b15  b16

After column flip-and-add:

 c11  c12  c13  c13  c12  c11

 c21  c22  c23  c23  c22  c21

 c31  c32  c33  c33  c32  c31 

 c31  c32  c33  c33  c32  c31 

 c21  c22  c23  c23  c22  c21

 c11  c12  c13  c13  c12  c11

After right diagonal flip-and-add :

 2 c11   d12    d13    d13    d12    d11

  d12   2 c22   d23    d23    d22    d12

  d13    d23   2 c33   d33    d23    d13 

  d13    d23    d33   2 c33   d23    d13 

  d12    d22    d23    d23   2 c22   d12

  d11    d12    d13    d13    d12   2 c11

So that leaves only the 6 distinct elements: c11, c22, c33, d12, d13, d23, in an array whose rows, columns, and main diagonals must sum to 8 * 21,
and it shouldn't take long to find all combinations of the latter with 4 <= c_ij <= 24 and 8 <= d_ij <= 48.

[TimberWolf]

I started thinking about the number of solutions likely to come up, with my first guess being around the 12 digit mark, from the way previous terms had grown. But alas I got bogged down in algebra which has exhausted my time.

I started looking at the total number of arrangements of the squares (regardless of lines summing to n(n+1)/2). It's a pretty formula:

(n^2)! / (n!)^n

Which by Sterling's approximation and also hopefully after my simplification comes to :

(2pi)^0.5 . n ^ (n^2+1)
-----------------------
     (2pi.n)^(n/2)

I used to have a neat symbolic equation solver/simplifier called "Scientific Notepad", but alas that doesn't work on Vista so now all I have is my pen. Does anyone know of any decent free or very low cost maths packages that handle symbolic algebra?

[OwlHoot]

I started thinking about the number of solutions likely to come up, with my first guess being around the 12 digit mark, from the way previous terms had grown. But alas I got bogged down in algebra which has exhausted my time.

I started looking at the total number of arrangements of the squares (regardless of lines summing to n(n+1)/2). It's a pretty formula:

(n^2)! / (n!)^n

Which by Sterling's approximation and also hopefully after my simplification comes to :

(2pi)^0.5 . n ^ (n^2+1)
-----------------------
     (2pi.n)^(n/2)

I used to have a neat symbolic equation solver/simplifier called "Scientific Notepad", but alas that doesn't work on Vista so now all I have is my pen. Does anyone know of any decent free or very low cost maths packages that handle symbolic algebra?

Just replace each factorial by Stirling's Approximation

This is a divergent series whose truncations give very accurate approximations, e.g.

n! = SQRT(2 PI n) (n / e)^n (1  +  1 / (12 n))

I don't think it's as simple as that though, because all the sums, and the requirement to use a given set of numbers impose extra, and arguably "artificial", conditions.

Incidently, the number of magic squares (a closely related construct) of order 6 is currently unknown, but believed to be about 1.7 * 10^19, and this enumeration is probably tougher than even that!

It is an unsolved problem to determine the number of magic squares of an arbitrary order, but the number of distinct magic squares (excluding those obtained by rotation and reflection) of order n=1, 2, ... are 1, 0, 1, 880, 275305224, ... (Sloane's A006052; Madachy 1979, p. 87). The 880 squares of order four were enumerated by Frénicle de Bessy in 1693, and are illustrated in Berlekamp et al. (1982, pp. 778-783). The number of 5×5 magic squares was computed by R. Schroeppel in 1973. The number of 6×6 squares is not known, but Pinn and Wieczerkowski (1998) estimated it to be (1.7745+/-0.0016)×10^(19) using Monte Carlo simulation and methods from statistical mechanics.

edit: Oops, sorry, missed the bit where you said you already used Stirling's approximation. I'll think about it some more when I'm sober :-)

[TimberWolf]

using Monte Carlo simulation and methods from statistical mechanics.

I briefly considered using statistical methods to approximate what the answer would be, by counting the number of invalid combinations tried before a valid one was found. But given that there are 2.7*10^24 arrangements, the likelihood of finding a solution by chance in a reasonable amount of time seemed too small. A program that swaps two squares if the resulting arrangement is closer to a valid solution does quickly find solutions though, and it's possible some kind of analysis could be done on that.

[TimberWolf]

Incidentally the number of solutions, as a proportion of all possible unique combinations (not necessarily summing to n(n+1)2, is reducing exponentially, even if the number of those unique combinations is increasing at an exponentially greater rate.
i.e.

n      solutions      unique combinations      col3  / col 2 

1          1                     1                1 in 1
2          0                     6                undefined
3          4                  1680                1 in 420
4        256              6 * 10^7                1 in 3/4 million
5    836,864             6 * 10^14                1 in 740 million

[Spacecadet]

I went for the brute force method using SQL

First a proof of concept using a 3x3 grid where each line and diagonal = 6

with n as (
select '1' as n
union all
select '2' as n
union all
select '3' as n
) ,
r as (
select n1.n c1, n2.n c2, n3.n c3
from n n1
cross join n n2
cross join n n3
where cast(n1.n as int) + cast(n2.n as int) + cast(n3.n as int) = 6
)
select r1.c1 as r1c1,r1.c2 as r1c2, r1.c3 as r1c3,
       r2.c1 as r2c1,r2.c2 as r2c2, r2.c3 as r2c3,
       r3.c1 as r3c1,r3.c2 as r3c2, r3.c3 as r3c3
from r r1
cross join r r2
cross join r r3
where 
    len(replace(
    r1.c1+r1.c2+r1.c3+
    r2.c1+r2.c2+r2.c3+
    r3.c1+r3.c2+r3.c3, '1', '')) = 6
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+
    r2.c1+r2.c2+r2.c3+
    r3.c1+r3.c2+r3.c3, '2', '')) = 6
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+
    r2.c1+r2.c2+r2.c3+
    r3.c1+r3.c2+r3.c3, '3', '')) = 6
and 
    cast(r1.c1 as int) + CAST(r2.c2 as int) + CAST(r3.c3 as int) = 6
and 
    cast(r1.c3 as int) + CAST(r2.c2 as int) + CAST(r3.c1 as int) = 6
and 
    cast(r1.c1 as int) + CAST(r2.c1 as int) + CAST(r3.c1 as int) = 6    
and 
    cast(r1.c2 as int) + CAST(r2.c2 as int) + CAST(r3.c2 as int) = 6        
and 
    cast(r1.c3 as int) + CAST(r2.c3 as int) + CAST(r3.c3 as int) = 6

Expanding this to a 5x5 grid:

with n as (
select '1' as n
union all
select '2' as n
union all
select '3' as n
union all
select '4' as n
union all
select '5' as n
) ,
r as (
select n1.n c1, n2.n c2, n3.n c3, n4.n c4, n5.n c5
from n n1
cross join n n2
cross join n n3
cross join n n4
cross join n n5
where cast(n1.n as int) + cast(n2.n as int) + cast(n3.n as int) + cast(n4.n as int) + cast(n5.n as int) = 15
)
select r1.c1 as r1c1,r1.c2 as r1c2, r1.c3 as r1c3, r1.c4 as r1c4, r1.c5 as r1c5,
       r2.c1 as r2c1,r2.c2 as r2c2, r2.c3 as r2c3, r2.c4 as r2c4, r2.c5 as r2c5,
       r3.c1 as r3c1,r3.c2 as r3c2, r3.c3 as r3c3, r3.c4 as r3c4, r3.c5 as r3c5,
       r4.c1 as r4c1,r4.c2 as r4c2, r4.c3 as r4c3, r4.c4 as r4c4, r4.c5 as r1c5,
       r5.c1 as r5c1,r5.c2 as r5c2, r5.c3 as r5c3, r5.c4 as r5c4, r5.c5 as r1c5
from r r1
cross join r r2
cross join r r3
cross join r r4
cross join r r5
where 
    len(replace(
    r1.c1+r1.c2+r1.c3+r1.c4+r1.c5+
    r2.c1+r2.c2+r2.c3+r2.c4+r2.c5+
    r3.c1+r3.c2+r3.c3+r3.c4+r3.c5+
    r4.c1+r4.c2+r4.c3+r4.c4+r4.c5+
    r5.c1+r5.c2+r5.c3+r5.c4+r5.c5, '1', '')) = 20
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+r1.c4+r1.c5+
    r2.c1+r2.c2+r2.c3+r2.c4+r2.c5+
    r3.c1+r3.c2+r3.c3+r3.c4+r3.c5+
    r4.c1+r4.c2+r4.c3+r4.c4+r4.c5+
    r5.c1+r5.c2+r5.c3+r5.c4+r5.c5, '2', '')) = 20
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+r1.c4+r1.c5+
    r2.c1+r2.c2+r2.c3+r2.c4+r2.c5+
    r3.c1+r3.c2+r3.c3+r3.c4+r3.c5+
    r4.c1+r4.c2+r4.c3+r4.c4+r4.c5+
    r5.c1+r5.c2+r5.c3+r5.c4+r5.c5, '3', '')) = 20
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+r1.c4+r1.c5+
    r2.c1+r2.c2+r2.c3+r2.c4+r2.c5+
    r3.c1+r3.c2+r3.c3+r3.c4+r3.c5+
    r4.c1+r4.c2+r4.c3+r4.c4+r4.c5+
    r5.c1+r5.c2+r5.c3+r5.c4+r5.c5, '4', '')) = 20
and 
    len(replace(
    r1.c1+r1.c2+r1.c3+r1.c4+r1.c5+
    r2.c1+r2.c2+r2.c3+r2.c4+r2.c5+
    r3.c1+r3.c2+r3.c3+r3.c4+r3.c5+
    r4.c1+r4.c2+r4.c3+r4.c4+r4.c5+
    r5.c1+r5.c2+r5.c3+r5.c4+r5.c5, '5', '')) = 20
and 
    cast(r1.c1 as int) + CAST(r2.c2 as int) + CAST(r3.c3 as int) + CAST(r4.c4 as int) + CAST(r5.c5 as int) = 15
and 
    cast(r1.c5 as int) + CAST(r2.c4 as int) + CAST(r3.c3 as int) + CAST(r4.c2 as int) + CAST(r5.c1 as int) = 15    
and 
    cast(r1.c1 as int) + CAST(r2.c1 as int) + CAST(r3.c1 as int) + CAST(r4.c1 as int) + CAST(r5.c1 as int) = 15    
and 
    cast(r1.c2 as int) + CAST(r2.c2 as int) + CAST(r3.c2 as int) + CAST(r4.c2 as int) + CAST(r5.c2 as int) = 15        
and 
    cast(r1.c3 as int) + CAST(r2.c3 as int) + CAST(r3.c3 as int) + CAST(r4.c3 as int) + CAST(r5.c3 as int) = 15        
and 
    cast(r1.c4 as int) + CAST(r2.c4 as int) + CAST(r3.c4 as int) + CAST(r4.c4 as int) + CAST(r5.c4 as int) = 15        
and 
    cast(r1.c5 as int) + CAST(r2.c5 as int) + CAST(r3.c5 as int) + CAST(r4.c5 as int) + CAST(r5.c5 as int) = 15

This found almost 60,000 solutions in 22 minutes - at which point I stopped it!

[TimberWolf]

I started thinking about the number of solutions likely to come up, with my first guess being around the 12 digit mark, from the way previous terms had grown. But alas I got bogged down in algebra which has exhausted my time.

I started looking at the total number of arrangements of the squares (regardless of lines summing to n(n+1)/2). It's a pretty formula:

(n^2)! / (n!)^n

Which by Sterling's approximation and also hopefully after my simplification comes to :

(2pi)^0.5 . n ^ (n^2+1)
-----------------------
     (2pi.n)^(n/2)

I used to have a neat symbolic equation solver/simplifier called "Scientific Notepad", but alas that doesn't work on Vista so now all I have is my pen. Does anyone know of any decent free or very low cost maths packages that handle symbolic algebra?

Wolfram's simplification


of Sterling's expansion


of