# IT fun. 1. Bypassing the chessboard with a knight to obtain a Magic square

#### Task

Find the knight’s traversal of the entire chessboard so that:

The moves formed a continuous chain

All fields were visited 1 time with numbers from 1 to 64

The sums of the cell numbers of the bypass in each column were equal

-//- in each line they gave the sum 260

The route was closed (from field 64 there was a move to field 1)

The route was symmetrical about the center

on both diagonals the sum is 260

– optional additional requirement

Story

#### Bypass with conditions 1.2 was solved by many. I recommend solving for a 5×4 board.

For large boards of any shape with a “smooth” perimeter, the method is simple: move to the “most isolated” square. (The number of black and white fields should allow for bypass).

Bypass with conditions 1-6 was solved 100 years ago.

And with all conditions 1-7 did not meet.Theory

The knight changes the color of the field with each move.

For an NxN board, the magic sum is S = N*(N*N+1)/2

When the knight walks, the sum along the 1st of the diagonals is always even, and S is even only for N divisible by 4: 8,12,16…

If the bypass is symmetrical, then it is closed! Otherwise, the route consists of 63 moves and the 32nd move is symmetrical to itself, which is not true for the knight. | There are no walks that are symmetrical to themselves with respect to vertical, diagonal, or rotation. And there are detours for central symmetry. | For each route from field 1 to field 64, there is a reverse numbered route, and it retains properties 1-7 of the first route. |

If we calculate the average branching of possible extensions at each depth (Monte Carlo method), then the shape of the enumeration tree becomes clear. This is not a pyramid / Christmas tree, but an onion / top. The thickest part is in the region of 30-40 moves. You need to optimize there. | Deep | branched |

Width | thirty | 1.419 |

1.525E+13 | 31 | 1.103 |

1.682E+13 | 32 | 1.219 |

2.049E+13 | 33 | 0.946 |

1.939E+13 | 34 | 1.064 |

2.062E+13 | 35 | 0.825 |

1.701E+13 | 36 | 0.947 |

1.610E+13 | 37 | 0.728 |

#### 1.173E+13

38

0.849

0.995E+13Solution attempts

#### Wrote in C a resident program under DOS, hanging on a system idle interrupt. Just randomly looking for a solution. Did not find.

On Delphi 5, I quickly wrote an enumeration of all symmetrical options relative to the center. After 5 minutes, she said that the closest solution has diagonals with sums of 256 and 264.

```
Type TBoard = record //доска по которой прыгает конь
C:array[0..64] of integer;//1-непосещ-ое поле,0-посещ
CntCol,CntRow:array[0..7] of integer;//0..8; счетчики своб полей
SumCol,SumRow:array[0..7] of integer;//-64..260; недостающие до 260 суммы
IS_END:array[0..63] of boolean;//разрешенные финишные поля
procedure Init;
procedure InitEND(n:integer;bCycle:boolean=False);
end;
procedure TSolver.GO(f,e,d:integer);
///f - поле на которое ступает конь (нумерация 0..63)
///e - финишное поле, если уже выявлен единственный претендент
///d - глубина дерева (номер хода)
var n, NCol, NRow, NDig, C1, Rest:integer;
Ch:record Next, F64:array[0..7] of integer; CntCh:integer;end;///ходы
function GetST:boolean;//генерируем возможные ходы коня
begin ..... end;
begin
with Board do begin
///считаем колонку, число своб полей и нехватку до 260 суммы по столбцу
NCol:=f mod 8;C1:=CntCol[NCol]-1;Rest:=SumCol[NCol]-D;
if (C1>3) or OK_SUM[Rest,D,C1] then begin ///сумма хороша?
CntCol[NCol]:=C1;SumCol[NCol]:=Rest;
NRow:=f div 8;/// считаем строку и ее параметры
C1:=CntRow[NRow]-1;Rest:=SumRow[NRow]-D;
if (C1>3) or OK_SUM[Rest,D,C1] then begin
CntRow[NRow]:=C1;SumRow[NRow]:=Rest;
C[f]:=0;LOG[D-1]:=f;///ставим коня (:=0)
if D=62 then Finishing(e)
else if GetST then with Ch do /// делаем детей
for n:=CntCh downto 0 do
GO(Next[n],F64[n],D+1);
C[f]:=1;inc(SumRow[NRow],D);inc(CntRow[NRow]);///восстановление
end;//if Row
inc(CntCol[NCol]);inc(SumCol[NCol],D);///восстановление
end;//if Col
end;//with
end;
```

The recursive method is used to enumerate all routes with pruning of unpromising branches

Fig 1, groups (grades) of symmetrical fields

Fig 1, groups (grades) of symmetrical fields

Fig 1, groups (grades) of symmetrical fields__Symmetry acceleration. (~15 times)__The board has many symmetries: relative to the center, horizontal. rotation by 90… For almost every position there are 7 symmetrical to it. If we add the backward traversal symmetry, then the number of analyzed positions decreases by almost 16 times.I left A1, B1, B2, C1, C2, C3, D1, D2, D3, D4 as starting fields (only 10, not 64) (Fig. 1).

Introduced the concept

allowed finishing fields

and this cut off the symmetry of the backward traversal. For a given starting field, only those that are suitable in color and with a Grade (Fig. 1) not less than it are taken as acceptable.

So for the starting field B1, all black fields except A1 and H8 can be finished, since all routes with an end on the fields A1 or H8 have already been viewed with the starting field A1.

And for the starting field D4, only D5 and E4 could finish. Since other fields have already been analyzed as starting ones.Acceleration by parallelization (~10 times).

I took all the variations of the first 10 moves and discarded those that were symmetrical to each other. 1.7 million left.

Created the BigBoss control flow and Worker settlement flows (11 pieces). The flows took the chains of the first 10 moves from the base and counted all their possible continuations. Synchronization via Critical Sections, Timer and Events.

After that, the estimated time dropped to 600 years.Acceleration on the properties of the horse’s move (~100 times) up to 6 years

By the 30-40th move, nodes of the enumeration tree appeared, from which it was impossible to move further. For example, fields B3 and C2 are occupied, but A1 is not.Also fields that wanted to be final, but there were more than 1 of them, or they did not fit according to the table of acceptable finishing fields.

Introduced a check into the move generator.

Acceleration on the properties of the magic square (~100 times) up to 20 days Tracked the sums in each column and row (the diagonal was too lazy). For example, after 49 moves in a row with 7 filled fields, the sum should be between 196 and 214. The most effective checks turned out to be with 5 filled fields.

Added this to position filtering before move generation.

Acceleration by code optimization (~4 times) up to 5 days

I selected pieces of code and measured their execution time.

Found and corrected bugs.

Replaced global variables with stack variables whenever possible.

Set up with statements.

Tested and disabled overflow checks and index out of range checks.

6* Unused ideas

Bitboards and MagicBords.

Identification of 2 impassable adjacent columns or rows.

#### Partial sums on diagonals.

How many moves do you need to make to complete this row/column

Assembly inserts and POPCNT commands

Neural network on BASIC for ZX-Spectrum 128K

results

Found 158 fundamentally different bypasses with conditions 1-4

The best walks have diagonal sums not 260, but 256 and 264. Here is one of them:

Figure 2, Closest to desired

Figure 2, Closest to desired

Figure 2, Closest to desired

43,46,01,24,41,20,63,22

02,25,42,45,64,23,40,19

47.44.27.04.17.38.21.62

26.03.48.37.28.61.18.39

07,50,29,60,05,16,35,5830,53,06,49,36,59,12,1551,08,55,32,13,10,57,3454,31,52,09,56,33,14,11