Magic Square Challenge
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