Расположение 8 ферзей на шахматной доске. Разбираемся, что же там нового открыли в задаче о ферзях. Дополнение до N и Answer Set Programming

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

Задача о N ферзях состоит в том, чтобы разместить N ферзей на доске размером N×N таким образом, чтобы ни один ферзь не находился под боем другого, при этом на доске заранее установлены несколько ферзей. То есть в итоге никакие два ферзя не должны находиться на одной линии или диагонали. Впервые задачку сформулировали в 1848 году, а в 1850 году придумали вариант головоломки, когда некоторое количество ферзей заранее поставлено на доску, а игрок должен расставить остальных, если это возможно.

Исследователи из Сент-Эндрюсского университета (Шотландия) опубликовали , в которой доказывают, что задача о N ферзях является не только #P-полной задачей, но также NP-полной задачей. Более того, Математический институт Клэя (США) готов заплатить миллион долларов любому, кто сможет оптимизировать решение этой задачи как задачи на доказательство P=NP.

Как известно, в теории сложности #P является классом проблем, решением которых является количество успешных, то есть, завершающихся в допускающих состояниях, путей вычислений для некой недетерминированной машины Тьюринга, работающей полиномиальное время. Вычислительные задачи класса #P (counting problems) связаны с соответствующими задачами разрешимости (decision problems) класса NP.

Учёные отмечают, что эта задача может быть самой простой среди NP-полных задач, чтобы объяснить суть этих проблем любому человеку, который знает правила игры в шахматы. У этой задачи вообще очень интересная история. В своё время она привлекла внимание Гаусса, который даже сделал небольшую ошибку в её решении (на доске 8×8 он сообщил о 76 решениях, но потом сам признал четыре из них ошибочными, так что остались только 72, а позже Гаусс установил все 92 решения для доски 8×8).

Обобщение задачи для доски N×N привлекло внимание многих математиков. За последние полвека вышло несколько десятков научных работ, посвящённых этой проблеме. Как минимум шесть из них цитируются более 400 раз на Google Scholar: это Golomb & Baumert, 1965; Bitner & Reingold, 1975; Mackworth & Freuder, 1985; Minton, Johnston, Philips, & Laird, 1992; Selman, Levesque & Mitchell, 1992; Crawford, Ginsberg, Luks, & Roy, 1996.

Сложность задачи о N ферзях часто неправильно оценивают. Даже в обильно цитируемых работах её часто называют NP-сложной задачей (NP-hard), но она будет таковой только при условии, что P=NP. На самом деле вычислительный вариант задачи, то есть определение количества решений для N ферзей, представляет собой последовательность A000170 из Онлайн-энциклопедии целочисленных последовательностей. Эта последовательность сейчас известна максимум для n=27, где количество решений превышает 2,34×10 17 . Не известно ни одно более эффективное решение проблемы, чем простой перебор. Так, для n=27 в 2016 году использовался масштабный параллельный поиск на FPGA.

В то же время, если компьютер начнёт перебор возможных положений ферзей на доске 1000×1000 клеток, то он загрузится этой задачей навечно. По мнению учёных, если некто найдёт действительно быстрый и эффективный способ решения, то сможет извлечь из этого гораздо бóльшую выгоду, чем один миллион долларов от Математического института Клэя. «Если вы напишете программу, которая может решить проблему действительно быстро, вы могли бы адаптировать её для решения многих важных задач, с которыми мы сталкиваемся ежедневно, - говорит профессор информатики Ян Гент (Ian Gent), один из авторов научной работы. - Среди них тривиальные проблемы, такие как поиск самой большой группы ваших друзей в Facebook, которые не знают друг друга, или очень важные задачи, например, взлом кодов, которые обеспечивают безопасность всех наших онлайн-транзакций».

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

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

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

Модели и сложность задач

Пришло время собственно обсудить: а как это вообще все решать и насколько быстро это вообще можно сделать?

Линейный поиск для классической задачи

Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: и . Однако, задача решается без перебора вариантов! Т.е., для доски любого размера можно всегда расставить ферзей один за одним лесенкой:

