Create the shortest function to print a magic square of given size.

A magic square is a NxN matrix of distinct numbers and the sum of each row, column and diagonal is equal to a constant.

A magic square of size 4 is:

07 12 01 14
02 13 08 11
16 03 10 05
09 06 15 04

And the constant is 34.

The function should be able to handle inputs up to N = 30 and doesn't need to show leading zeroes.

Using Matlab's magic function or similar built-in function is not allowed.

More useful information: http://mathworld.wolfram.com/MagicSquare.html

::Edit::

The output doesn't need to be pretty printed and may contain [](){}, or List/Array delimiters of your language. Although, it should use one line for each row

E.g.

1, 2,
3, 4,

((9,8), 
 (6,7))

[10 2]
[3 456]

PS: The corner case, when N = 2 is undefined behavior as there's no magic square of that size.

Also, the function should complete in less than 1 minute to avoid brute force.

JBernardo

Posted 2011-07-13T02:07:50.413

Reputation: 1 659

Does it have to be pretty-printed, or can the function return a list of lists or similar? – Joey Adams – 2011-07-13T02:16:59.000

@Joey I Added that information – JBernardo – 2011-07-13T03:11:27.887

Bad codegolf example as it is an NP-complete problem unless you're cheating. – Neil – 2011-07-13T16:13:17.940

@Neil Reference? – Matthew Read – 2011-07-13T20:11:18.327

@JBernardo: NP-complete problems can be solved. By calling it NP-complete, I only mean there is no efficient manner of going about solving for a magic square. Though it would seem that I confused magic squares with latin squares, which is NP-complete.

– Neil – 2011-07-14T10:10:43.427

@JBernardo: If you had written what I had wrote, you'd realize I was stating that I was wrong and that I confused magic squares with latin squares. Not just that, but you'd realize that NP-complete does not mean that it cannot be done since I addressed that as well. – Neil – 2011-07-14T13:02:39.047

Does the program have to handle the trivial case where N=1? – Peter Olson – 2011-07-14T13:51:50.163

@Peter Of The Corn Yes. – JBernardo – 2011-07-16T04:40:01.797

Answers

Ruby, 344 characters

q=->n{r=0...n;n%2>0?(m=r.map{[]*n};x=n/2;y=i=0;r.map{r.map{m[y%=n][x%=n]=i+=1;x+=1;y-=1};x-=1;y+=2};m):n<5?[[16,3,2,13],[5,10,11,8],[9,6,7,12],[4,15,14,1]]:(d=q[n/2];r.map{|y|r.map{|x|4*d[b=y/2][a=x/2]-[0,3,2,1,3,0,2,1,3,0,1,2][(n/2%2<1?b<n/4?0:8:a==n/4&&b==n/4?4:a==n/4&&b==n/4+1?0:b<=n/4?0:b==n/4+1?4:8)+y%2*2+x%2]}})}
Q=->n{q[n].map{|s|p s}}

You can use it e.g. like

Q[3]

and the output will be

[8, 1, 6]
[3, 5, 7]
[4, 9, 2]

The solution is not yet fully golfed. Also huge squares are generated reasonably fast. It uses a recursive function q to generate the squares unless n is odd in which case the square is generated directly or n==4 which is hard-coded.

Howard

Posted 2011-07-13T02:07:50.413

Reputation: 23 109

@Franklin I didn't know how to directly calculate the square for N=4 with less chars. And for the other one, the condition N<5 is one char less than N==4. – Howard – 2011-07-16T05:24:12.740

Magic Square Generator in Python, ~~127~~ 106 characters

106 char code

#Works for odd numbers only


n=5
print [[(i+j-1+n/2)%n*n+(i+2*j-2)%n+1for j in range(n)]for i in range(n)]

127 char code

#Works for odd numbers only

n=3
j,A=n/2,[[0]*n for i in[0]*n]
i=c=0
while c<n*n:c=A[i][j]=c+1;i,j=[i+1,[n,i][i>0]-1][c%n>0],[j,[n,j][j>0]-1][c%n>0]
print A

See: http://ajs-handling-problems-in-pythonblog.blogspot.in/2013/10/shortest-magic-square-generator-code-in.html

Coding man

Posted 2011-07-13T02:07:50.413

Reputation: 1 193

[n,i][i] returns list index out of range when i = 2, as it is after the very first iteration. Needs more testing? – primo – 2013-10-17T18:10:39.110

my mistake! updated the code...128 chars – Coding man – 2013-10-18T04:27:32.820

@primo n=3 j,A=n/2,[[0]n for i in[0]n] i=c=0 while c<n*n:c=A[i][j]=c+1;i,j=[i+1,[n,i][i>0]-1][c%n>0],[j,[n,j][j>0]-1][c%n>0] print A – Coding man – 2013-10-18T04:39:11.677

@primo sorry for bad indentation..use the link to see a clean code – Coding man – 2013-10-18T04:50:35.283

I've added the code to your post. I imagine that it was downvoted by someone who thought it was spam. – primo – 2013-10-18T04:52:06.870

Q, 50

Works for odd numbers

{(+)a rotate'(+)(a:((!)x)-1)rotate'x cut 1+(!)x*x}

usage

q){(+)a rotate'(+)(a:((!)x)-1)rotate'x cut 1+(!)x*x} 5
24 1  8  15 17
5  7  14 16 23
6  13 20 22 4 
12 19 21 3  10
18 25 2  9  11

tmartin

Posted 2011-07-13T02:07:50.413

Reputation: 3 917

Magic square generator

Answers

Ruby, 344 characters

Q, 50