Задача

Найти обход конем всей шахматной доски, так чтобы:

1. Ходы образовывали непрерывную цепочку

2. Были посещены все поля по 1 разу с номерами от 1 до 64

3. Суммы номеров клеток обхода в каждом столбце были равны

4. -//- в каждой строке давали сумму 260

5. (*) Маршрут был замкнут (с поля 64 был ход на поле 1)

6. (*) Маршрут был симметричен относительно центра

7. (*) на обеих диагоналях сумма 260
   (*) - необязательное дополнительное требование

История

• Обход с условиями 1,2 решали многие. Рекомендую решить для доски 5х4.

• Для больших досок любой формы с "гладким" периметром метод прост: делать ход на "самую изолированную" клетку. (Количество черных и белых полей должно позволять обход).

• Обход с условиями 1-6 решали 100 лет назад.

• А со всеми условиями 1-7 не встречал.

Теория

• Конь меняет цвет поля при каждом ходе.

• Для доски NxN магическая сумма равна S = N*(N*N+1)/2
  При обходе конем сумма по 1-й из диагоналей всегда четная, а S четная только для N делящихся на 4: 8,12,16...

• Если обход симметричен, то он замкнут! Иначе маршрут состоит из 63 ходов и 32-й ход симметричен сам себе, что для коня неверно.

• Не существует обходов симметричных самим себе относительно вертикали, диагонали или поворота. А для центральной симметрии обходы есть.

• Для каждого маршрута от поля 1 до поля 64 есть обратный маршрут с обратной нумерацией, и в нем сохраняются свойства 1-7 первого маршрута.

• Если посчитать среднее ветвление возможных продалжений на каждой глубине (Метод Монте-Карло), то станет ясна форма дерева перебора. Это не пирамида/елка, а луковица/юла. Самая толстая часть в районе 30-40 ходов. Оптимизировать надо там.

Попытки решения

1. Писал на С резидентную программу под DOS, висевшую на прерывании бездействия системы. Просто случайно искала решение. Не нашла.

2. На Делфи 5 быстро написал перебор всех симметричных вариантов относительно центра. Через 5 минут она сказала, что самое близкое решение имеет диагонали с суммами 256 и 264.
   А для поного перебора всех несимметричных маршрутов надо 300 тыс. лет. (Celeron 800)

3. В августе 2022 взял из чулана XEON-2400 (12 core) RAM 40Gb + W7 + RAD2007 + 2 ящика пива.

Поехали: Алгоритм

Для перебора всех маршрутов с отсечением бесперспективных ветвей задействован рекурсивный метод

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. Ускорение симметрией. (в ~15 раз)

   У доски много симметрий: относительно центра, горизонтали. поворот на 90... Почти для каждой позиции есть 7 симметричных ей. Если добавить симметрию обратного обхода, то число анализируемых позиций снижается почти в 16 раз.
   Оставил в качестве стартовых поля A1, B1,B2, С1,С2,С3, D1,D2,D3,D4 (всего 10, а не 64) (рис 1).
   Ввел понятие допустимых финишных полей и это отсекало симметрию обратного обхода. Для данного стартового поля берутся допустимыми только подходящие по цвету и с Грейдом(рис 1) не менее его.

   Так для стартового поля B1 финишными могут быть все черные поля кроме A1 и H8, так как все маршруты с концом на полях A1 или H8 уже просмотрены при стартовом поле A1.

   А для стартового поля D4 финишными могли быть только D5 и E4. Так как другие поля уже анализировались как стартовые.

2. Ускорение распараллеливанием (в ~10 раз).

   Я взял все варианты первых 10 ходов и отбросил симметричные друг другу. Осталось 1,7 млн.
   Создал управляющий поток BigBoss и расчетные потоки Worker (11 штук). Потоки брали из базы цепочки первых 10 ходов и считали все возможные их продолжения. Синхронизация через Критические Секции, Таймер и Эвенты.
   После этого расчетное время снизилось до 600 лет.

3. Ускорение на свойствах хода коня (в ~100 раз) до 6 лет

   К 30-40 ходу возникали узлы дерева перебора, из которых нельзя двигаться дальше. Например, поля B3 и С2 заняты, а А1 нет.
   Также поля, желающие быть финальными, но их было более 1, либо они не подходили по таблице допустимых финишных полей.
   Ввел проверку в генератор ходов.

4. Ускорение на свойствах магического квадрата (в ~100 раз) до 20 дней Отслеживал суммы в каждом столбце и строке (диагонали было лень). Например, после 49 хода в строке с 7 заполненными полями сумма должна быть между 196 и 214. Наиболее эффективными оказались проверки при 5-х заполненных полях.
   Добавил это в фильтрацию позиций перед генерацией ходов.

5. Ускорение оптимизацией кода (~4 раза) до 5 суток

   Выделил куски кода и замерил время их выполнения.
   Выявил и почистил огрехи.
   Заменил по возможности глобальные переменные на переменные в стеке.
   Понаставил операторов with.
   Протестировал и отключил проверки переполнения и выход индексов за пределы диапазона.

6* Неиспользованные идеи
Битборды и MagicBords.
Выявление 2-х непроходимых соседних столбцов или строк.
Частичные суммы на диагоналях.
Сколько ходов надо сделать для заполнения данной строки/столбца
Ассемблерные вставки и команды POPCNT
Нейросеть на BASIC для ZX-Spectrum 128K

Результаты

• Найдено 158 принципиально разных обхода с условиями 1-4

• Симметричных 18

• Замкнутых 65

• с Условием 7* найдено 0.

• Лучшие обходы имеют суммы по диагоналям не 260, а 256 и 264. Вот один из них:

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,58
30,53,06,49,36,59,12,15
51,08,55,32,13,10,57,34
54,31,52,09,56,33,14,11