10
\$\begingroup\$

A magic square is a square array of numbers with side n consisting of the distinct positive integers 1, 2, ..., n² arranged such that the sum of the n numbers in any horizontal, vertical, or main diagonal line is always the same number, which is known as the magic constant.

Your program must input, through std-in, a number specifying the length of the side of your square, then the numbers in the square. No numbers may be used more than once, no number greater than n² may be used, and all numbers must be greater than 0. The program must determine whether that combination of numbers is a magic square.

\$\endgroup\$

10 Answers 10

4
\$\begingroup\$

CJam, 47 39 35 33 31 bytes

l~/{_1fb_,Y${\(_@=\}%:++\z}2*;=

Takes input like

4 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]

Outputs 1 if magic square, 0 otherwise.

How it works:

l~/                               "Evaluates the input and split the array into chunks"
                                  "of size N where N is the first integer";
   {                      }2*     "Run this code block 2 times";
    _1fb                          "Copy the 2D array and calculate sum of each row of copy";
        _,                        "Copy the array containing sum of each row and get"
                                  "its length. This is equal to N";
          Y${      }%             "Run this code block for each array of the original"
                                  "2D array that we copied from stack";
             \(_                  "Put the length number to top of stack, decrement and"
                                  "copy that";
                @=\               "Take the element at that index from each row and put"
                                  "N back behind at second position in stack";
                     :+           "Take sum of elements of the array. This is sum of"
                                  "one of the diagonals of the 2D array";
                       +          "Push diagonal sum to row sum array";
                        \z        "Bring original array to top and transpose columns";
                             ;    "At this point, the stack contain 3 arrays:"
                                  "  Array with sum of rows and main diagonal,"
                                  "  Array with sum of columns and secondary diagonal and"
                                  "  The original array. Pop the original array";
                              =   "Check if sum of rows + main diagonal array is equal to ";
                                  "sum of columns + secondary diagonal array";

This can be golfed further.

Try it online here

\$\endgroup\$
6
\$\begingroup\$

Python 2: 132 chars

n,l=input()
r=range
print r(1,n*n+1)==sorted(l)*len({sum(l[i::j][:n])for(i,j)in zip(r(n)+r(0,n*n,n)+[0,n-1],[n]*n+[1]*n+[n+1,n-1])})

An example run:

STDIN: 4,[16,3,2,13,5,10,11,8,9,6,7,12,4,15,14,1]
Output: True

The are two things to check:

  1. The sums are the rows, columns, and diagonals are all equal
  2. The elements are a permutation of [1,2,...,n*n].

The first is checked by taking sums of slices corresponding to these subsets. Each row, column, or diagonal is described by its starting value and its displacement. We take the list corresponding slice, truncate to n elements, and sum it. In Python's [start:end:step] notation, rows are [r*n::1], columns are [c::n] and the two diagonals are [0::n+1] and [n-1::n-1]. These are stored as a list of 2*n+2 pairs produced by zip.

We take the sets of sums and check that it has length 1. Also, we sort the input and check that it is the list [1,2,...,n*n]. Actually, we combine both into one check by multiplying sorted(l) by the length of the sum-sets, a check that always fails unless the sum-set has length 1.

\$\endgroup\$
  • \$\begingroup\$ I realized that you can encode a pair (i,j) more efficiently as a single number x, taking i=x%C and j=x/C for some large enough C. Might give that a shot later. \$\endgroup\$ – xnor Oct 17 '14 at 6:18
5
\$\begingroup\$

APL, 35

∧/2=/(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕)

Explanation
x←⎕⍴⍨,⍨⎕ prompts for input, shape it into a matrix, and assign to x
Reverses the matrix left-to-right
x(...) Create a array of matrices: x and x reverse
1 1∘⍉¨ For each of those matrices, take the diagonal
+/↑ form a 2×n matrix of the numbers on those diagonals and sum the rows

⍉x Transpose x
x, then concatenate with x to form a n×2n matrix
+⌿ and sum the columns

(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕) concatenate to form an array of the sums
2=/ check if consecutive pairs equal
∧/ and AND together all those results

\$\endgroup\$
3
\$\begingroup\$

Mathematica 128 125

d = Diagonal; r = Reverse; i = Input[];
Length@Union[Tr /@ Join[p = Partition[i[[2]], i[[1]]], 
t = Transpose@p, {d@p}, {d@t}, {d@r@p}, {d@r@t}]] == 1

Takes input such as

{4,{16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1}}

True

\$\endgroup\$
  • \$\begingroup\$ Surely there's a lot of whitespace that can be removed here \$\endgroup\$ – Beta Decay Oct 17 '14 at 21:12
  • \$\begingroup\$ All of the white space can be removed. I left it there for readability. And I didn't count unnecessary white space. \$\endgroup\$ – DavidC Oct 17 '14 at 23:29
  • \$\begingroup\$ You can do Input[r=Reverse] to save a byte. #&@@ is a byte shorter than [[1]]. You can probably in addition use infix notation for Partition for another byte. And Thread should work instead of Transpose. Alternatively, use this Unicode character as a post fix operator (Mathematica uses it for superscript T for transpose). \$\endgroup\$ – Martin Ender Oct 18 '14 at 0:12
3
\$\begingroup\$

APL 47 32

Using TwiNight's excellent solution and applying some more tweaking:

∧/2=/+⌿(1 1∘⍉∘⌽,1 1∘⍉,⍉,⊢)⎕⍴⍨,⍨⎕

Explanation:

This uses function trains, which were introduced in v14 of the Dyalog interpreter. APL is executed from right to left, ⎕'s are inputs, so first the dimensions, then the vector of numbers.

⎕⍴⍨,⍨⎕ creates the matrix NxN

After that comes the function train which are basically just a sequence of functions (between brackets) applied to the right argument. The functions are:

⊢ Returns just right argument (that is the matrix)

⍉ Transposes the right argument matrix

1 1∘⍉ Returns the diagonal

1 1∘⍉∘⌽ Returns the diagonal of the reversed (horizontally) matrix

All the results are concatenated with the function ","

At this point, the result is a matrix whose columns are then summed (+⌿). The values obtained this way are then checked to be the same with ∧/2=/

I'll leave my old solution here too:

{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)ר⊂M}

