Множество эвристических алгоритмов для определения расстановок ферзей в задаче N ферзей

УДК 511

Введение

С давних времён существовала математическая задача по определению расстановок 8 ферзей на шахматной доске 8х8 таким образом, чтобы в каждой расстановке ни один из этих ферзей не находился под боем других ферзей[1].

В дальнейшем эту задачу расширили, и была сформулирована задача по расстановке N ферзей на доске NxN, где N > 3.

Следующим этапом появилась задача завершения расстановки: на доске NxN уже установлены М ферзей (М < N), которые не находятся под боем друг друга, и требуется завершить расстановку, определив расположения остальных (N – M) ферзей. Для этой задачи может и не быть решения (расстановки)[2]. Задача завершения расстановки в данной статье не рассматривается.

В настоящее время все эти задачи решаются, в основном, методом поиска с возвратом: последовательно ставится очередной ферзь на следующую вертикаль (горизонталь) таким образом, чтобы этого ферзя не били уже установленные ферзи. Если на очередной вертикали (горизонтали) все клетки оказались под боем, и нельзя установить очередного ферзя, то идёт возврат к предыдущему установленному ферзю (или к более раннему установленному ферзю), и уже для этого ферзя ищется другая клетка в этой вертикали (горизонтали) не под боем.

В последнее время получил распространение вероятностный алгоритм, основанный на градиентной эвристике. Данный алгоритм предполагает работу со случайным набором N ферзей на доске NxN, которая заключается в последовательности замен пар ферзей с тем, чтобы общее количество столкновений ферзей на доске было минимальным. При этом возможны несколько случайных расстановок ферзей [5].

Во всех этих задачах существует несколько определённых целей решения:

- построить одно любое решение задачи (либо доказать, что решение невозможно);

- определить количество решений;

- построить все возможные решения.

Однако существующие компьютеры не позволяют достичь всех этих целей при решении задачи на больших досках. Наибольшая доска, для которой удалось найти все решения, имеет размер 27х27. Кроме того, для больших досок затруднительно решить задачу завершения расстановки.

Актуальность

Поскольку метод поиска с возвратом трудоёмок при определении расстановок ферзей на больших досках, то математики старались придумать эвристические алгоритмы определения расстановок ферзей с помощью одной или нескольких формул. Эвристических алгоритмов оказалось в публикациях всего 4. Задача создания этих алгоритмов заключалась в определении хотя бы одного решения (расстановки) на любой доске.

Эвристические алгоритмы используют основное свойство построения расстановок на всех досках: если на небольших досках, размер которых определяется  с некоторым шагом по размеру доски, алгоритм определяет расстановку, то этот алгоритм будет определять расстановку на всех досках, размер которых определяется с тем же шагом по размеру доски.

Цели и задачи

Все известные эвристические алгоритмы по расстановке ферзей на доске NxN можно представить в виде 4-х вариантов[3]. Ниже эти варианты сформулированы на алгоритмическом языке Python, что удобно для дальнейшей работы.

Начальное условие: доска имеет размер N = 6хК + k, шаг ферзей на доске df = 2, 1<= i <= N, 0<= k <= 5.

Вариант 1. Эвристический алгоритм по расстановке ферзей на досках размером 6хК, 6хК+1, 6хК+4, 6хК+5:

начальная точка f = 0,                                                                                      (1)

Вариант 2. Эвристический алгоритм по расстановке ферзей на досках размером 6хК+2, 6хК+3, 6хК+4, 6хК+5:

начальная точка f = N1/2,
где N1 = (N-1)/2 для нечетных N и N1 = (N-1)/2 для четных N,                      (2)

Вариант 3. Эвристический алгоритм по расстановке ферзей на досках размером 6хК+2:

начальная точка f = 0,
где N1 = (N-1)/2 для нечетных N и N1 = (N-1)/2 для четных N                                                 (3)

Вариант 4. Эвристический алгоритм по расстановке ферзей на досках размером 6хК+3:

начальная точка f = 2,
N1 = (N-1)/2                                                               (4)

Ставится задача: определение множества эвристических алгоритмов по расстановке ферзей на досках NxN.

