Foreword (for English-speaking readers)

How many ways are there to place 6 nonattacking queens on n x n board? On this page the exact formula for 6-Queens problem is given. Recently Vaclav Kotesovec has obtained the formula for 5-Queens problem. I had derived the similar one, but I didn’t hurry to publish the result in OEIS. Then I decided to promote the competition to obtain as many data for 6-Queen problem as possible. My program turned out to be the fastest and I calculated the answer for n=82. The recurrence has order 81 and is presented below.

The following text on this page explains the idea of my solution and it is written in Russian.

—————————————————————-

Итак, конкурс завершён, и мне удалось вывести формулу. Строгое доказательство формулы возможно, если посчитать примерно 144 значения, но на это у меня не хватит вычислительной мощности. Однако формула почти наверное верна, и тому есть косвенные доказательства, которые будут представлены в конце. Вместе с формулой были также получены производящая функция и рекуррентное соотношение. Специально не оформляю формулы в TeX, чтобы можно было скопировать и проверить в какой-нибудь системе компьютерной алгебры. Я использую Maple.

Формула

Явная формула [ Exact Formula ]

a(n)=
1/47628000*(n-1)*
(66150*n^10-3241350*n^9+
73161900*n^8-1004921400*n^7
+9334555125*n^6-61490397675*n^5
+291912061245*n^4
-988979114935*n^3+2292629743017*n^2
-3280814206325*n+2166093922711)*n
+1/432*(72*n^7-2916*n^6+50580*n^5
-485172*n^4+2750088*n^3-8977638*n^2
+14596860*n-7467833)*floor(1/2*n)
+2/243*(216*n^5-6480*n^4+81308*n^3-525474*n^2
+1650126*n-1364199)*floor(1/3*n)
+1/4*(116*n^3-2133*n^2+12902*n-13728)*floor(1/4*n)
+8/125*(100*n^3-1778*n^2+16360*n-19739)*floor(1/5*n)
+2/27*(2118*n-4499)*floor(1/6*n)
+48/49*(95*n-173)*floor(1/7*n)
+2*(2*n-5)*floor(1/8*n)
+1/243*(216*n^5-6750*n^4+88940*n^3
-620184*n^2+2250534*n-3138465)*floor(1/3*n+1/3)
-1/4*(16*n^3-149*n^2-794*n+13265)*floor(1/4*n+1/2)
+1/4*(100*n^3-1984*n^2+13696*n-26993)*floor(1/4*n+1/4)
+4/125*(150*n^3-2842*n^2+27521*n-65479)*floor(1/5*n+1/5)
+4/125*(100*n^3-1978*n^2+19118*n-54269)*floor(1/5*n+2/5)
+4/125*(50*n^3-1014*n^2+10311*n-30319)*floor(1/5*n+3/5)
-4/9*(92*n+1067)*floor(1/6*n+1/2)
+2/27*(1566*n-10901)*floor(1/6*n+1/3)
+1/9*(1934*n-6633)*floor(1/6*n+1/6)
-1/27*(2670*n+1903)*floor(1/6*n+2/3)
+4/49*(920*n-3597)*floor(1/7*n+1/7)
+8/49*(335*n-1672)*floor(1/7*n+2/7)
+4/49*(600*n-3409)*floor(1/7*n+3/7)
+8/49*(145*n-926)*floor(1/7*n+4/7)
+4/49*(160*n-989)*floor(1/7*n+5/7)
-12*floor(1/8*n+1/2)
+2*(2*n-11)*floor(1/8*n+1/4)
+2*(2*n-9)*floor(1/8*n+1/8)
+2*(2*n-11)*floor(1/8*n+3/8)
-4*floor(1/8*n+5/8)

Рекуррентное соотношение [ Recurrence ]


