# 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.   ## 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          38,400         816:45:36
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
``` 