Главная
Эксперименты
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 часов (по одному модулю).

25 августа 2013
10 мая 2014

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

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


Copyright © 2009-2014 by