20
\$\begingroup\$

A magic square is an n-by-n square grid, filled with distinct positive integers in the range 1,2,...n^2, such that each cell contains a different integer and the sum of the integers in each row, column and diagonal is equal.

Your task is to take an n-by-n matrix consisting of positive numbers, and a placeholder character for empty cells (I'll use 0, but you can use any non-numeric character or datatype you like), and determine if it's possible to make a magic square by filling in the missing numbers

The matrix will be at least 2-by-2, and at most 10-by-10. The smallest possible non-trivial magic square is 3-by-3. The numbers in the input matrix might be higher than n^2, and it's possible that all cells are filled.

Test cases:

2   2
2   0
False

8   0   6
0   5   0
0   9   2
True

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

10   0   1
 0   5   9
 3   7   5
False

99    40    74     8    15    51     0    67     0     1
 0    41    55    14     0    57    64     0    98     0
81    47    56    20    22    63    70    54     0    88
 0    28     0    21     0    69    71    60    85    19
 0    34     0     2     9    75    52    61     0    25
24    65    49     0    90    26    33    42    17    76
 0     0    30    89    91     0    39    48     0    82
 6    72    31    95     0    38    45    29     0    13
12    53     0    96    78     0     0     0    10    94
18    59    43    77     0     0    27    36     0   100
True
\$\endgroup\$
4
  • \$\begingroup\$ Hmm. I think I've seen a solution somewhere.. \$\endgroup\$ – Matthew Roh May 6 '17 at 12:21
  • 1
    \$\begingroup\$ Suggested test case to make sure that the diagonals are tested correctly: [ [ 1, 5, 9 ], [ 6, 7, 2 ], [ 8, 3, 4 ] ] (falsy) \$\endgroup\$ – Arnauld May 6 '17 at 13:17
  • \$\begingroup\$ Can we number the placeholders (i.e. [[8, X1, 6], [X2, 5, X3], [X4, 9, 2]])? \$\endgroup\$ – Scott Milner May 7 '17 at 0:13
  • \$\begingroup\$ @Scott sure, feel free... \$\endgroup\$ – Stewie Griffin May 7 '17 at 8:45
5
\$\begingroup\$

JavaScript (ES6), 270 268 bytes

Takes the matrix as a 2D array. Returns 0 or 1.

a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

Test cases

This is definitely too slow for the last test case. :-(

let f =

a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

console.log(f([
  [ 2,  2 ],
  [ 2,  0 ]
]));

console.log(f([
  [ 8,  0,  6 ],
  [ 0,  5,  0 ],
  [ 0,  9,  2 ]
]));

console.log(f([
  [ 16,   2,   3,  13 ],
  [  5,  11,  10,   8 ],
  [  9,   7,   6,  12 ],
  [  4,  14,  15,   1 ]
]));

console.log(f([
  [ 10,  0,  1 ],
  [  0,  5,  9 ],
  [  3,  7,  5 ]
]));

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 45 38 bytes

gn¹à@¹˜āsKœ0ªεΘr.;¹gôD©ø®Å\®Å/)O˜Ë}à*

Also uses \$0\$ as placeholder. The more \$0\$s in the input, the slower the program is. Size of the matrix doesn't matter that much (a 10x10 matrix with three \$0\$s runs quite a bit faster than a 3x3 matrix with seven \$0\$s).

Could have been 4 bytes less, but there is currently a bug in the builtin .; with 2D lists. : and .: work as expected, but .; doesn't do anything on 2D lists right now.. hence the work-around of ˜ and ¹gô to flatten the matrix; use .; on the list; and transform it back into a matrix again.

Try it online or verify some more test cases. (NOTE: Last test case of the challenge description is not included, because it has way too many 0s..)

Explanation:

g          # Get the length of the (implicit) input-matrix (amount of rows)
           #  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 3
 n         # Square it
           #  → 9
  ¹        # Push the input-matrix again
   à       # Pop and push its flattened maximum
           #  → 8
    @      # Check if the squared matrix-dimension is >= this maximum
           #  → 9 => 8 → 1 (truthy)
¹          # Push the input-matrix again
 ˜         # Flatten it
           #  → [8,0,6,0,5,0,0,0,2]
  ā        # Push a list in the range [1,length] (without popping)
           #  → [1,2,3,4,5,6,7,8,9]
   s       # Swap so the flattened input is at the top of the stack again
    K      # Remove all these numbers from the ranged list
           #  → [1,3,4,7,9]
œ          # Get all possible permutations of the remaining numbers
           # (this part is the main bottleneck of the program;
           #  the more 0s and too high numbers, the more permutations)
           #   i.e. [1,3,4,7,9] → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
 0ª        # Add an item 0 to the list (workaround for inputs without any 0s)
           #  i.e. [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]] 
           #   → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1],"0"] 
ε          # Map each permutation to:
 Î         #  Push 0 and the input-matrix
  ˜        #  Flatten the matrix again
   r       #  Reverse the items on the stack, so the order is [flat_input, 0, curr_perm]
    .;     #  Replace all 0s with the numbers in the permutation one by one
           #   i.e. [8,0,6,0,5,0,0,0,2] and [1,3,4,7,9]
           #    → [8,1,6,3,5,4,7,9,2]
      ¹g   #  Push the input-dimension again
        ô  #  And split the flattened list into parts of that size,
           #  basically transforming it back into a matrix
           #   i.e. [8,1,6,3,5,4,7,9,2] and 3 → [[8,1,6],[3,5,4],[7,9,2]]
 D         #  Duplicate the current matrix with all 0s filled in
  ©        #  Store it in variable `®` (without popping)
   ø       #  Zip/transpose; swapping rows/columns of the top matrix
           #   → [[8,3,7],[1,5,9],[6,4,2]]
 ®Å\       #  Get the top-left to bottom-right main diagonal of `®`
           #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [8,5,2]
 ®Å/       #  Get the top-right to bottom-left main diagonal of `®`
           #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [6,5,7]
    )      #  Wrap everything on the stack into a list
           #   → [[[8,1,6],[3,5,4],[7,9,2]],
           #      [[8,3,7],[1,5,9],[6,4,2]],
           #      [8,5,2],
           #      [6,5,7]]
     O     #  Sum each inner list
           #   → [[15,12,18],[18,15,12],15,18]
      ˜    #  Flatten it
           #   → [15,12,18,18,15,12,15,18]
       Ë   #  Check if all values are the same
           #   → 0 (falsey)
}à         # After the map: Check if any are truthy by taking the maximum
           #  → 1 (truthy)
*          # And multiply it to the check we did at the start to verify both are truthy
           #  → 1 (truthy)
           # (after which the result is output implicitly)

The part D©ø®Å\®Å/)O˜Ë is also used in my 05AB1E answer for the Verify Magic Square challenge, so see that answer for a more in-depth explanation about that part of the code.

\$\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.