Strategies in counting magic squares
For the definitions of terms, see this.
Preparing 2N+2 magic series
To construct a magic square of order N, We need 2N+2 magic series for rows, columns and diagonals which satisfy the following constraints:
Row magic series don't have common elements with each other.
Column magic series don't have common elements with each other.
Each row magic series shares only one element with each column magic series.
Up/down diagonal (candidate) magic series shares only one element with each row/column magic series.
Diagonal (candidate) magic series don't have common elements when N is even, and share only one common element when N is odd.
We generate sets of rows and of columns as sorted sets reserving freedom of shuffling the members of each set. And, at this stage, we allow the elements of diagonal magic series scattered in a square, not in a diagonal line, so we call them 'candidates'.
Excluding duplicates
By definition and for efficiency, we have to avoid duplicates from rotations and reflections. These transformations of order 8 can be expressed by the following three generating transformations:
reflection with respect to the down diagonal line (, rows-columns exchange, or transposition)
horizontal reflection
180deg rotation (or horizontal/vertical simultaneous reflection)
Duplicates from the above 1. and 2. can be eliminated by adopting the following technical constraints, respectively.
Transformation 3. is a part of M-transformations and will be discussed in the last subsection.
Complementary pair
(Inaccurate description was corrected on 2024.06.03. The codes had been correct.)
Most of magic squares have their complementary counterparts and we can save counting efforts by producing only one of a pair. We, however, have to be careful in handling exceptional cases in which the complement of a magic square happens to be equivalent to the original one.
We introduce three cases in which the largest row magic series is
greater than,
less than. or
equal to
the largest complement of row/column magic series.
We can omit counting the case 2 by doubling the count for the case 1 because the cases 1 and 2 transform into each other under the complementary transformation, In the case 3, we just count magic squares without doubling.
Note that all squares in the case 3. are not necessarily self-complementary. You may break down the case 3. into finer cases to reduce redundancy further if you can handle them with low overhead.
An efficient method to find magic squares
Given 2N+2 magic series satisfying the above conditions, we have not yet known whether the diagonal candidate magic series can be aligned correctly. We have to check if magic squares can be constructed using the freedom reserved in the first subsection.
Permuting columns alone always allows us to make the down diagonal candidate aligned diagonal.
Permuting rows and permuting columns conjointly (in the same way as rows) always keeps the down diagonal elements within the right positions.
Thus the final question is:
The answer is “It depends”. We can, however, find a charming necessary condition by utilizing power of symmetry. Up diagonal line is symmetric under the row-column exchange and any conjoint permutations of rows and columns always preserve that symmetry. We, therefore, have the following lemma.
While we cannot simply claim that symmetric patterns are always transformable into the up-diagonal line, it is an easy task to check all symmetric patterns of up-diagonal candidates for a specific small N. We have only
15 such patterns for N=6 and all of them are transformable into the up-diagonal line. Thus, once we find a symmetric up-diagonal candidate, we obtain as many magic squares as the number of
M-transformations, which is 48 for N=6.
As mentioned in the second subsection, duplicates from 180deg rotation should be eliminated, we, therefore, have the multiplicity halved (24 for N=6).
in mathematical terms
Since every element of a diagonal candidate magic series appear only once in every row and in every column, the arrangement of a diagonal candidate corresponds to a permutation of N objects, or an element of the symmetric group SN
Let us denote (the arrangements of) the down and up diagonal candidates as d and u, respectively, which are elements of SN.
Permuting columns to make the down diagonal candidate diagonal corresponds to multiplying by d-1. By this permutation, we get dd-1 = e and ud-1, where e is the identity.
The current arrangement of the up diagonal candidate ud-1 is transformable into the up diagonal line by a conjoint permutation of columns and rows if and only if ud-1 belongs to the same conjugacy class as the up-diagonal (reversed order) permutation does. For N=6, this conjugacy class consists of 15 elements which are just depicted in the figure above.
Practically, we can distinguish the conjugacy class of a permutation by its cycle type, and the cycle type of the reversed order permutation consists of floor(N/2) 2-cycles and (N mod 2) 1-cycle. Since we have already checked that the number of common elements of down and up diagonal candidates equals to (N mod 2), the correct 1-cycle component is already guaranteed. Consequently, all we have to check is that ud-1 does not have any cycles longer than 2, in other words, ( ud-1 ) 2 = e or ud-1 = du-1 = ( ud-1 )T.