Programming: theory and practice by alexBlack


Главная Эксперименты Утилиты Компоненты Что почитать Контакты
Главная
Эксперименты 
Non-crossing knight tours

О количестве незамкнутых маршрутов коня

Утилиты

Компоненты

Контакты












О количестве незамкнутых маршрутов коня







Содержание







В 1997 Brandan D. McKay посчитал[1] количество замкнутых путей коня на 
доске 8x8. Для незамкнутых путей известна только оценка количества[2]. 
В сети удалось найти страничку[3], где Guenter Stertenbrink приводит данные 
по количеству путей для различных досок, включая 7x7. 




Количество открытых путей коня для доски 7x7 составляет 82787609160.
Это без учета направления. С учетом направления их в два раза больше и 
равно 165575218320. 




Количество открытых путей коня для доски 8x8 равно 9795914085489952
или с учетом направления 19591828170979904. 




Далее описан алгоритм, который был использован для подсчета количества 
и приведены результаты.




Алгоритм

После нескольких экспериментов оказалось, что даже для доски 7x7 посчитать 
количество маршрутов затруднительно - не хватает ни времени, ни памяти. 
Не найдя ничего лучше, я вернулся к делению доски на части. Описаны как 
минимум два варианта такого деления: в уже упомянутой статье McKay и в 
более ранней статье[4]. Последний вариант разбиения также рассматривается 
в книге[5]. Здесь описан еще один вариант деления доски на части 
применительно к открытым путям (он немного отличается в деталях). 




Сначала разделим открытые пути на группы задавая координаты начала 
и конца пути. Количество путей для каждой такой группы будем считать отдельно.
Эта идея тоже не нова[6]. Например, для доски 6x6 имеем 45 
вариантов: 













y1x1y2x2kcounty1x1y2x2kcounty1x1y2x2kcounty1x1y2x2kcount

0
0
0
1
8
46666
0
0
0
3
8
20227
0
0
0
5
4
83646
0
0
1
2
8
9862

0
0
1
4
8
27510
0
0
2
3
8
8424
0
0
2
5
8
13687
0
0
3
4
8
7496

0
0
4
5
8
44725
0
1
0
2
8
11342
0
1
0
4
4
26906
0
1
1
1
8
14594

0
1
1
3
8
6195
0
1
1
5
8
25715
0
1
2
0
8
8611
0
1
2
2
8
4918

0
1
2
4
8
2773
0
1
3
1
8
4269
0
1
3
3
8
4229
0
1
3
5
8
10918

0
1
4
2
8
4217
0
1
4
4
8
16009
0
1
5
1
4
23610
0
1
5
3
8
7638

0
2
0
3
4
4636
0
2
1
2
8
1737
0
2
1
4
8
7438
0
2
2
1
8
1775

0
2
2
3
8
1900
0
2
2
5
8
4781
0
2
3
2
8
2316
0
2
3
4
8
1623

0
2
4
1
8
6019
0
2
4
3
8
1688
0
2
5
2
4
4720
1
1
1
2
8
2336

1
1
1
4
4
8552
1
1
2
3
8
2424
1
1
3
4
8
1819
1
2
1
3
4
608

1
2
2
2
8
760
1
2
2
4
8
636
1
2
3
3
8
620
1
2
4
2
4
528

2
2
2
3
4
740


3318960



Здесь (x1,y1), (x2,y2) - координаты начала и конца пути. k - коэффициент
(количество путей с учетом отражений, поворотов). count - количество 
путей с заданным началом и концом.




Разделим доску на верхнюю и нижнюю половины. В качестве примера возьмем 
тот-же путь, который рассматривается у B.D.McKay, но уберем из него одно 
ребро (a1c2), чтобы сделать путь незамкнутым. Деление пути на две части показано 
на рисунке. 





















Основной принцип - ребра, пересекающие границу строк 4 и 5 используются
только в нижней части. Договоримся называть профилем описание двух строк. 
В данном случае для верхней и нижней половины - это строки 4 и 5. В принципе 
неважно как, но мы можем получить количество всех путей с одинаковым профилем 
для верхней и нижней части. (Напомню, что мы рассматриваем одну группу и 
концы путей фиксированы). Для получение списка профилей можно использовать 
ZDD, в какой-то статье упоминался даже перебор с возвратами. У меня это
динамическое программирование по профилю, отсюда и название. Кстати, это 
количество для доски 8x8 еще умещается в int32.




Остается проверить соединение профилей верхней части с профилями нижней 
части и для корректных соединений вычислить произведение и сложить. 
Для этого разделим описание профиля на две части. 