Проведённые исследования показали, что эвристических алгоритмов по расстановке ферзей на досках NxN достаточно много. Каждый из этих алгоритмов начинается на определённой доске и далее применяется на других досках с определённым шагом по размеру доски. Поэтому можно говорить о множестве эвристических алгоритмов по расстановке ферзей.

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

Например, на доске 8х8 имеется 12 расстановок (без учета симметрии), следовательно, максимально с доской 8х8 будет связано 12 алгоритмов. А оказалось, что получилось 7 алгоритмов.

На доске 13х13 уже более 1900 расстановок без учета симметрии, следовательно, необходимо создать около 1900 эвристических алгоритмов.

Но это не совсем так. Анализ расстановок на доске 13х13 показал, что некоторые расстановки можно определять с помощью одного алгоритма. Но это всё можно проверить только при визуальном изучении расстановок.

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

Поскольку эвристических алгоритмов будет много, и они будут относиться к разным начальным доскам, то необходимо ввести какую-то нумерацию этих алгоритмов. Однако конкретная нумерация алгоритмов в данной статье пока не рассматривается.

Поскольку доска квадратная, то любая расстановка ферзей будет расстановкой, если доску повернуть на 90, 180, 270 градусов, а также, если доску повернуть относительно двух главных диагоналей (доска «зеркальная»). Если первоначальная расстановка не имеет симметрии, то за счёт таких поворотов можно получить ещё 7 расстановок, если имеется одна симметрия – то только 3 расстановки, если есть две симметрии – то только 1 расстановку. Симметричные расстановки можно получить с помощью известных формул перехода от одних систем координат к другим.

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

В статье не приводятся полностью все найденные эвристические алгоритмы по расстановке ферзей, поскольку это займёт много места. Поэтому приведены основные принципы поиска отдельных алгоритмов.

Ранее отдельные результаты работы по поиску алгоритмов были представлены на сайте sql.ru, на форуме «Программирование», в теме «Расстановка ферзей»[4].

Эвристический алгоритм «помещает» очередные ферзи расстановки в определённые клетки доски NхN. Кроме того, в клетки доски могут «помещаться» расстановки ферзей на доске МхМ. В последнем случае получается расстановка на доске (MxN)x(MxN). Такой метод построения расстановок ферзей назовём пока методом матрица в матрице (МММ).

В МММ в качестве вставляемых расстановок могут быть применены не любые расстановки, а расстановки определённого типа – модулярные расстановки[2].

Модулярная расстановка - это такая расстановка, которая в двух диагоналях, расположенных на одинаковом расстоянии от главной диагонали, содержит не более одного ферзя.

Для модулярных расстановок справедливо следующее свойство: если последнюю вертикаль (горизонталь) доски сделать первой вертикалью (горизонталью) доски, или наоборот, то получается новая расстановка. Таким образом, одна полученная модулярная расстановка позволяет получить ещё несколько дополнительных модулярных расстановок. Перестановка вертикалей доски предполагает перестановку чисел в расстановке. Перестановка последней (первой) горизонтали предполагает увеличение (уменьшение) на 1 значения чисел расстановки по модулю величины размера доски.

Если модулярная расстановка не имеет симметрий, то за счет перестановок крайних вертикалей и горизонталей будет (N*N -1) дополнительных расстановок, если одна симметрия, то будет (N – 1) дополнительных расстановок, если две симметрии, то будет (N – 1)/2 дополнительных расстановок.

Модулярные расстановки возможны только на досках 6хК+1 и 6хК+5.

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

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

Прототипами для алгоритмов на всех досках можно, в основном, считать варианты 1, 2, 3, 4, которые были приведены выше.

Вариант 1а. Наиболее интересным вариантом для получения эвристических алгоритмов является вариант 1 для досок 6хК+1 и 6хК+5 (6хК-1).

Этот вариант является модулярным с одним видом симметрии.

Новые расстановки можно получить как в виде перестановки горизонталей (вертикалей), так и с помощью изменения величины f - начальной точки (1):

0<= f <=(N - 1)