Отсюда вывод, для N = 1 и N > 3 решение всегда есть (см. алго), а для N = 2 или N = 3
всегда нет (тривиально следует из доски). Это значит, что задача разрешимости для N ферзей (где нужно сказать есть решение или нет) решается тривиально за константное время (ну ок, конструктивно за линейное - расставить/проверить).

Самое время перепроверить прочитанное, читаем типичный заголовок "задачу о N ферзях признали NP-полной задачей" - у вас замироточили глаза?

Как считать число решений на практике

Вот тут начинается самое интересное: у количества решений задачи о расстановке ферзей даже есть своё имя - "последовательность A000170 ". На этом хорошие новости заканчиваются. Сложность задачи: выше NP и P#, на практике это означает, что оптимальное решение - это скачать данные последовательности в словарь и возвращать нужное число. Так как для N=27 оно уже считалось на параллельном кластере сколько там недель.

Решение : выписываем табличку и по n, возвращаем а(n)
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528

Однако, если у вас какая-то хитрая разновидность задачи и все-таки нужно посчитать решения (а их количество неизвестно и раньше их никто не посчитал), то лучший вариант прототипа обсуждается чуть ниже.

Дополнение до N и Answer Set Programming

Тут начинается самое интересное: в чём же состоит новый результат статьи? Задача о дополнении до N ферзей - NP-полна ! (Интересно, что про NP-полноту дополнения латинского квадрата было известно ещё в 1984-ом году.)

Что это означает на практике? Самый простой способ решишь эту задачу (или вдруг, если нам нужно её вариацию) - использовать SAT. Однако, мне больше нравится следующая аналогия:

SAT - это ассемблер для комбинаторных NP-задач, а Answer Set Programming (ASP) - это С++ (у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP , была придумана в 1988ом году Михаилом Гельфондом и Владимиром Лифшицем, работавших тогда в университетах Техаса и Стэнфорда соответственно).

Если говорить упрощенно: ASP - это декларативный язык программирования ограничений (constraints в англоязычной литературе) с синтаксисом Prolog. То есть мы записываем, каким ограничениям должно удовлетворять решение, а система сводит всё к варианту SAT и находит нам решение.

Детали решения здесь не столь важны, и Answer Set Programming достоин отдельного поста (который лежит у меня в черновике уже неприлично долго): поэтому разберем концептуальные моменты

Строка 1 { queen(X,Y) : column(Y) } 1:- row(X). - называется choice rule, и она определяет, что является допустимым пространством поиска.

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

В качестве системы для экспериментов рекомендую Clingo .
И для начала стоит посмотреть их tutorial и попочитать блог на www.hakank.org .

Безусловно, если впервые писать на ASP, то первая модель не выйдет невероятно эффективной и быстрой, но скорее всего будет быстрее перебора с возвратом, написанным на скорую руку. Однако, если понять основные принципы работы системы, ASP может стать "regexp для NP-полных задач".

Проведем простой численный эксперимент с нашей ASP моделью. Я добавил 5 коварных ферзей в модель и запустил поиск решения для N от 1 до 150 и вот, что вышло (запущено на обычном домашнем ноутбуке):

Итого, наша ASP модель примерно в течении минуты может найти решения задачи о дополнении при N <= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.

Выводы

• Новый результат связан не с классической задачей о 8 ферзях, а дополнении обобщенной задачи о ферзях (что интересно, но в целом закономерно);
• Сложность существенно возрастает, так как, коварно поставив ферзей на доске, можно сбить алгоритм, ставящий ферзей по какой-то фиксированной закономерности;
• Эффективно посчитать число решений нельзя (ну совсем; пока не случится какой-то ужас и P не сравняется с NP итд);
• Возможно этот результат повлияет на работу современных SAT систем, так как некоторые эксперты считают, что эта задача в чем-то проще классических NP-полных задач (но это только мнение)
• Если вам вдруг зачем-то нужно решать подобную задачу - лучше всего воспользуйтесь системами аля Answer Set Programming, специально для этого предназначенных