Первая часть - описание половины пути. Пронумеруем от единицы все концы 
профиля, пропуская пустые и занятые соединениям ячейки. Для каждого конца 
пути в массив запишем номер парного конца (с которым он соединен). 
Пропущенные концы пути будем считать соединенными с нулевым концом. 
Для приведенного выше пути (если пронуровать сначала по строке 4, затем 
по строке 5) получим следующие два описания. 













0123456
2005634
t0 - для верхней части

0546213
t1 - для нижней части





В верхней части элемент t0[0] указывает на ячейку 2. Это означает, что 
парный конец для ячейки 2 пропущен где-то выше. (второй элемент указывает 
на нулевой). Первый элемент тоже указывает на нулевой, но он будет окончанием 
пути, поэтому ссылка на него не нужна. 




В нижней части элемент t1[0] указывает сам на себя, это означает, что 
в нижней части нет пропущенных концов. 




Таких описаний путей будет гораздо меньше чем профилей. Для каждого 
такого описания будем хранить список масок - это вторая часть описания. 




Вторая часть профиля - битовая маска. Каждую клетку профиля будем обозначать 
следующими кодами: 













в верхней части
в нижней части
00b11bПустая клетка

11b00bКлетка занята соединением

01b01bКонец пути





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













01 11 00 01 00 01 11 01 00 11 00 00 00 00 01 01








pascal




   cc := <количество концов>;
   if t[0][0] <> 0 then d := 0 else d := 1;
   k := t[d][0];
   while k <> 0 do begin
      lk := k;
      t[d][lk] := 0;
      d := 1-d;
      k := t[d][lk];
      t[d][lk] := 0;
      dec(cc);
   end;
   // Если cc = 0, соединение корректно




Окончательно. Проверяем соединение половинок путей на отсутствие внутренних 
циклов. Это делается достаточно просто, код приведен слева. 




Для половинок путей, которые корректно соединяются, имеем два списка масок.
В этих списках нужно найти пары одинаковых элементов. Это тоже не сложно - 
перемещением указателей по двум спискам за O(n+m), где n,m - длины списков.




Немного о времени работы. Описанный выше алгоритм находит количество 
маршрутов с концами (0,0), (1,2) (Их количество известно, т.к. оно совпадает
с количеством замкнутых маршрутов) примерно за 1-2 часа (компьютер 2.9GHz).
Время соединения половинок сильно зависит от положения концов. Для разного 
вида маршрутов время поиска меняется от получаса до 6-8 часов. 




B.D.McKay в своей статье приводит время 232 часа, но здесь трудно сравнить - 
неизвестны характеристики и количество занятых компьютеров, возможно
это постарался закон Мура. 




Количество маршрутов на доске 7x7










y1x1y2x2kcounty1x1y2x2kcounty1x1y2x2kcounty1x1y2x2kcount

0
0
0
2
8
674230890
0
0
0
4
8
693761851
0
0
0
6
4
2597336722
0
0
1
1
4
542411964

0
0
1
3
8
326632052
0
0
1
5
8
551769417
0
0
2
2
4
264163082
0
0
2
4
8
263220801

0
0
2
6
8
775731572
0
0
3
3
4
608710172
0
0
3
5
8
348023248
0
0
4
4
4
285883108

0
0
4
6
8
802505050
0
0
5
5
4
560525540
0
0
6
6
2
2694889704
0
1
0
3
8
0

0
1
0
5
4
0
0
1
1
0
4
0
0
1
1
2
8
0
0
1
1
4
8
0

0
1
1
6
8
0
0
1
2
1
8
0
0
1
2
3
8
0
0
1
2
5
8
0

0
1
3
0
8
0
0
1
3
2
8
0
0
1
3
4
8
0
0
1
3
6
8
0

0
1
4
1
8
0
0
1
4
3
8
0
0
1
4
5
8
0
0
1
5
2
8
0

0
1
5
4
8
0
0
1
5
6
4
0
0
1
6
1
4
0
0
1
6
3
8
0

0
1
6
5
4
0
0
2
0
4
4
213136114
0
2
1
1
8
144994543
0
2
1
3
8
100971663

0
2
1
5
8
146061300
0
2
2
0
4
226164434
0
2
2
2
8
62894692
0
2
2
4
8
78153165

0
2
2
6
8
214637016
0
2
3
1
8
66795208
0
2
3
3
8
217263528
0
2
3
5
8
98083166

0
2
4
2
8
75639171
0
2
4
4
8
79245382
0
2
4
6
4
235868380
0
2
5
1
8
151555750

0
2
5
3
8
103860011
0
2
5
5
8
154709590
0
2
6
2
4
193207272
0
2
6
4
4
231176672

0
3
1
2
8
0
0
3
2
1
8
0
0
3
2
3
4
0
0
3
3
0
4
0

0
3
3
2
8
0
0
3
4
1
8
0
0
3
4
3
4
0
0
3
5
2
8
0