Полученные таким образом расстановки будут модулярными.

Следующим развитием данного варианта является изменение величины df - шага ферзей на доске (1):

2<= df <=(N - 2)

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

Для остальных досок, определённых для данного варианта, расстановки, причём модулярные, получаются в случае, когда величины df, (df + 1) и (df – 1) не имеют общие множители (кроме 1) с величиной размера доски.

В качестве примера: все 10 расстановок на доске 5х5 можно определить с помощью одного алгоритма: на первом этапе алгоритма вычисляются расстановки для шагов 2 и 3, а на втором этапе вычисляются расстановки за счёт перестановок первых вертикалей расстановок, полученных на первом этапе:

Rast1a[N] – массив расстановок,

Итого 2 х 5 = 10 модулярных расстановок.

Количество модулярных расстановок на доске 7х7 равно 28 [4]. Для этой доски получаем 4 шага (2, 3, 4, 5) и 7 перестановок вертикалей для каждого шага. Итого – 28 модулярных расстановок ферзей.

Для доски 11х11 количество модулярных расстановок равно 88 [4]. Для этой доски получаем 8 шагов (2, 3, 4, 5, 6, 7, 8, 9) и 11 перестановок вертикалей для каждого шага. Итого – 88 модулярных расстановок ферзей.

При этом не надо искать симметричные расстановки с помощью изменения системы координат, так как с помощью различных шагов и перестановок вертикалей все эти симметричные расстановки определяются.

Расчёты показали, что алгоритм варианта 1а, принципы работы которого приведены выше, определяет модулярные расстановки на следующих досках в следующих количествах:

на доске 13х13 – 130            на доске 17х17 -  238           на доске 19х19 - 304

на доске 23х23 -  460           на доске 25х25 – 250            на доске 29х29 - 754

на доске 31х31 – 868            на доске 35х35 – 280            на доске 37х37 - 1258

на доске 41х41 – 1558          на доске 43х43 – 1720          на доске 47х47 - 2068

на доске 49х49 – 1372          на доске 53х53 – 2650          на доске 55х55 - 880

на доске 59х59 – 3304          на доске 61х61 – 3538 и т.д.

Вариант 1а–ch. Далее, в качестве развития вариантов 1 и 1а, может оказаться ситуация, когда для очередного шага ферзей df получается модулярная расстановка, которая будет неизменной при повороте доски на 90, 180, 270 градусов. Если посмотреть на картинку этой расстановки на доске, то можно увидеть множество квадратов, по углам которых расположены ферзи - четверки ферзей.

Каждая из этих четверок ферзей имеет свои вертикали, горизонтали и диагонали. Поэтому для этих четверок ферзей справедливо условие: можно менять одновременно вертикали противоположных ферзей и получать новую расстановку.

Таким образом, если на доске количество четвёрок Q, то можно определить Q новых расстановок. При этом, если у двух четвёрок нет общих ферзей, то можно получить уже не 2, а 3 расстановки. А если у 3-х четвёрок нет общих ферзей, то можно получить не 3, а 7 расстановок.

Таким образом, если Q четвёрок не имеют общих ферзей, то можно получить (2^Q – 1) расстановок.

Расстановки с четвёрками ферзей существуют на досках размером 5хК+4.

Расстановку с четвёрками ферзей можно определить следующим образом. При очередной перестановке вертикалей варианта 1а один из ферзей располагается в центре доски, а четыре ферзя на крайних вертикалях и горизонталях имеют следующие значения:

Полученная расстановка имеет две симметрии. Поэтому для этих расстановок количество новых расстановок за счёт перестановок вертикалей и горизонталей равно (N – 1)/2.

На доске определяется либо 2 расстановки с четвёрками ферзей, либо, реже, 4 расстановки с четвёрками ферзей. Данные получены для досок размером до 1000.

