# Magic Square Challenge

For the purpose of this question, a magic square is an n×n square of (not necessarily distinct) positive integers, where all rows, columns, and main diagonals add to a "magic constant" m.

Create a function or full program that, given the magic number m and a list representing a square with at most one wrong number in each row and column, will output a list with the entries rearranged to represent a correct square. Your program will be expected to handle any solvable square of any size. Your program should take less than twenty minutes for n=7 or smaller. Assume that all input is solvable.

### Example Input (list, m)

[16, 16, 11, 9, 14, 17, 9, 29, 13, 1, 15, 5, 6, 16, 15, 7, 3, 17, 11, 12, 14, 17, 3, 8, 6], 58


which represents this square1:

16 16 11 09 14
17 09 29 13 01
15 05 06 16 15
07 03 17 11 12
14 17 03 08 06

A compliant solution has to solve the following 7x7 square within the time limit.

[31, 19, 10, 13, 14, 32, 15, 6, 21, 17, 22, 30, 17, 7, 17, 30, 17, 24, 17, 11, 8, 7, 22, 33, 13, 15, 17, 11, 14, 16, 21, 22, 13, 11, 29, 16, 13, 3, 19, 12, 12, 43, 27, 13, 19, 13, 20, 18, 11], 123


### Example Output

For the first test case, this is the only correct solution.

[16, 16, 3, 9, 14, 6, 9, 29, 13, 1, 15, 5, 6, 17, 15, 7, 11, 17, 11, 12, 14, 17, 3, 8, 16]


For a bonus of -10, format your output into a square and pad single digits with zeroes as below.2

16 16 03 09 14
06 09 29 13 01
15 05 06 17 15
07 11 17 11 12
14 17 03 08 16

1 Bolded numbers are in incorrect cells.
2 Bolded numbers have switched cells.

• There is no well-defined answer. I might as well always print out the same solved magic square, because I can argue that I corrected the input to it.
– orlp
Aug 7, 2015 at 15:37
• Do we have to handle any dimensions or will it always be 5x5? Aug 7, 2015 at 15:47
• The golfiest approach I can think of is going to be sheer brute force on permutations. Is there a time constraint, or is this okay? Aug 7, 2015 at 15:52
• Not that it matters, but there are at most 49! distinct permutations of a 7x7 square. Aug 7, 2015 at 17:43
• @Dennis 49! = 608281864034267560872252163321295376887552831379210240000000000. 49^49 = 66009724686219550843768321818371771650147004059278069406814190436565131829325062449.
– orlp
Aug 7, 2015 at 18:52

q~:Q,mQ:Le!{QL/.{1$W$W*t_:+W*t}:Te_$Q$=Tz{W%_L,.=a\}2*++::+)-!*}=&T"%02d "ffe%N*