Глава 8. Задача о восьми ферзях

Задача о восьми ферзях, как и задача о ходе коня, является одной из самых знаменитых математических задач на шахматной доске. Если задачей о коне занимался Леонард Эйлер, то задача о ферзях привлекла внимание другого великого математика - Карла Гаусса.

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

Найти ту или иную расстановку ферзей, удовлетворяющую условию задачи, не так трудно (четыре решения приведены на рис. 43). Значительно труднее подсчитать общее число существующих расстановок; собственно, в этом и состоит задача о восьми ферзях. Ясно, что как и в случае ладей, больше восьми не атакующих друг друга ферзей на шахматной доске расставить невозможно. И, соответственно, на доске n×n необходимым образом нельзя расставить более n ферзей (в общем виде задача будет рассмотрена несколько ниже).

Рис. 43. Восемь ферзей, не угрожающих двуг другу на шахматной доске

Любопытно, что многие авторы ошибочно приписывают задачу о восьми ферзях и ее решение самому Гауссу. На самом деле первым ее сформулировал в 1848 г. немецкий шахматист М. Беццель. Доктор Ф. Наук (слепой от рождения) нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс увлекся задачей и нашел 72 решения, которые сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук (он привел их в упомянутой газете от 21 сентября 1850 г.). Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом, который в своих книгах немало места уделил рассматриваемой задаче.

Доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей).

В принципе, расставляя на доске восемь ферзей всевозможными способами, мы в конце концов найдем все устраивающие нас расстановки. Однако этот путь чересчур долог и скучен. Можно ограничиться только решениями соответствующей задачи о ладьях и отобрать среди них такие, в которых никакая пара ладей не стоит па одной диагонали. Но и в этом случае перебор довольно велик (понадобятся, как мы знаем, более 40000 попыток). Таким образом, при решении задачи «вручную» (а именно так поступали в прошлом веке) вынужденный перебор расстановок должен быть хорошо продуман. Известно много способов организовать более или менее разумный поиск искомых расположений ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике (в основном в прошлом столетии и начале нынешнего). В наш век вычислительных машин задача такого сорта не смогла бы вызвать столь живой интерес. Ведь достаточно составить несложную программу для ЭВМ - и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски вокруг центра на 90, 180 и 270° по часовой стрелке (поворот на 360° приводит к исходной позиции). Из данной расстановки ферзей новую можно получить также зеркальным отражением доски относительно одной из пунктирных прямых на рис. 43 (1-я позиция) . Например, из первой расстановки на этом рисунке при повороте доски на 90° мы получаем третью, а при отражении относительно линии, разделяющей королевский и ферзевый фланги, - четвертую. При помощи других поворотов и отражений можно получить еще пять решений.

Итак, при поворотах и отражениях доски из одной расстановки ферзей получаются, вообще говоря, семь новых. Доказано, что в общем случае на доске n×n (при n > 1) для любой расстановки n ферзей, не угрожающих друг другу, возможны лишь три ситуации: а) при одном отражении доски получается новая расстановка, а повороты и другие отражения ничего нового не дают; б) новое решение получается при повороте доски на 90°, а отражения дают еще две расстановки; в) все три поворота и четыре отражения доски приводят к восьми несовпадающим расстановкам (включая исходную).

В случае а) исходное решение называется дважды симметрическим, в случае б) - симметрическим, а в случае в) - простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует. Алгебраическую интерпретацию решений каждого класса можно найти у Окунева.

Множество (набор) расстановок восьми ферзей называется основным,если они, во-первых, не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи этих преобразований. Известно, что всякий набор основных решений задачи содержит ровно 12 позиций (расстановок восьми ферзей). Приведем одип из таких наборов:

Остальные 80 позиций получаются из этих двенадцати в результате поворотов и отражений доски. Первые 11 расстановок являются простыми, и лишь последняя - симметрической. Таким образом, всего на доске существует 11×8 + 1×4 = 92 расстановки восьми ферзей, не угрожающих друг другу.