Поиск всех четвёрок ферзей на полученной расстановке трудоёмкий. Однако часть четвёрок можно легко найти. Для этого необходимо переставить ферзя из первой вертикали в центр доски. И зная, как переставляется этот ферзь, переставить все необходимые вертикали и горизонтали доски. Тогда в центре доски окажется ферзь, а вокруг него будут видны на доске (N-1)/4 четвёрки ферзей. Чтобы их определить, необходимо, начиная с первой вертикали, вычёркивать ферзи по четвёркам. Тогда для очередного ферзя с координатами (x,y) определяются ещё 3 ферзя с координатами:

(N + 1 – x, N + 1 – y), (y, N + 1 – x), (N + 1 – y, x)

Все эти четвёрки не имеют общих ферзей, и в результате получаются расстановки в количестве:

2^((N-1)/4) – 1                                       (5)

После того, как определены все четвёрки ферзей вокруг центрального ферзя, составляется программа перебора этих четвёрок с последующим изменением расстановок за счёт перестановки вертикалей для выбранных четвёрок ферзей.

Расстановки, получаемые после перебора четвёрок ферзей, будут модулярными без симметрии, поэтому для каждой такой расстановки необходимо ещё найти (N*N – 1) расстановок за счет алгоритма перестановки вертикалей и горизонталей.

Существует программа, которая определяет доски, на которых можно построить такие четвёрки. Расстановки с четвёрками ферзей определяются, например, на досках размером (если рассматривать доски размером до 100):

5, 13, 17, 25, 29, 37, 41, 53, 61, 65 (4 расстановки), 73, 85 (4 расстановки), 89, 97.

Данный перечень можно продолжить.

Например, существуют 2 расстановки с чётверками ферзей на доске 997х997. Если  обратиться к формуле (5), то количество модулярных расстановок, которые определяет алгоритм варианта 1а-ch с помощью четвёрок ферзей на доске 997х997, а также с учётом симметрии, будет равно:

2 * (2^249 – 1) * 997 * 997 модулярных расстановок       (6)

Это очень большое число, и вряд ли современный компьютер посчитает все эти расстановки.

Таким образом, на всех досках, где определена расстановка с четвёрками ферзей, алгоритм 1а-ch определяет для этой расстановки другие модулярные расстановки в количестве, которое вычисляется аналогично (5).

Вариант 1а-1. Теперь рассмотрим применение варианта 1а для получения расстановок на досках 6хК и 6хК+4.

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

Вариант 1а-ch-1. Дальнейшее развитие варианта 1а-1. Для получения четвёрок ферзей необходимо к доске добавить вертикаль (N + 1) и горизонталь (N + 1), найти для увеличенной доски расстановку с четвёрками ферзей. В дальнейших вычислениях необходимо использовать только те четвёрки ферзей, ферзи у которых не находятся на добавленных вертикалях и горизонталях.

Поскольку нельзя переставить ферзя в центр доски, то невозможно определить четвёрки ферзей вокруг центрального ферзя. Поэтому применяется программа поиска всех четвёрок ферзей.

Вариант 1б. Теперь рассмотрим другое изменение варианта 1 на досках 6хК+1, 6хК+5.

Пусть имеется расстановка на доске 13х13 согласно варианту 1.

Оказывается, что имеются двойки ферзей, которые можно менять местами: вертикали 1 и 11, 2 и 12, 3 и 13. То есть, имеются ещё 3 расстановки.

Для доски 25х25 имеются двойки ферзей, которые можно менять местами: первая линия 1 и 23, 2 и 24, 3 и 25, вторая линия 1 и 20, 2 и 21, 3 и 22, 4 и 23, 5 и 24, 6 и 25. То есть, уже найдено 9 расстановок.

Получается, что для досок 12хК+1 можно определить расстановки в количестве:

R = r * 3, где r – сумма чисел от 1 до К.

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

Вариант 1б-1. Теперь рассмотрим применение варианта 1б на досках 6хК, 6хК+4.

Для этого к доске добавляется (N + 1) вертикаль и (N +1) горизонталь, применяется алгоритм варианта 1б и не используются двойки ферзей, которые включают в себя вертикаль (N + 1).

Приведённые выше эвристические алгоритмы определяют помещение ферзя в определённую клетку доски (перестановка вертикалей, горизонталей). Такие расстановки будем называть простыми расстановками.