0
3
6
3
2
0
1
1
1
3
8
63062849
1
1
1
5
4
71279944
1
1
2
2
4
41161628

1
1
2
4
8
45494010
1
1
3
3
4
163578772
1
1
3
5
8
66408960
1
1
4
4
4
50410666

1
1
5
5
2
87328652
1
2
1
4
4
0
1
2
2
1
4
0
1
2
2
3
8
0

1
2
2
5
8
0
1
2
3
2
8
0
1
2
3
4
8
0
1
2
4
3
8
0

1
2
4
5
4
0
1
2
5
2
4
0
1
2
5
4
4
0
1
3
2
2
8
27118508

1
3
3
1
4
43786022
1
3
3
3
4
100382214
1
3
4
2
8
34889626
1
3
5
3
2
43844752

2
2
2
4
4
25714348
2
2
3
3
4
80151786
2
2
4
4
2
26791716
2
3
3
2
4
0

2
3
4
3
2
0


82787609160






Количество маршрутов на доске 8x8










y1x1y2x2kcounty1x1y2x2kcounty1x1y2x2kcount

0
0
1
2
8
13267364410532
0
0
0
1
8
54552256212699
0
0
0
3
8
53513623917026

0
0
0
5
8
38319263945887
0
0
1
4
8
22028341304672
0
0
1
6
8
24545417293337

0
0
2
3
8
18169717918556
0
0
2
5
8
11898830224344
0
0
2
7
8
36260324340202

0
1
0
2
8
13715532029359
0
1
0
4
8
19787784587850
0
1
0
6
4
19696437975588

0
1
1
1
8
9532852044884
0
1
1
3
8
9781368428585
0
1
1
5
8
3948987337989

0
1
1
7
8
18452758804511
0
1
2
0
8
11837244334694
0
1
2
2
8
4916116057785

0
1
2
4
8
6519391180857
0
1
2
6
8
3963616860125
0
2
0
3
8
13028014826653

0
2
0
5
4
9199431089350
0
2
1
2
8
2594753369630
0
2
1
4
8
6896564497083

0
2
1
6
8
6141718992235
0
2
2
1
8
3058014157000
0
2
2
3
8
4742905832287

0
2
2
5
8
3017311430061
0
2
2
7
8
8820173297063
0
3
0
4
4
19413135466842

0
3
1
1
8
10110408062108
0
3
1
3
8
7397079054040
0
3
1
5
8
5194582369570

0
3
2
2
8
4187402128045
0
3
2
4
8
7042336261341
0
3
2
6
8
3322556445765

1
1
1
2
8
1818964438000
1
1
1
4
8
3382009933240
1
1
1
6
4
4092105851786

1
1
2
3
8
3156956348424
1
1
2
5
8
1955718659401
1
2
1
3
8
1393891993618

1
2
1
5
4
784774093806
1
2
2
2
8
863129351934
1
2
2
4
8
1358907753723

1
2
2
6
8
759280813902
1
3
1
4
4
2751020507674
1
3
2
3
8
2388209930997

1
3
2
5
8
1601984682169
2
2
2
3
8
1448516328233
2
2
2
5
4
927050878144

2
3
2
4
4
2070436314614
2
3
3
3
8
3841893599203
0
1
3
3
8
11380749105370

0
3
3
3
8
11253924713882
1
2
3
3
8
2257682669436
3
3
3
4
4
6737067025770

1
3
3
4
8
4618651547733
2
2
3
4
8
2561861542533
0
0
3
4
8
32111843670433

0
2
3
4
8
7803023308345
1
1
3
4
8
5288710283637
1
4
3
5
8
2237982204691

2
0
2
3
8
4468486383410
2
3
3
5
8
2083235884884
0
1
3
5
8
6346254706220

0
3
3
5
8
6332595904045
1
2
3
5
8
1281964632032
1
0
1
3
8
7479817116837

2
1
3
5
8
1228355540630
1
0
3
5
8
6094976633237
3
0
1
3
8
7132951430941

2
1
1
3
8
1398177460803
1
3
3
6
8
2562529995619
0
0
3
6
8
19761053531743

0
2
3
6
8
4893931908582
1
1
3
6
8
3236422263593
2
0
0
3
8
13034602591968

0
6
3
0
8
18763414874730
0
4
3
0
8
19007860152205
1
0
0
4
8
19680810381791

2
0
1
4
8
4988881790166
1
0
2
4
8
6367896948102
3
0
2
4
8
5885031108241

2
1
2
4
8
1186833539859
1
0
1
5
8
3889871389337
1
0
2
6
8
3653737248102

1
0
1
7
4
19038978435678
2
0
2
7
4
8753390471776
2
0
1
6
8
6199280467394