a(0) = 0, a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 0,
a(6) = 4,
a(7) = 832,
a(8) = 22708,
a(9) = 312956,
a(10) = 2716096,
a(11) = 17117832,
a(12) = 84871680,
a(13) = 349093856,
a(14) = 1239869972,
a(15) = 3905117168,
a(16) = 11139611892,
a(17) = 29224290600,
a(18) = 71402912960,
a(19) = 164029487484,
a(20) = 357164398040,
a(21) = 741835920276,
a(22) = 1477798367368,
a(23) = 2836053660668,
a(24) = 5263672510684,
a(25) = 9478352925488,
a(26) = 16606678238496,
a(27) = 28378012168908,
a(28) = 47398421913600,
a(29) = 77522788818316,
a(30) = 124365738451680,
a(31) = 195977208395580,
a(32) = 303748457927000,
a(33) = 463582807382736,
a(34) = 697434075907504,
a(35) = 1035256352634420,
a(36) = 1517521355687872,
a(37) = 2198354851112760,
a(38) = 3149525540545556,
a(39) = 4465340754179496,
a(40) = 6268789672000200,
a(41) = 8718985543275112,
a(42) = 12020393279930400,
a(43) = 16433877629761792,
a(44) = 22290259302807700,
a(45) = 30006374870365136,
a(46) = 40104595602917300,
a(47) = 53235736336244300,
a(48) = 70206658745546392,
a(49) = 92012392107526748,
a(50) = 119874540287319196,
a(51) = 155285624835663096,
a(52) = 200061731591400456,
a(53) = 256402868739653996,
a(54) = 326964160566718884,
a(55) = 414936937933564876,
a(56) = 524143826614930088,
a(57) = 659146400314780240,
a(58) = 825370726096096944,
a(59) = 1029248723087783480,
a(60) = 1278382175175730400,
a(61) = 1581726455456457436,
a(62) = 1949802708715765760,
a(63) = 2394934394370749612,
a(64) = 2931519277634600260,
a(65) = 3576331321283597364,
a(66) = 4348866396076652064,
a(67) = 5271724407012487004,
a(68) = 6371045245979662116,
a(69) = 7676988784016499040,
a(70) = 9224280528369282176,
a(71) = 11052810248193489712,
a(72) = 13208310203912865056,
a(73) = 15743096674420482872,
a(74) = 18716907492532573788,
a(75) = 22197814778572880876,
a(76) = 26263252803050925204,
a(77) = 31001134787399966700,
a(78) = 36511107035656245460,
a(79) = 42905907681877306448,
a(80) = 50312888556807094572,
a(n) = a(n-81)+5*a(n-80)+13*a(n-79)+21*a(n-78)+19*a(n-77)
-5*a(n-76)-57*a(n-75)-127*a(n-74)-184*a(n-73)-180*a(n-72)
-70*a(n-71)+162*a(n-70)+476*a(n-69)+768*a(n-68)
+889*a(n-67)+695*a(n-66)+114*a(n-65)-794*a(n-64)
-1806*a(n-63)-2570*a(n-62)-2701*a(n-61)-1929*a(n-60)
-234*a(n-59)+2072*a(n-58)+4374*a(n-57)+5898*a(n-56)
+5950*a(n-55)+4180*a(n-54)+771*a(n-53)-3521*a(n-52)
-7530*a(n-51)-9994*a(n-50)-9959*a(n-49)-7119*a(n-48)
-1994*a(n-47)+4156*a(n-46)+9657*a(n-45)+12909*a(n-44)
+12881*a(n-43)+9447*a(n-42)+3464*a(n-41)-3464*a(n-40)
-9447*a(n-39)-12881*a(n-38)-12909*a(n-37)-9657*a(n-36)
-4156*a(n-35)+1994*a(n-34)+7119*a(n-33)+9959*a(n-32)
+9994*a(n-31)+7530*a(n-30)+3521*a(n-29)-771*a(n-28)
-4180*a(n-27)-5950*a(n-26)-5898*a(n-25)-4374*a(n-24)
-2072*a(n-23)+234*a(n-22)+1929*a(n-21)+2701*a(n-20)
+2570*a(n-19)+1806*a(n-18)+794*a(n-17)-114*a(n-16)
-695*a(n-15)-889*a(n-14)-768*a(n-13)-476*a(n-12)
-162*a(n-11)+70*a(n-10)+180*a(n-9)+184*a(n-8)
+127*a(n-7)+57*a(n-6)+5*a(n-5)-19*a(n-4)-21*a(n-3)
-13*a(n-2)-5*a(n-1), n>80.

Производящая функция (только знаменатель) [ Generating Function (Denominator only) ]


(x-1)^13*(x+1)^8*(x^2+x+1)^6*(x^2+1)^4*(x^4+x^3+x^2+x+1)^4
*(x^2-x+1)^2*(x^6+x^5+x^4+x^3+x^2+x+1)^2*(x^4+1)^2.

Идея решения

