An Efficient Algorithm for Constructing all Magic Squares of Order Four

Like the Sudoku puzzle, the magic square involves recreational mathematical contexts and has attracted considerable attention. Although there are many researches available, few of them could provide an efficient solution for constructing all magic squares of order four. In this paper, we firstly formulate constraints of magic squares of order four by a collection of linear equations and provide an intuitive but computationally infeasible solution to these equations. Then, we propose an efficient algorithm for constructing all magic squares of order four. The algorithm transforms solving these equations into finding all possible permutations of seven free variables from sixteen consecutive natural integers based on the Gaussian Elimination method. Furthermore, we show the effectiveness of the proposed algorithm by 48 magic squares in the experimental section.