takes dimension as left argument, vector of elements as right argument, for example:

4{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)ר⊂M}16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1
1

Can be tried online here: www.tryapl.org

\$\endgroup\$
2
\$\begingroup\$

GolfScript 67 (demo)

~]:q(/q(/zip+[q()/{(\;}%]+[q((/);(;{(\;}%]+{{+}*}%.&,2<q(2?,{)}%-!*
\$\endgroup\$
2
\$\begingroup\$

JavaScript (E6) 194

Using prompt to read input and display output.
Test in console with FireFox >31 (Array.fill is very new)

z=(p=prompt)(n=p()|0).split(' '),u=Array(2*n).fill(e=d=n*(n*n+1)/2),z.map((v,i)=>(r=i/n|0,u[r+n]-=v,u[c=i%n]-=v,d-=v*(r==c),e-=v*(r+c+1==n))),o=!(e|d|u.some(v=>v)),z.sort((a,b)=>a-b||(o=0)),p(o)

Less golfed

n = prompt()|0; // input side length
z = prompt().split(' '); // input list of space separeted numbers  
e = d = n*(n*n+1)/2; // Calc sum for each row, column and diagonal
u = Array(2*n).fill(e), // Init check values for n rows and n columns

z.map( (v,i) => { // loop on number array 
  r = i / n | 0; // row number
  c = i % n; // column number
  u[r+n] -= v; // subtract current value, if correct it will be 0 at loop end
  u[c] -= v; 
  if (r==c) d -= v; // subtract if diagonal \
  if (r+c+1==n) e -=v; // subtract if diagonal /
}),
o=!(e|d|u.some(v=>v)); // true if values for rows, cols and diags are 0
z.sort((a,b)=>a-b||(o=0)); // use sort to verify if there are repeated values in input
alert(o);
\$\endgroup\$
2
\$\begingroup\$

Pyth, 24 30 bytes

&q1l{sM++JcEQCJm.e@bkd_BJqSlQS

Try it online here.

&q1l{sM++JcEQCJm.e@bkd_BJqSlQSQ   Implicit: Q = evaluated 1st input (contents), E = evaluated 2nd input (side length)
                                  Trailing Q inferred
          cEQ                     Chop E into pieces or length Q
         J                        Store in J
                      _BJ         Pair J with itself with rows reversed
               m                  Map the original and it's reverse, as d, using:
                .e   d              Map each row in d, as b with index k, using:
                  @bk                 Get the kth element of b
                                  The result of this map is [[main diagonal], [antidiagonal]]
        +J                        Prepend rows from J
       +     CJ                   Prepend columns from J (transposed J)
     sM                           Sum each
    {                             Deduplicate
   l                              Length
 q1                               Is the above equal to 1?
&                                 Logic AND the above with...
                          SlQ     ... is the range [1-length(Q)]...
                         q        ... equal to...
                             SQ   ... sorted(Q)

Edit: fixed a bug, thanks to @KevinCruijssen for letting me know :o)

\$\endgroup\$
  • \$\begingroup\$ This outputs True for magic squares with numbers that are too big, or not all unique. I.e. 4 and [12,26,23,13,21,15,18,20,17,19,22,16,24,14,11,25] or 4 and [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] output both True. (Almost all existing answer have the same problem though, but since they are posted over 4 years ago I didn't bother to correct their mistakes in a comment.) \$\endgroup\$ – Kevin Cruijssen Jan 21 at 14:46
  • \$\begingroup\$ @KevinCruijssen Damn, I got so focused on verifying the sums that I forgot about the other requirements... I'm such a dope \$\endgroup\$ – Sok Jan 21 at 15:11
1
\$\begingroup\$

LUA 186 Chars

s=io.read(1)v=io.read(2)d=0 r=0 for i=1,#s do t=0 for j = 1, #s do t=t+s[i][j]end d=d+s[i][i] r=r+s[i][#s-i+1]if t ~= v then o=true end end if d~=v and r~= v then o=true end print(not o)
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 24 bytes

ô©O®øO®Å\O®Å/O)˜Ë²{¹nLQ*

Input format: 4\n[2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]. Outputs 1/0 for truthy/falsey respectively.

Try it online or verify some more test cases.

Explanation:

ô       # Split the 2nd (implicit) input into parts of a size of the 1st (implicit) input
        #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15] and 4
        #   → [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
 ©      # Store it in the register (without popping)
  O     # Take the sum of each row
        #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [34,34,34,34]
®       # Push the matrix from the register again
 ø      # Zip/transpose; swapping rows/columns
        #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
        #   → [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]]
  O     # Sum each inner list again
        #  i.e. [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]] → [34,34,34,34]
®       # Push the matrix from the register again
 Å\     # Get the top-left to bottom-right main diagonal of it
        #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [2,5,12,15]
   O    # Sum it together
        #  i.e. [2,5,12,15] → 34
®       # Push the matrix from the register again
 Å/     # Get the top-right to bottom-left main diagonal of it
        #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [3,8,9,14]
   O    # Sum it together
        #  i.e. [3,8,9,14] → 34
)       # Wrap everything on the stack into a list
        #  → [[34,34,34,34],[34,34,34,34],34,34]
 ˜      # Flatten this list
        #  i.e. [[34,34,34,34],[34,34,34,34],34,34] → [34,34,34,34,34,34,34,34,34,34]
  Ë     # Check if all values are equal to each other
        #  i.e. [34,34,34,34,34,34,34,34,34,34] → 1 (truthy)
²       # Push the second input again
 {      # Sort it
        #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]
        #  → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
  ¹n    # Push the first input again, and take its square
        #  i.e. 4 → 16
    L   # Create a list in the range [1, squared_input]
        #  i.e. 16 → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
     Q  # Check if the two lists are equal
        #  i.e. [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
        #   and [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] → 1 (truthy)
*       # Check if both checks are truthy by multiplying them with each other
        #  i.e. 1 and 1 → 1
        # (and output the result implicitly)
\$\endgroup\$

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.