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

1.173E+13

1. 38

2. 0.849
   0.995E+13

3. Solution 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;

1. 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

2. 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.

3. 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.

4. 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.

5. 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