В настоящей статье приведена только малая часть эвристических алгоритмов из тех, которые удалось найти. В частности, были получены алгоритмы, которые опираются на все расстановки на досках 4х4, 5х5, 6х6, 7х7, 8х8, 9х9. Получено дальнейшее расширение вариантов 2, 3, 4.

Вместе с тем существуют сложные расстановки, которые определяются путём суммы или произведения двух расстановок: первая расстановка на доске NxN, вторая расстановка на доске МхМ.

Суммой двух расстановок будет сложная расстановка на доске (N+M)x(N+M), в которой перечислены сначала значения первой расстановки, а потом значения второй расстановки. При этом к значениям одной расстановки добавляется величина доски другой расстановки. Примеры таких расстановок были приведены в [6]. Задача по определению суммы расстановок очень трудоёмкая.

Произведением двух расстановок будет расстановка на доске (NxM)x(NxM), в которой вместо каждого ферзя в расстановке на доске NxN устанавливается расстановка на доске MxM.

В таком произведении участвуют две расстановки: основная расстановка на доске NxN и включённая расстановка на доске MxM.

Каждое значение сложной расстановки, которая является произведением двух расстановок, определяется следующим образом:

имеются две расстановки: основная - rast1[N] и включённая - rast2[M], и сложная расстановка Srast3 [NхМ], тогда:

Примеры произведения двух расстановок были приведены в [7]. Такие расстановки в данной публикации назывались фрактальным решением, хотя к фракталам такое построение расстановки имеет малое отношение.

В [4] автором было предложено названия метода определения произведения расстановок как метода матрицы в матрице. Это было связано с тем, что на доске вместо ферзя устанавливается как бы другая доска. Если рассматривать этот процесс как построение матриц, то получается, что вместо элемента матрицы устанавливается другая матрица.

Поскольку в настоящей работе упор делается на произведение расстановок, то данный метод можно назвать методом произведения расстановок (МПР).

Ставится задача: определение множества эвристических алгоритмов по определению сложных расстановок ферзей с помощью МПР.

В дальнейшем необходимо ввести следующее обозначение: комбинация (N, М) – это перечень всех сложных расстановок, которые получаются при произведении известных основных расстановок на доске NxN и известных включённых расстановок на доске МхМ. Если идёт обозначение (N,1), то это обозначает перечень простых расстановок на доске NxN.

Исследования МПР проводились по нескольким направлениям.

Основная расстановка в МПР может быть любой расстановкой.

Включённая расстановка в МПР должна быть только модулярной расстановкой.

Если основная расстановка будет модулярной расстановкой, то сложная расстановка будет тоже модулярной.

Основная и включённая расстановки могут быть сложными расстановками.

Пример: доска 25х25, комбинация (5, 5), перечень сложных расстановок получается при произведении основных расстановок на доске 5х5 (всего 10 расстановок) и включённых расстановок на доске 5х5 (всего 10 расстановок).

В результате применения алгоритма (7) для всех расстановок на двух досках получается:

10 х 10 = 100 сложных модулярных расстановок.           (8)

Вариант МПР-0 для определения симметричных расстановок и расстановок после перестановки вертикалей. Поскольку применяемые  в МПР основные и включённые расстановки имеют в своём составе все симметричные расстановки, то и все получаемые сложные расстановки тоже будут иметь в своём составе сложные симметричные расстановки.

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

Для комбинации расстановок (5, 5) получается 500 сложных расстановок, для комбинации расстановок (5, 7) получается 1960 сложных расстановок, для комбинации расстановок (7, 5) получаем 5488 сложных расстановок и т.д.

Можно привести формулу расчёта количества сложных расстановок, получаемых с помощью перестановки вертикалей:

имеются на доске NxN основные модулярные расстановки в количестве n,

имеются на доске МхМ включённые модулярные расстановки в количестве m.

Тогда общее количество сложных модулярных расстановок, получаемых с помощью перестановки вертикалей для комбинации (N, M), будет равно:

M * n * m              

Вариант МПР-1 для двух включённых расстановок. В первоначальном определении МПР говорится об одной включённой расстановке.

