Constructing magic squares: an integer constraint satisfaction problem and a fast approach

Abstract Magic squares are a fascinating mathematical challenge that has intrigued mathematicians for centuries. Given a positive (and possibly large) integer $$ n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> , one of the main challenges that still remains is to find, within a reasonable computational time, a magic square of order $$ n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> , that is, a square matrix of order $$ n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> with unique integers from $$ a_{\min } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>a</mml:mi> <mml:mo>min</mml:mo> </mml:msub> </mml:math> to $$ a_{\max } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>a</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:math> , such that the sum of each row, column, and diagonal equals a constant $$ \mathcal {C}(A) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>(</mml:mo> <mml:mi>A</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . In this work, we first present an integer constraint satisfaction problem for constructing a magic square of order $$ n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> . Nonetheless, the solution time of this problem grows exponentially as the order increases. To overcome this limitation, we also propose a fast approach that constructs magic squares depending on whether $$ n $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> is odd, singly even, or doubly even. Moreover, we provide a proof of the correctness of this novel approach. Our numerical results show that our method can construct magic squares of order up to 70 000 in less than 140 seconds, demonstrating its efficiency and scalability.