Magic Squares

[blue_girl]

For creating magic squares, there are algorithms to make odd and doubly even (divisible by 4) squares. However, there are no know methods of making a singly even magic square without going through all of the permutations. This brute force method seems very inefficient (and very processor-consuming). The number of permutations for a board are N!, where N is the number of slots on the board. Thus, a 3x3 grid would have 9 values, so 9! (362,880) variations. However, the smallest singly even magic square is 6x6, which entails 3.71993327 × 10⁴¹ combinations to be tested.

My question is this: does anybody have any ideas for ways to cut down on the number of permutations that need to be tested? My computer is by far lacking the computing power to test out a 6x6 grid, let alone anything larger.


(PS: I wasn't sure whether this should go here or The Help Desk. Hopefully I chose correctly. Also, I found no duplicate threads in either place by searching for "magic square.")

[carletronicon]

Hmm... for the first row, there are 36 * 35 * 34 * 33 * 32 different possibilities (some of which will fail, i.e. if you pick 1,2,3,4,5, the 6th # ends up needing to be bigger than 36 to make them add up). Second row is 30 * 29 * 28 * 27 * 26 possibilities; the 6th row is forced by what's left and by needing to make each column add up and so I calculate just doing that will reduce it down to 10^32 possibilities. That's unfortunately still much greater than 2^80

[Who, me?]

Hm, not what i'm familiar with, but here's my thoughts, even if they may offer no new insights
--

of an n x n magic square

You can split it into four sub squares that all have the same sum

When constructed into a magic square, these sub squares would have to have complementary row sums and column sums, which is made easier by the fact that the sub-squares have the same sum

Once complementary rows are made for two pairs of subsquares, then we have to make compliments of their columns, which would then be just switching numbers in their rows.

Hmm, this would still be NP-complete though... (subset sum problem)

-

Or, a simpler analysis of how to do it, is to again divide it into four squares with the same sum, and then make magic squares out of them. They will be guaranteed to be odd sized squares, and any square made of them would be guaranteed to be also a magic square.

-

Well, goodluck

[Sandor]

For creating magic squares, there are algorithms to make odd and doubly even (divisible by 4) squares. However, there are no know methods of making a singly even magic square without going through all of the permutations.

I'm not sure about that. This page appears to disagree with you: http://www.grogono.com/magic/6x6.php, as does this one: http://en.wikipedia.org/wiki/Magic_squa ... er_of_rows

[blue_girl]

Hmm... for the first row, there are 36 * 35 * 34 * 33 * 32 different possibilities (some of which will fail, i.e. if you pick 1,2,3,4,5, the 6th # ends up needing to be bigger than 36 to make them add up). Second row is 30 * 29 * 28 * 27 * 26 possibilities; the 6th row is forced by what's left and by needing to make each column add up and so I calculate just doing that will reduce it down to 10^32 possibilities. That's unfortunately still much greater than 2^80

Yes, that was the problem I had been running into...'tis all figured out now, having found a working algorithm.

For creating magic squares, there are algorithms to make odd and doubly even (divisible by 4) squares. However, there are no know methods of making a singly even magic square without going through all of the permutations.

I'm not sure about that. This page appears to disagree with you: http://www.grogono.com/magic/6x6.php, as does this one: http://en.wikipedia.org/wiki/Magic_square#Medjig-method_of_constructing_magic_squares_of_even_number_of_rows

Thank you, Sandor. Once I was able to ask my comp sci teacher about it in class, I was able to determine that there is, in fact, an algorithm. Previously, he had (mistakenly) told me that that there was none. I should have double checked the validity of his statement earlier.

[sourmìlk]

We don't know that NP-Complete problems can't be solved in polynomial time. Why don't you just find the polynomial time solution, assuming there is one? I hear that the Clay Mathematics Institute is offering good money if you do.