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.
[ [ 1, 5, 9 ], [ 6, 7, 2 ], [ 8, 3, 4 ] ]
(falsy) \$\endgroup\$[[8, X1, 6], [X2, 5, X3], [X4, 9, 2]]
)? \$\endgroup\$