Однако исследования показали, что в качестве включённых расстановок могут быть выбраны две различные модулярные расстановки. Для этих двух модулярных расстановок должны выполняться следующие условия:

- включённые расстановки определяются согласно варианту 1а;

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

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

Если рассматривать пример (8), то среди включённых расстановок на доске 5х5 можно определить 5 пар включённых расстановок. Поскольку в основной расстановке ферзей 5, то количество различных вариантов по одной расстановке из пары для всех 10 основных расстановок равно:

(2^5 – 1) * 10 сложных расстановок

А поскольку таких пар 5, то окончательное количество получаемых в примере сложных расстановок будет:

(2^5-1) *10 * 5 = 1650 сложных расстановок.

Расчёты показали следующее количество двух включённых расстановок на следующих досках:
5х5 – 5, 7х7 – 10, 11х11 – 18, 13х13 – 23, 17х17 – 31, 19х19 – 34, 23х23 – 42, 25х25 – 23, 29х29 – 55.

Рассмотрим общий случай:
- на доске NxN определено Р расстановок;
- на доске МхМ определено Qp пар модулярных расстановок.

Тогда общее количество сложных расстановок для комбинации (N,M) при применении алгоритма варианта МПР-1 будет равно:

(2 ^ N - 1) * Qp * P

Вариант МПР-2 для перемещения групп ферзей. При рассмотрении сложной расстановки оказалось, что ферзи включённой расстановки с одним порядковым номером, расположенные на доске сложной расстановки, имеют на этой доске свои горизонтали, вертикали и горизонтали. То есть, имеет место группа ферзей, которую можно одновременно перемещать на доске по этим горизонталям, вертикалям и диагоналям.

Поскольку включенные расстановки располагаются на элементах основной расстановки, то и любая группа ферзей должна располагаться на одной из основных расстановок на доске NxN.

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

Продолжим рассматривать пример (7).

Каждый ферзь из включённой расстановки формирует группу из 5 ферзей (количество ферзей основной расстановки), которая может располагаться на 10 основных расстановках. Поскольку групп ферзей 5, и каждая из них принимает 10 положений, то получается, что вариант перемещения групп ферзей определяет:

10*10*10*10*10 = 100 000 сложных расстановок.

Рассмотрим общий случай:

- на доске NxN определено Р расстановок;

- на доске МхМ определено Q модулярных расстановок.

Тогда общее количество сложных расстановок комбинации (N,M) для варианта МПР-2 будет равно:

(P ^ M) * Q

Есть ещё одно утверждение: поскольку включённые расстановки определяются на основании алгоритма варианта 1а, то в какой-то момент в результате перемещений групп ферзей получится расстановка, определяемая алгоритмом варианта 1а на доске (NxM)x(NxM).

Вариант МПР-12 для перемещения групп ферзей в варианте МПР-1. Для варианта МПР-12 перемещаемую группу ферзей можно создавать только для тех ферзей, которые имеют одинаковые значения в этих двух расстановках. В данном варианте количество сложных расстановок для примера (7) будет равно 10, поскольку только одна группа ферзей может перемещаться по 10 основным расстановкам.

Если рассматривать предыдущий пример, то общее количество сложных решений комбинации (N,M) для варианта МПР-12 будет равно:

(P) * Q

Примеры для объединения результатов расчётов по всем алгоритмам МПР для определённых досок. 

Для начала рассмотрим пример (8):

- вариант МПР-0 определяет 500 сложных расстановок;

- вариант МПР-1 определяет 1550 сложных расстановок;

- вариант МПР-2 определяет 100000 сложных расстановок

- вариант МПР-3 определяет 10 сложных расстановок.

Если всё сложить, то получается, что на доске 25х25 в комбинации (5, 5) определяются 102 060 сложных расстановок.

На больших досках добавляется операция «разбиения» таких досок на более мелкие доски. То есть, проводится определение множителей величины размера рассматриваемой доски. Это позволяет построить для применения МПР последовательность всех возможных комбинаций промежуточных досок.

