Background
A magic square is an n×n
matrix consisting of one of each of the integers from \$1\$ to \$n^2\$ where every row, column, and diagonal sum to the same value. For example, a 3×3 magic square is as follows:
4 9 2
3 5 7
8 1 6
Here, each row, column, and diagonal sum to the magic sum of 15, which can be calculated with the following formula:
$$ n × \frac{n^2 + 1}{2} $$
Even if you didn't have the full n×n
magic square, you could reproduce it without guessing. For example, given just the 4, 9, 2, and 3 of the prior magic square, you could fill
4 9 2 4 9 2 4 9 2 4 9 2 4 9 2 4 9 2
3 _ _ => 3 _ _ => 3 5 _ => 3 5 7 => 3 5 7 => 3 5 7
_ _ _ 8 _ _ 8 _ _ 8 _ _ 8 1 _ 8 1 6
Task
Given a partially-filled magic square, your program or function should output the full magic square.
The input is guaranteed to be part of of a magic square, such that the only deduction necessary to solve it is taking a row, column, or diagonal in which n-1
values are determined and filling in the final entry (without this rule, 4 9 _ / _ _ _ / _ _ _
would be a valid input since only one magic square starts 4 9
, but that would require a more complicated approach or a brute-force of all possibilities).
Input and output may be any reasonable format for a square matrix (n
×n
matrix datatype; string representations; length-n×n
flat array; etc.). In all formats, you may optionally take n
as another input.
You may use any character or value other than _
in the input to represent blanks as long as that value is unmistakable for a possible entry.
Related decision-problem variant: Is Magic Possible?
Sample Testcases
(one newline between input and output; three between cases)
4 9 2
3 5 7
8 1 6
4 9 2
3 5 7
8 1 6
4 9 2
3 _ _
_ _ _
4 9 2
3 5 7
8 1 6
4 9 _
_ 5 _
_ _ _
4 9 2
3 5 7
8 1 6
_ _ _
_ 5 7
_ 1 6
4 9 2
3 5 7
8 1 6
_ 16 13 _
11 5 _ _
7 9 12 6
_ _ _ 15
2 16 13 3
11 5 8 10
7 9 12 6
14 4 1 15
1 23 _ 4 21
15 14 _ 18 11
_ _ _ _ _
20 8 _ 12 6
5 3 _ 22 25
1 23 16 4 21
15 14 7 18 11
24 17 13 9 2
20 8 19 12 6
5 3 10 22 25
n-1
values determined? \$\endgroup\$