Magic Square Challenge

Question

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 square¹:

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.²

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

---

¹ _{Bolded numbers are in incorrect cells.}
² _{Bolded numbers have switched cells.}

Answer 1

CJam, 73 70 bytes

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

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

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

Try it online: permalink for Chrome | permalink for Firefox