# Is magic possible?

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

• Hmm. I think I've seen a solution somewhere.. – Matthew Roh May 6 '17 at 12:21
• Suggested test case to make sure that the diagonals are tested correctly: [ [ 1, 5, 9 ], [ 6, 7, 2 ], [ 8, 3, 4 ] ] (falsy) – Arnauld May 6 '17 at 13:17
• Can we number the placeholders (i.e. [[8, X1, 6], [X2, 5, X3], [X4, 9, 2]])? – Scott Milner May 7 '17 at 0:13
• @Scott sure, feel free... – Stewie Griffin May 7 '17 at 8:45

## 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 ]
]));

# 05AB1E, 45 bytes

Zsgn©>‹®L¹˜Kœ0ªε\¹˜0y.;¹gô©O®øO®Å\O®Å/O)˜Ë}à*


Also uses $$\0\$$ as placeholder. The more $$\0\$$s (or numbers above $$\n^2\$$ ) 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:

Z               # Get the maximum of the (implicit) input-matrix (implicitly flattened)
# (and without popping the matrix)
#  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 8
s              # Swap to get the input-matrix again
g             # Get its length (amount of rows)
#  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 3
n            # Square it
#  i.e. 3 → 9
©           # Store it in the register (without popping)
>‹         # Check if the maximum is <= this squared matrix-dimension
#  i.e. 8 <= 9 → 1 (truthy)
®               # Push the squared matrix-dimension again
L              # Create a list in the range [1, squared_matrix_dimension]
#  i.e. 9 → [1,2,3,4,5,6,7,8,9]
¹             # Push the input-matrix
˜            # Flatten it
#  i.e. [[8,0,6],[0,5,0],[0,0,2]] → [8,0,6,0,5,0,0,0,2]
K           # Remove all these numbers from the ranged list
#  i.e. [1,2,3,4,5,6,7,8,9] and [8,0,6,0,5,0,0,0,2] → [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 y to:
\           #  Remove the implicit y which we don't need yet
¹˜          #  Push the flattened input again
0         #  Push a 0
y        #  Push permutation y
.;      #  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]]
©  #  Save the matrix with all 0s filled in in the register (without popping)
O           #  Take the sum of each row
#   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [15,12,18]
®øO         #  Take the sum of each column
#   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [18,15,12]
®Å\O        #  Take the sum of the top-left to bottom-right main diagonal
#   i.e. [[8,1,6],[3,5,4],[7,9,2]] → 15
®Å/O        #  Take the sum of the top-right to bottom-left main diagonal
#   i.e. [[8,1,6],[3,5,4],[7,9,2]] → 18
)           #  Wrap everything on the stack into a list
#   → [[15,12,18],[18,15,12],15,18]
˜          #  Flatten it
#   i.e. [[15,12,18],[18,15,12],15,18] → [15,12,18,18,15,12,15,18]
Ë         #  Check if all values are equal
#   i.e. [15,12,18,18,15,12,15,18] → 0 (falsey)
}               # After the map:
#  → [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
à              # Check if any are truthy by taking the maximum
#  → 1 (truthy)
*             # And multiply the two checks to verify both are truthy
#  i.e. 1 and 1 → 1 (truthy)
# (and output the result implicitly)


The part ©O®øO®Å\O®Å/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.