Knight Move Magic Squares - Order 6

Description

In row 1, let A be the sum of the three cells labelled a, and B the sum of the three cells labelled b.
If the square is magic, V zigzagA3:


        . the sum of aaa in each row and column is A
        . the sum of bbb in each row and column is B
        . A + B = Σ,(magic constant)

There are 33,550,848 order 6 knight move magic squares. Here is a small sample.

Distribution

These distribution charts are based on squares of numbers 1 .. 36.

L C D.txt

aaa Sum D.txt

Construction

The squares were made with program Order6ZigZagA3. Total run time was 14½ hours.

Algorithm

Phase I, (13 hours)

Make 3x6 rectangles:

For 6x6 squares with pattern:

                   a b a b a b
                   b a b a b a
                   a b a b a b
                   b a b a b a
                   a b a b a b
                   b a b a b a

where
the sum of a cells in each row and in each column is the same, (A), and
the sum of b cells in each row and in each column is the same, (B = Σ-A):

Make all 3x6 rectangles of the values 0 .. 35, corresponding to the
a's and/or b's of the 6x6 square:

                 x0  x1  x2
                 x3  x4  x5
                 x6  x7  x8
                 x9 x10 x11
                x12 x13 x14
                x15 x16 x17

where each row has the same sum, and alternating column values have this sum,
e.g., x0+x6+x12 = x3+x9+x15 = x0+x1+x2.

Check the 18 values not included in the rectangle to determine if they can make
any similar rectangle with sum B = Σ-A.
This step is crucial, reducing the second phase of the algorithm
from many years of computation to only 1½ hours.

If x17 > x0 and \diagonal x0+x3+x7+x10+x14+x17 = Σ, save in file AA.
If x15 > x2 and /diagonal x2+x5+x7+x10+x12+x15 = Σ, save in file BA.

For each file, write a 64-bit vector representing the values in the rectangle.
For A files, write x0, x1, x3, x4, x6, x7, x9, x10.
For B files, write x1, x2, x4, x5, x7, x8, x10, x11.
The remaining values can be computed.
For efficient I/O write the bit vector and 8 1-byte values as 2 64-bit hexadecimals.

Phase II, (1½ hours)

Combine the AA and BB rectangles:

For each rectangle in each AA file, for each rectangle in its corresponding BB file,
if x2 > x0 and the intersection of the bit vectors is empty, make the square.

Check

The numbers of squares made by these checks matched the final results. Here x0 and A sum refer to number range 1 .. 36.

Check 1

All squares were made for a few big x0 values by a backtracking algorithm, (optimized for the special symmetry):

                      
             x0         squares           time
            ----        -------        ----------
             26         (26,112)       (399:20:13)   still running < 38,400
             27          25,344         446:20:51
             28           6,912         251:11:32
             29           3,072         132:04:57
             30               0          62:22:18
             31               0          24:55:32
             32               0           7:53:58
             33               0           1:30:14

Check 2

Before the "crucial" step was added to phase I, all squares were made for a few small A AA file, BB file combinations:

                      
              A           squares          time
             ---         ---------      ----------
              33           71,424         0:00:05
              34           20,736         0:00:21
              35           20,736         0:01:06
              36           82,944         0:08:46
              37           19,712         0:13:08
              38                0         0:45:22
              39           20,736         3:41:03
              40                0         9:35:00
              41                0        25:34:47