Рассматривая основные расстановки, можно обнаружить те или иные интересные особенности их. Например, легко заметить внешнюю симметрию последней расстановки (2-я позиция на рис. 43). Это основное решение, единственное в своем роде, характеризуется также тем, что только у него центральная часть доски (квадрат 4×4) свободна от ферзей. Еще одно его свойство состоит в том, что ферзями не занята главная диагональ доски a1 - h8 (этим свойством обладает и первое основное решение).

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

Всякое решение задачи можно записать, как набор (t 1 , t 2 , … t 8), представляющий собой перестановку чисел 1, 2, …, 8. Здесь ti - номер горизонтали, на которой стоит ферзь i-й вертикали. Так как никакие два ферзя не находятся на одной горизонтали, то все t x различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i < j ≤ 8) имеем: |t j - t i | ≠ j - i.

Числовая запись расстановок ферзей иногда бывает очень удобной. Например, для нахождения расстановок при фиксированном расположении ферзя на a1 достаточно из всех 92 позиций, записанных в числовой форме, отобрать такие, у которых первая координата равна 1. Если фиксировано положение ферзя на d3, то следует выделить позиции, у которых на четвертом месте стоит число 3, и т. д.

Запишем числа 1, 2, …, 8 сначала по возрастанию, а потом по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки, например (3, 7, 2, 8, 5, 1, 4, 6):

Полученные суммы образуют два набора чисел: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Возникает следующая задача.

Какие перестановки чисел 1, 2,…, 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все числа различны?

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

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

Задача о n ферзях. На шахматной доске n×n расставить n ферзей так, чтобы они не угрожали друг другу.

На доске 1×1 один ферзь ставится на единственное поле, и решение существует. На доске 2×2 один ферзь, где бы он ни стоял, угрожает всем полям доски, и второго ферзя поставить некуда. При любой расстановке трех ферзей на доске 3×3 хотя бы два из них угрожают друг другу. Итак, при n, равном 2 или 3, задача не имеет решений.

Что касается случаев n > 3, то известно, что на любой доске n×n можно расставить n ферзей так. чтобы они не угрожали друг другу. Доказательству этого далеко не очевидного факта посвящено много статей, в том числе в серьезных математических изданиях.

На доске 4×4 существует единственная основная расстановка, причем дважды симметрическая (a2, b4, c1, d3), т. е. всего здесь имеется два решения. На доске 5×5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; всего же имеется десять искомых позиций. Интересно, что из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполнят все поля доски 5×5. Аналогичное наложение в общем случае возможно только при тех и, которые не делятся ни на 2, ни на 3. Из этого, в частности, следует, что для обычной доски подобрать восемь решепий, для которых ферзи заполняют всю доску, невозможно.

Обобщая указанное выше алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка (t 1 , t 2 , … t n) n ферзей на доске n×n является искомой, если для любых i, j (i < j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Сейчас мы опишем одну возможную схему искомого расположения n ферзей на доске n×n при всех n > 5. Доказательство того, что в полученных расстановках наше условие выполняется, можно найти, например, у Окунева или у Ягломов.

Рассмотрим последовательно ряд случаев. Пусть сначала n четно, причем n = 6k или n = 6k + 4. Половину всех ферзей поставим на первых n/2 вертикалях ходом коня, начиная со второй горизонтали и передвигаясь каждый раз на 2 поля вверх и на 1 вправо. Вторую половину поставим на оставшихся n/2 вертикалях тем же способом, но начиная с первой горизонтали. Для доски 6×6 (n = 6k, k = 1) это дает такую расстановку ферзей: a2, b4, c6, d1, e3, f5 (решение, представленное на рис. 45 для n = 10, получается иным образом).

При n = 6k + 2 предыдущий прием уже не проходит, и ферзей приходится расставлять более «хитрым» способом. Расположим их ходом коня со второй вертикали по

(n/2 - 2)-ю, начиная с третьей горизонтали, и далее с

(n/2 + 3)-й вертикали по (n - 1)-ю, начиная с шестой горизонтали. В результате свободными останутся шесть вертикалей и шесть горизонталей доски, на которых шесть ферзей должны занять поля с такими координатами: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). При n = 14 (n = 6k + 2, k = 2) получаем расстановку на рис. 44. Кстати, на обычной доске 8×8 (8 = 6k + 2, к = 1) расстановка восьми ферзей указанным способом совпадает все с тем же замечательным решением на рис. 43 (2-я позиция), но заметить закономерность расположения ферзей здесь вряд ли возможно.

