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.

Your Task

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.
CJam, 73 70 bytes

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


The above code is 80 bytes long and qualifies for the bonus.

Time complexity is O(n!) for n&times;n squares. For 9&times;9, this translates to 7 seconds on my machine.

Try it online: permalink for Chrome | permalink for Firefox