Рассмотрим следующий пример: определение комбинаций сложных расстановок на доске 1000х1000.

Всего при определении расстановок на доске 1000х1000 будут участвовать комбинации расстановок: 

(1000,1), (200,1), (125,1), (40,1), (25,1), (8,1), (5,1), (200,5), (40,5), (40,25), (5,5), (5,25), (25,5), (8,5), (8,25), (8,125).

При рассмотрении комбинаций (5,1), (25,1), (125,1), (5,5), (5,25), (25,5) определяются модулярные простые расстановки для применения во включённых расстановках, а также другие возможные расстановки для применения всех полученных расстановок в основных расстановках. При этом возможно определение пар включённых расстановок.

Дополнительно сложные расстановки на доске 1000х1000 можно определить, если применить доску 1001х1001. Здесь возможны 4 варианта определения расстановок:

1.Ферзь на доске 1001х1001 устанавливается в клетку (1,1). Тогда из получаемых расстановок убирается первое число - 1, и все значения этих расстановок уменьшаются на 1.

2.Ферзь на доске 1001х1001 устанавливается в клетку (1,N). Тогда из получаемых расстановок убирается первое число - N.

3.Ферзь на доске 1001х1001 устанавливается в клетку (N,N). Тогда из получаемых расстановок убирается последнее число - N.

4.Ферзь на доске 1001х1001 устанавливается в клетку (N,1). Тогда из получаемых расстановок убирается последнее число - 1, и все значения этих расстановок уменьшаются на 1.

Всего при определении расстановок на доске 1001х1001 будут участвовать комбинации расстановок: 

(1001,1), (7,1), (11,1), (13,1), (77,1), (91,1), (143,1), (77,13), (91,11), (143,7), (11,13), (13,11), (7,13), (13,7), (7,11), (11,7).

Здесь также необходимо определить модулярные расстановки для комбинаций (7,1), (11,1), (13,1), (11,13), (13,11), (7,13), (13,7), (7,11), (11,7), а также пары включённых расстановок.

Нахождение ферзей в углах доски при определении сложной расстановки предполагает, что в углах доски находится ферзь включённой расстановки. Только с таким условием отбираются как включённые расстановки, так и пары включённых расстановок для работы на доске 1001х1001. Также должно быть ограничение на перемещение ферзей из угла доски при работе алгоритма варианта МПР-2.

Если во всей цепочке комбинаций при определении сложной расстановки участвуют только модулярные расстановки на каждой из промежуточных досок, то данная сложная расстановка будет модулярной, и для неё справедливо применение варианта МПР-0.    

Можно все полученные эвристические алгоритмы собрать в один Главный алгоритм и попытаться найти расстановки на больших досках. Однако, даже у найденных алгоритмов так много получается расстановок, что на существующих компьютерах просто перечислить расстановки на больших досках будет невозможно из-за нехватки времени.

Научная новизна

В качестве развития существующих эвристических алгоритмов (1), (2), (3), (4) получено некоторое множество эвристических алгоритмов из всех возможных эвристических алгоритмов определения расстановок ферзей в задаче N ферзей.

В результате расчётов получено количество расстановок ферзей, определяемых с помощью представленных алгоритмов.

Показано, что могут быть трудности при определении всех расстановок ферзей с помощью представленных алгоритмов на больших досках с применением существующих компьютеров.

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

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

Рецензии:

18.05.2020, 13:05 Мирмович Эдуард Григорьевич
Рецензия: Вообще, такого рода задачи могут или могли бы стать одним из инструментов для теории групп и представлений в части поиска неприводимых представлений, а, может, и других разделов математики множеств. Но это так, интуитивно. В детстве рецензент находил несколько вариантов таких расстановок, а в шахматах дальше 3-го разряда не продвинулся. Если даже эта статья - полная копия или сборка из других статей и материалов (что рецензент не изучал), то всё равно заслуживает публикации. Только надо бы чётко указать, на каком алгоритмическом языке (инструкции) рассматриваются варианты, подкорректировать пробелы и др. синтаксические погрешности и шероховатости исправить. Рецензент рекомендует к публикации данную работу.