Нам осталось рассмотреть задачу для нечетных значений n. Чтобы получить решение в этом случае, достаточно заметить, что в предложенных нами расстановках на «четных» досках главная диагональ (идущая из левого нижнего угла в правый верхний) оставалась свободной. Учитывая это обстоятельство, искомую расстановку n ферзей на доске n×n (при нечетном n) можно получить следующим образом. На вертикалях и горизонталях этой доски с номерами от 1 до (n - 1) расставим (n - 1) ферзя так, как это делается на доске (n - 1)×(n - 1) (n - 1 четно!), а затем n-то ферзя расположим в правом верхнем углу доски. Описанным способом можно получить первую расстановку ферзей на доске 5×5 из указанной расстановки на доске 4×4, а из расстановки ферзей на доске 6×6 имеем следующую для n = 7: a2, b4, c6, d1, e3, f5, g7.

«8 ферзей» – отличная задача-головоломка для развития логического . Эта online флеш-игра является своеобразной современной формулировкой известной шахматной задачи, придуманной шахматистом Максом Базелем в 1848 г.

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

Правила. Задача о 8 ферзях имеет своим единственным условием задание расставить на стандартной шахматной доске (64 клетки, 8х8) 8 фигур – ферзей, (или королев, если угодно), таким образом, чтоб ни одна из них не была под боем другой.

Вспоминается фраза из «Трех мушкетеров» Дюма, отпущенная Ришелье во время игры в шахматы с д’Артаньяном: «Это королева, она ходит как угодно». Эта цитата хоть в конкретном случае и была двойственной, но все же она для тех, кто незнаком с правилами игры в шахматы. Уточним, что ферзь ходит на любое поле по вертикали, горизонтали и диагонали, на любые расстояния.

Всего оригинальных решений 12. Общее количество возможных (с учетом применения операции симметрии) вариантов – 92. Первым опубликовал ответ на эту задачу в 1850 г. Франц Нак. С тех пор многие ученые решали и исследовали эту задачу, предлагая собственные варианты решения. Так, известный немецкий математик, механик и физик Карл Гаусс очень любил эту головоломку и находил 72 варианта возможной расстановки. Он творчески подошел к процессу поиска ответа – разные комбинации 8 ферзей достигались с помощью интересного приёма… поворота доски на 90, 180 и 270 градусов соответственно. Такое вот нетривиальное решение этой головоломки.

Задача достаточно сложная, но как минимум один вариант как правильно расставить ферзей находится довольно быстро и называется явным. Самое популярное правильное расположение достигается следующей расстановкой ферзей: a2, b4, c6, d8, e3, f1, g7, h5. Схема данной расстановки изображена на первом рисунке, оставшиеся три способа расставить ферзей были найдены при вращении шахматной доски.

Другие комбинации постарайтесь найти самостоятельно. Успехов!

Тренируемые навыки

При поиске ответа на задачу тренируются следующие навыки:

• – способность находить нестандартные решения интеллектуальных задач, действовать не на основе изобретенного алгоритма, адаптивно ведя поиск ответа;
• – вид умственной деятельности и избирательное направление восприятия, без которых концентрация на предмете невозможна;
• логическое мышление – вид мыслительного процесса, при котором знание достигается путем применения в рассуждении понятий и логических конструкций.

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