Пару месяцев назад появилась занятная статья с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.
Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)
Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:
- Отличная статья ---пресс служба университета---> невразумительный пресс-релиз.
- Пресс релиз ---занятный перевод---> непонятная статья на гиктаймс
Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.
Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.
О чём пойдёт речь:
- История задачи
- Три типа задачи "о ферзях"
- Модели и сложность
- Выводы
История задачи
Латинский квадрат
Задача известна еще с древности (~ средних веков), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:
Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.
Задача о восьми ферзях
Задачу придумал в 1848 году шахматный композитор Макс Беззель: суть задачи в том, чтобы расставить 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга. С тех пор многие математики, например Гаусс, работали над задачей, а алгоритмисты и программисты, такие как Дейкстра, придумали множество подходов к поиску и подсчету решений.
В задаче, о которой мы будем говорить, не 8 ферзей, а N и доска, соответственно, не обычная шахматная, а NxN.
Три типа задачи "о ферзях"
Есть три наиболее популярных постановки задачи о ферзях
Расстановка N ферзей
Задача формулируется очень прямолинейно.
Дано: пустая доска NxN, например 8х8
(в принципе понятно, что достаточно просто указать N, но так наглядней)
Найти: расстановку максимально возможного числа ферзей
Т.е. на вход число — размер доски, а на выход позиции ферзей (одного решения).
Подсчет числа решений
Задача ставится тоже достаточно просто:
Дано: размер пустой доски N
Найти: H число возможных расстановок N ферзей на доске
Например, размер доски N = 1, тогда число возможных расстановок H = 1.
N = 8 => H = 92.
Дополнение до N ферзей
Вот тут формулировка чуть-чуть коварней:
Дано: размер доски N и M позиций уже установленных ферзей
Найти: позиции оставшихся N — M ферзей
Визуально все как на КПДВ:
(картинка также из оригинальной статьи)
Вариации задачи
Вообще говоря, вариаций задачи больше: см. например: расстановку белых и черных ферзей
http://www.csplib.org/Problems/prob110
однако здесь мы рассматриваем только основной классический вариант.
В подобной вариации решения существенно отличаются (белые не бьют белых, а черные черных: в случае путаницы — см. комментарии тут):
(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного — но не обоих сразу; взято из статьи)
Модели и сложность задач
Пришло время собственно обсудить: а как это вообще все решать и насколько быстро это вообще можно сделать?
Линейный поиск для классической задачи
Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: Зачем нам всем нужен SAT и все эти 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 достоин отдельного поста (который лежит у меня в черновике уже неприлично долго): поэтому разберем концептуальные моменты
% domain
row(1..n).
column(1..n).
% alldifferent
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.Строка 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, специально для этого предназначенных
Комментарии (41)
CaptainTrunky
04.12.2017 10:39На мой взгляд, Answer Set Programming — одна из самых недооцененных технологий сегодня. Постараюсь как-нибудь рассказать, как с ее помощью мы вполне себе прикладные задачи решали.
varagian Автор
04.12.2017 11:40Отлично, надо бы организовать Хабра-цикл статей по ASP :-)
CaptainTrunky
04.12.2017 11:58+1Можно скооперироваться в личке, но я в любом случае адски занят до января. :)
varagian Автор
04.12.2017 12:00Не вопрос — мне тут еще диссертацию надо доредактировать, так что к январю — это еще хорошо :-)
CaptainTrunky
04.12.2017 12:03У меня защита кандидатской по ASP в этот четверг. :)
varagian Автор
04.12.2017 12:13Ого, эту сужает список возможных университетов где-то до 10 (на самом деле нет) :) Потсдам?
CaptainTrunky
04.12.2017 12:17Все куда более прозаично. Я при физтехе в Москве решал одну прикладную задачу с использованием ASP, ну и заодно в теории покопался знатно. До Постдама не дорос еще. :)
varagian Автор
04.12.2017 12:20Если это опубликовать, то в Потсдаме будут всегда рады — они активно ищут людей :-)
CaptainTrunky
04.12.2017 12:22+1Да, я думал уже с ними как-то связаться, показать, что мы тут на практике умеем. Но тут защита подкралась незаметно и стало резко не до того. :)
varagian Автор
04.12.2017 12:24ок, хорошо, как что — можно мне писать: скину Торстену, ему всегда интересно на приложения ASP посмотреть
trusted
05.12.2017 09:06Быть может в большей мере используется Constraint Programming (CP) из родственной ASP области. И в частности для решения прикладных задач.
На CP Minizinc (Gecode) для N=150 находит решение за 7 сек, а с дополнениями еще быстрее.
int: n; array [1..n] of var 1..n: q; predicate noattack(int: i, int: j, var int: qi, var int: qj) = qi != qj / qi + i != qj + j / qi - i != qj - j; constraint forall (i in 1..n, j in i+1..n) ( noattack(i, j, q[i], q[j]) ); solve satisfy; output [ if fix(q[i]) = j then "Q " else ". " endif ++ if j = n then "\n" else "" endif | i, j in 1..n ];varagian Автор
05.12.2017 10:42Ну технологии и правда родственные: главные CP и ASP конференции в этом году вообще вместе проводили. Где-то ASP чуть интересней, где-то CP. На мой вкус ASP как-то естественней, чем CP, особенно для реляционных задач, но тут я совсем biased :-)
trapwalker
04.12.2017 11:59+1Вот же ж хитрые ж… Я вспоминаю областную олимпиаду по информатике, куда я (девятиклассник тогда), приехал из своей деревни поучаствовать потому, что в моём районе особо не с кем было соперничать. Причем олимпиада была для 10 и 11 классов. И вот там было задание посчитать количество возможных расстановок ферзей. Короче не решил я ее тогда… да и про NP-полные задачи я не знал.
Insty
04.12.2017 13:12Мне довелось лично встретиться с автором статьи в Великобритании и обсудить в чем же конкретно заключается сложность задачи. Из-за невразумительного пресс-релиза у многих людей, которые не совсем в теме, возникло столько трактовок и предположений, что на авторов посыпалась лавина вопросов. В беседе со мной у одного из авторов статьи чувствовалось некоторое раздражение от необходимости в который раз отвечать на одни и те же вопросы. Немалую роль в этой ситуации сыграло упоминание вознаграждения в $1M.
Короче говоря, есть несколько задач связанных между собой, которые неразрешимы на данный момент для достаточно большой доски, например, 1000x1000:
1) нахождение числа всех возможный расстановок ферзей;
2) нахождение числа возможных расстановок, когда на доске уже установлены одна или более фигур;
3) нахождение хотя бы одной правильной расстановки, когда на доске уже установлены одна или более фигур (либо указание невозможности расставить остальные фигуры).
Последняя задача интуитивно кажется наиболее простой, однако так ли это на самом деле — неизвестно. Чтобы понять сложность задачи попробуйте расставить несколько ферзей случайным образом на большой доске и затем отыскать хотя бы одно решение, в котором фигуры не бьют друг друга.
Можно высказать предположение, что для достаточно большой доски существует алгоритм, расставляющий фигуры за меньшее количество операций, чем банальный поиск перебором (при условии что на доске уже стоит хотя бы одна фигура!). Если такой алгоритм будет найден или это предположение будет доказано иным способом, можно утверждать, что P=NP.varagian Автор
04.12.2017 13:23SAT не делает "банального поиска с перебором" — но это никак не даёт нам P=NP
third112
08.12.2017 05:53Можно высказать предположение, что для достаточно большой доски существует алгоритм, расставляющий фигуры за меньшее количество операций, чем банальный поиск перебором (при условии что на доске уже стоит хотя бы одна фигура!). Если такой алгоритм будет найден или это предположение будет доказано иным способом, можно утверждать, что P=NP.
можно утверждать = будет доказано?
varagian Автор
08.12.2017 12:21Если этот алгоритм полиномиальный для вообще любой NP полной задачи, то отсюда напрямую следует, что P = NP.
tyomitch
04.12.2017 19:21(белые не бьют белых, а черные черных)
Судя по иллюстрации, всё как раз наоборот?
у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP, была придумана в 1988ом году Михаилом Гельфондом и Владимиром Лифшицем
О да, фамилии выдают в них истинных носителей загадочной русской душиvaragian Автор
04.12.2017 20:03(белые не бьют белых, а черные черных)
Судя по иллюстрации, всё как раз наоборот?Если белые бьют белых, то как они стоят на одной строке? см. например самую верхнюю
О да, фамилии выдают в них истинных носителей загадочной русской души
Пушкину, она судя по этой логике, тоже не полагается?
tyomitch
04.12.2017 23:42(белые не бьют белых, а черные черных)
Судя по иллюстрации, всё как раз наоборот?
Если белые бьют белых, то как они стоят на одной строке? см. например самую верхнюю
Наоборот — это «белые не бьют чёрных, а чёрные белых».varagian Автор
04.12.2017 23:57Тут видимо у нас какая-то путаница в определениях: "белые не бьют белых" = белые не атакуют белых в принципе, т.е., это ок для решения, если белый ферзь стоит на одной диагонали, строке или столбце с другим белым ферзём — но это НЕ ок, если белый стоит на одной диагонали/строке/колонке с черным.
Видимо ваша интерпретация примерно такая, решение — это два множества пар W = { (x,y) } и B = { (x,y) }, таких ни один ферзь (x_w,y_w) из W "не бьёт" (= стоит на одной...) ни одного ферзя (x_b, y_b) из B.
Так? Если да, то это вопрос того, что означает фраза естественного языка: "белые не бьют белых" итд.
tyomitch
05.12.2017 12:22+1Да, я действительно понял «не бьют» как «ищется максимальная расстановка, в которой не бьют», тогда как у вас это означало «не способны бить, и при этом ищется максимальная расстановка».
Что касается загадочной русской души Пушкина: нам неизвестно, считал ли он себя русским, или его провозгласили русским «задним числом». Есть даже анекдот про это.vlanko
05.12.2017 14:42Уточню, две разные задачи. Вначале все ферзи равные — каждая не должна бить ни одну другую.
Во второй задаче, где черные и белые, белые не должны бить черных и наоборот (благо, для ферзей это одновременно).
Yggaz
05.12.2017 13:20+1Говоря, что фигура А «бьёт» фигуру Б, обычно имеют в виду, что фигура Б находится на поле, на которое фигура А может пойти. То есть «бить» и «атаковать» обычно используются как точные синонимы.
Посмотрите статью, например. Там формулировка исходной задачи именно такая: "расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого".
Кстати, и по вами приведённой ссылке: we are required to place two equal-sized armies of black and white queens on a chessboard so that the white queens do not attack the black queens (and necessarily vice versa) and to find the maximum size of two such armies.
А вы используете эти слова по-разному. Для вас «не бьёт», кажется, означает «не может срубить». То есть пусть себе атакует, последствий не будет всё равно.
И это несколько сбивает, да.varagian Автор
05.12.2017 13:25Ок, тут полностью согласен. Главное, что мы определили значение всех терминов и теперь путаницы нет. (Поставлю-ка я ссылку на эти комментарии в статье.)
LoadRunner
1x1
-
LoadRunner
Почта сохранила Ваш ответ. Не буду его цитировать, но остальным напомню про диагонали — в случае нечётного N именно там идут пересечения, если пользоваться лесенкой.
varagian Автор
Давайте сначала разберемся с тем, что кажется спорным:
LoadRunner
То, что я вижу на приведённом примере — совсем не «один за одним лесенкой».
Да, определённые паттерны есть, причём для N разной кратности можно найти свои паттерны. Но это не лесенка. Это больше напомнит Г — ход шахматного коня, потому что это самые ближайшие друг к другу клетки, с которых ферзи не бьют друг друга.
varagian Автор
Они не стоят "один за одним" — она ставятся один за одним (ставим первого, потом второго, третьего и никогда не меняем предыдущих позиций) — в этом разница с дополнением, там их нельзя поставить один за одним — их нужно ставить все сразу.
"Лесенка" тут взялась из того, что шаг алгоритма делает что-то похожее на ступеньку (иногда выскакивая за доску и делая mod оказывается на другой стороне) — хотите можете дать этому другое название — здесь это нужно исключительно в качестве иллюстрации, если не помогает, а буква Г помогает, то почему бы и нет.
Germanets
Более шахматный вариант — расположение по ходам коня друг от друга.
Azzzi
varagian Автор
4b атакует 1e, нет?
alvik48
b4-e1, c6-f3, d8-g5…
LoadRunner
Зарегистрироваться ради комментария и забыть про диагонали…