Моё решение этой задачи прошло через несколько этапов: от реализации «в лоб» до реализации за O(n7). Опишу кратко, что было сделано.

Реализация «в лоб»

Каждый ферзь имеет 2 степени свободы, поэтому, когда их количество фиксировано, каждый может занимать одну из O(n2) позиций на доске. Если число ферзей k, то, запустив 2k вложенных друг в друга циклов, перебираем эти позиции и считаем нужные расстановки. Когда k=6 алгоритм имеет сложность O(n12). Здесь же нужно учесть, что 6!=720 перестановок в таком алгоритме считаются за одну. То есть когда первый ферзь уже поставлен, второго надо ставить строго ниже первого. Третьего – ниже второго и т. д. Сделав это, получаем скорость работы примерно 2 минуты для n=15. Учитывая вертикальную симметрию, получаем 1 минуту. Этим можно посчитать до n=20, но придётся ждать довольно долго.

От O(n12) к O(n10)

Следующий шаг состоял в переходе к 11-й степени сложности, но там обсуждать нечего. Рассмотрим сразу способ, позволяющий перейти к O(n10). Предположим, что у нас есть k ферзей. Чтобы посчитать, сколькими способами их расположить на доске, чтобы они не били друг друга, ставим k-1 ферзя, а для последнего за O(1) вычисляем, на скольких свободных клетках он может оказаться. Делаются эти расчёты по формуле включения–исключения. Смотрите рисунок ниже. Предположим, что мы уже поставили некоторых ферзей (как угодно), и хотим выяснить, сколько клеток, находящихся между красными линиями они пробивают (последнего ферзя будем ставить именно в этот промежуток).

По формуле включения–исключения нужно посчитать, сколько клеток бьёт каждый ферзь. Вычесть из этого количество клеток, бьющихся каждой парой ферзей и прибавить те, которые бьются тремя ферзями. Четырёх и больше ферзей рассматривать нет смысла. Такие комбинации в данном решении никогда не встретятся, так как предполагается, что внутри зоны между красными линиями будет только один ферзь, место для которого мы как раз ищем. На рисунке клетки, отмеченные синим, бьются одним ферзём. Зелёные – двумя. Красные клетки бьются тремя ферзями и (ВАЖНО) трижды бьются каждой парой из трёх соответствующих ферзей. В этом примере первый ферзь (если считать сверху вниз) бьет 4 клетки. Второй – 6 и третий тоже 6. Итого 16. Вычитаем количество клеток, которых бьют пары ферзей. Это 3 зелёных клетки плюс трижды 2 красных (всего 9). Прибавляем 2 красных и получается 9. Это значит, что 9 клеток пробиваются и 16-9=7 свободны.

Формулы для подсчёта клеток, находящихся под атакой, довольно сложны. Например, в моей программе, подсчёт числа клеток, которые бьёт ферзь из позиции (i,j) выглядит следующим образом (только в программе отсчёт идет от 0, поэтому к данному рисунку формулу применить правильно не получится):

( bottom - top - 1 )
+ min ( max ( 0, i - j + n - top - 1 ), bottom - top - 1 )
+ min ( max ( 0, i + j - top ), bottom - top - 1 ).

(top – верхняя линия [здесь top=2], bottom – нижняя [здесь bottom=5], n – высота доски [здесь n=6]).

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

Таким образом, если решать задачу о k ферзях, то этим методом она решается за O(n2k-2), а в нашем случае – за O(n10). У меня этот алгоритм сначала работал долго, но с помощью профилировщика был ускорен в 10 раз. Для n=35 вычисления длились 30 часов на одном ядре, и чуть больше суток для n=50 на 64 ядрах.

Переход к O(n7)

Далее с моей стороны начались попытки решать задачу быстрее, чем за 10 степень. Медленно я двигался к O(n9), затем O(n8), но вдруг второй участник – тов. alexBlack – неожиданно (и, видимо, случайно) мне подсказал, что он рассматривает прямоугольные доски вместо квадратных. И как только я представил прямоугольную доску, сразу стало понятно, как без усилий решать задачу за 7-ю степень (за что спасибо, тов. alexBlack).

Будем рассматривать конфигурации, при которых доска имеет размер mxn и ни одну границу нельзя сдвинуть так, чтобы уменьшить доску. То есть границы доски тем или иным способом заняты. Всего существует 3 способа, при котором границы доски заняты. Первый способ порождает конфигурации типа А: когда ферзи стоят в противоположных углах -

