6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does it have to be pretty-printed, or can the function return a list of lists or similar? \$\endgroup\$ – Joey Adams Jul 13 '11 at 2:16
  • \$\begingroup\$ @Joey I Added that information \$\endgroup\$ – JBernardo Jul 13 '11 at 3:11
  • \$\begingroup\$ Bad codegolf example as it is an NP-complete problem unless you're cheating. \$\endgroup\$ – Neil Jul 13 '11 at 16:13
  • \$\begingroup\$ @Neil Reference? \$\endgroup\$ – Matthew Read Jul 13 '11 at 20:11
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Jul 14 '11 at 10:10
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Jul 16 '11 at 5:24
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ [n,i][i] returns list index out of range when i = 2, as it is after the very first iteration. Needs more testing? \$\endgroup\$ – primo Oct 17 '13 at 18:10
  • \$\begingroup\$ my mistake! updated the code...**128 chars** \$\endgroup\$ – Coding man Oct 18 '13 at 4:27
  • \$\begingroup\$ @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 \$\endgroup\$ – Coding man Oct 18 '13 at 4:39
  • \$\begingroup\$ @primo sorry for bad indentation..use the link to see a clean code \$\endgroup\$ – Coding man Oct 18 '13 at 4:50
  • \$\begingroup\$ I've added the code to your post. I imagine that it was downvoted by someone who thought it was spam. \$\endgroup\$ – primo Oct 18 '13 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.