2
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – orlp Aug 7 '15 at 15:37
  • 2
    \$\begingroup\$ Do we have to handle any dimensions or will it always be 5x5? \$\endgroup\$ – Martin Ender Aug 7 '15 at 15:47
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Geobits Aug 7 '15 at 15:52
  • 2
    \$\begingroup\$ Not that it matters, but there are at most 49! distinct permutations of a 7x7 square. \$\endgroup\$ – Dennis Aug 7 '15 at 17:43
  • 1
    \$\begingroup\$ @Dennis 49! = 608281864034267560872252163321295376887552831379210240000000000. 49^49 = 66009724686219550843768321818371771650147004059278069406814190436565131829325062449. \$\endgroup\$ – orlp Aug 7 '15 at 18:52
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice work, +1. As a complete aside, the permalink for Chrome works in Safari but the Firefox one does not. \$\endgroup\$ – Alex A. Aug 8 '15 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.