Конфигурации типа A

4 оставшихся ферзя имеют по 2 степени свободы. Но мы помним, что позиции последнего ферзя определяются по формуле включения-исключения. Поэтому, когда m и n фиксированы, вычисление количества таких конфигураций выполняется за время O(n6).

Конфигурации типа B получаются, когда один ферзь блокирует угол, а два других – противоположные стороны доски (при этом не занимают угол).

Конфигурации типа B

Один из ферзей на границе может двигаться только по зелёным клеткам, а второй – только по синим. То есть у них на двоих есть две степени свободы. Остальные три ферзя можно поставить за O(n4), и получается так же 6-я степень сложности.

Конфигурации типа C получаются, когда ферзи не занимают углы и каждую границу блокирует ровно один ферзь.

Конфигурации типа C

4 ферзя имеют по одной степени свободы, остальные два ставятся за O (n2). Опять 6-я степень сложности.

Обозначим через Ai,j, Bi,j, Ci,j число конфигураций вида A, B и C на досках размером ixj. Тогда числа

Zi,j = 2Ai,j + 4Bi,j+Ci,j

показывают, сколькими способами можно расположить 6 ферзей на доске ixj так, чтобы они не били друг друга, а границы доски были заняты. Для проверки представляю Zi,j (для i,j=6..12, причём i≥j так как матрица симметрична).

[4],
[86,472],
[366,2216,8692],
[1286,7426,27024,76424],
[3518,20112,69174,186448,431180],
[8550,46934,156970,405958,906302,1805772],
[17684,96770,317466,804762,1747092,3419536,6155276].

Ответом ко всей задаче будет, очевидно, сумма:

Выражение под знаком суммы Zi,j(n-i+1)(n-j+1) показывает, сколькими способами можно расположить прямоугольник размером ixj в квадрате nxn.

Итак, для вычисления очередного значения Qn, надо знать все предыдущие Zi,j (i,j=6..n-1), и посчитать следующую строку матрицы Z: Zn,j (j=6..n). Для этого потребуется n*O(n6) = O(n7) операций.

Именно эта программа считала ответ для n=80 около 10 часов на 56 ядрах. Это долго, конечно, но данную реализацию я даже не оптимизировал. Например, когда все ферзи, кроме последнего, уже поставлены, каждый раз заново считались клетки, которые бьются первым, вторым, третьим ферзями и т. д., хотя их позиции долгое время не изменяются. То есть программа ещё раз в 8-10 ускоряется, так как написана очень грубо. Но этого хватило и хорошо.

Косвенное доказательство

Здесь я вынужден сослаться на кое-какие вещи, которые известны из комбинаторики. Известно, что производящая функция последовательности Qn является рациональной, а корни знаменателя равны по модулю единице. Из этого следует, что формула будет иметь вид квазиполинома (это полином, в котором присутствуют операции взятия целой части от деления). Известно, что степень полинома будет равна 2k, а максимальный период (знаменатель внутри floor) тоже 2k (если число ферзей равно k). Известно, что в формуле коэффициент при n2k равен 1/k!, а коэффициент при n2k-1 равен -5/(3(k-2)!). Если в моей формуле раскрыть скобки, то так и будет. Рекуррентное соотношение для квазиполинома должно быть кососимметричным. Так и получается. Ну и последнее. В такого рода задачах, когда известен вид формулы, она обычно восстанавливается однозначно, только часто не всегда знаешь порядок соотношения (то есть степень знаменателя производящей функции). Когда набирается нужный объём начальных данных, сразу получается довольно компактное выражение в виде рекуррентного соотношения. Если чисел мало, таких красивых соотношений не получается никогда. Вместо них получаются жуткого вида дроби на пару десятков экранов.

Это, конечно, не доказательство, но для строгого доказательства надо примерно 144 значения. Так как полином имеет степень 12, а в знаменателе у целой части не может быть чисел больше 12. Всего (максимум) 144 неопределённых коэффициента. А по 80 удалось их только «угадать». Впрочем, если кто-то покажет число n, для которого формула не верна, я приму критику о нестрогости в своих рассуждениях.

Всем спасибо за явное и неявное участие. Конкурсы ещё будут, но пока не знаю, когда именно.

Обсуждение конкурса на форуме в этой теме.