2
1
2
6
4
752238261758
3
1
3
4
8
4334675275153
2
0
3
4
8
7474224359929

3
0
1
5
8
3901368000653
3
6
2
2
8
1536675151797
2
0
2
5
8
2798678350278

3
2
3
5
4
2039402798854
3
0
3
5
8
6144547361796
3
0
2
6
8
3316224124942

3
1
3
6
4
2623390769320
2
0
3
6
8
4475136983567
1
7
3
0
8
18301613261859

3
0
3
7
4
18347338911548
2
4
4
3
8
3829168650830
0
6
4
3
8
11384945695491

0
4
4
3
8
11380066814254
1
5
4
3
8
2299723906956
1
3
4
5
8
2350384908827

2
2
4
5
8
1356433460747
0
0
4
5
8
17584181056279
0
2
4
5
8
4307131412320

1
1
4
5
8
2834395588131
3
1
4
5
8
2305759868921
2
0
4
5
8
4306336026741

0
1
4
6
8
7235538927799
0
3
4
6
8
7334194720202
1
2
4
6
8
1388460707748

1
0
4
6
8
6856469270543
3
0
4
6
8
7029600175570
2
1
4
6
8
1404560673934

0
0
4
7
8
53327551936644
0
2
4
7
8
13171082952014
2
2
4
7
8
4110098877183

2
0
4
7
8
12783825032822
0
1
5
5
8
4188002138569
1
2
5
5
8
824566197813

0
0
5
6
8
10423527233861
0
2
5
6
8
2587253594987
1
1
5
6
8
1742174684045

2
0
5
6
8
2569784089443
0
1
5
7
8
12627919083035
1
0
5
7
8
12911625540903

0
0
6
7
8
52777208157959
0
1
6
6
8
8712185116989
0
3
6
6
8
8367322955059

0
0
0
7
4
152548120426494


9795914085489952





Для доски 8x8 нужно было вычислить 136 значений для разных окончаний путей. 
Эти значения приведены в таблице выше. 102 из них приведены у Guenter Stertenbrink.




Для путей (1,0,2,6) я думаю, что у Guenter Stertenbrink опечатка, хотя бы 
потому, что в его таблице два одинаковых значения:



  kt8*8,a2g3:225768266...6
  kt8*8,c2d4:225768266...6


Правильное значение (1,0,2,6) = 3653737248102. 
Количество путей, для окончаний (0,0,0,7) у меня отличается от значения, 
приведенного Guenter Stertenbrink: 



   (0 0 0 7):15254812042...4  
  kt8*8,a1h1:1524879908....0


К сожалению пока я не могу проверить это значение другим путем. 




Остальные 34 значения для проверки посчитаны дважды (второй раз в отраженном 
варианте). Позднее мне удалось пересчитать эти значения другим способом. 




Надеюсь кто-нибудь пересчитает и подтвердит эти данные. (Временно некоторые 
цифры в неподтвержденных данных заменены точками).
Пока же, если данные в таблице верны, количество открытых путей коня 
на доске 8x8 равно 979591408548...2 (или с учетом направления 1959182817097...4). 




Дополнительная проверка

Чтобы проверить количество путей для доски 8x8 я вернулся к динамике по профилю, 
применив на этот раз ломаный профиль. Суммирование количества выполнено по 
модулю 225-1. (Повторив расчет три раза по разным модулям можно было бы 
получить полное значение, но для проверки достаточно вычислить значение 
по одному модулю.) Количество профилей в худшем случае достигает ~2.5*109
штук, поэтому чтобы уложиться в 3-4 гигабайта памяти пришлось сделать
обработку профилей в несколько проходов. В окончательном варианте 
для расчета одного значения требовалось около 16-18 часов (по одному модулю). 









1↑Brendan D.McKay. Knight's Tours an 8x8 Chessboard. 



2↑George Jelliss. Some Enumerations of Classes of 8x8 Knight's Tours



3↑Guenter Stertenbrink. Number of Knight's Tours. 2005/02/24



4↑Martin Lobbing, Ingo Wegener. The Number of Knight's Tours Equals ... - Counting with Binary Decision Diagrams. 1995



5↑Ingo Wegener. Branching Programs and BDD. 



6↑Damon Bell. Lower Bound on Open Knight's Tours. 













25 августа 2013

10 мая 2014



      

      
Comments
          

      

      
11.12.2019 04:28  Jaime Irigoyen  
 Wow, this is incredible!!!! 
 Thank you very much for all the hard work
 

      

      

      
      

      
Вы можете оставить комментарий или задать вопрос
         

         


           

                          Ваше имя: 

             

             Текст сообщения:
             
             
             

             

              
           


         

         
         

      
 
      


      
 
      

    







Copyright © 2009-2014 by