- PVSM.RU - https://www.pvsm.ru -
Пару месяцев назад появилась занятная статья [1] с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.
Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)
Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:
Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.
Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.
О чём пойдёт речь:
Задача известна еще с древности (~ средних веков [17]), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:
Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.
Задачу придумал в 1848 году шахматный композитор [18] Макс Беззель: суть задачи в том, чтобы расставить 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга. С тех пор многие математики, например Гаусс, работали над задачей, а алгоритмисты и программисты, такие как Дейкстра, придумали множество подходов к поиску и подсчету решений.
В задаче, о которой мы будем говорить, не 8 ферзей, а N и доска, соответственно, не обычная шахматная, а NxN.
Есть три наиболее популярных постановки задачи о ферзях
Задача формулируется очень прямолинейно.
Дано: пустая доска NxN, например 8х8
(в принципе понятно, что достаточно просто указать N, но так наглядней)
Найти: расстановку максимально возможного числа ферзей
Т.е. на вход число — размер доски, а на выход позиции ферзей (одного решения).
Задача ставится тоже достаточно просто:
Дано: размер пустой доски N
Найти: H число возможных расстановок N ферзей на доске
Например, размер доски N = 1, тогда число возможных расстановок H = 1.
N = 8 => H = 92.
Вот тут формулировка чуть-чуть коварней:
Дано: размер доски N и M позиций уже установленных ферзей
Найти: позиции оставшихся N — M ферзей
Визуально все как на КПДВ:
(картинка также из оригинальной статьи)
Вообще говоря, вариаций задачи больше: см. например: расстановку белых и черных ферзей
http://www.csplib.org/Problems/prob110 [19]
однако здесь мы рассматриваем только основной классический вариант.
В подобной вариации решения существенно отличаются (белые не бьют белых, а черные черных):
(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного — но не обоих сразу; взято из статьи [20])
Пришло время собственно обсудить: а как это вообще все решать и насколько быстро это вообще можно сделать?
Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: Зачем нам всем нужен SAT и все эти P-NP (часть первая) [21] и вторая вот тут [22]. Однако, задача решается без перебора вариантов! Т.е., для доски любого размера можно всегда расставить ферзей один за одним лесенкой:
Существует целый ряд алгоритмов расстановки, например см. вот эту статью [23] или даже вот тут в Вики [24].
Отсюда вывод, для N = 1 и N > 3 решение всегда есть (см. алго), а для N = 2 или N = 3
всегда нет (тривиально следует из доски). Это значит, что задача разрешимости для N ферзей (где нужно сказать есть решение или нет) решается тривиально за константное время (ну ок, конструктивно за линейное — расставить/проверить).
Самое время перепроверить прочитанное, читаем типичный заголовок "задачу о N ферзях признали NP-полной задачей" — у вас замироточили глаза?
Вот тут начинается самое интересное: у количества решений задачи о расстановке ферзей даже есть своё имя — "последовательность A000170 [25]". На этом хорошие новости заканчиваются. Сложность задачи: выше 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 ферзей — NP-полна! (Интересно, что про NP-полноту дополнения латинского квадрата было известно [26] ещё в 1984-ом году.)
Что это означает на практике? Самый простой способ решишь эту задачу (или вдруг, если нам нужно её вариацию) — использовать SAT. Однако, мне больше нравится следующая аналогия:
SAT — это ассемблер для комбинаторных NP-задач, а Answer Set Programming (ASP) — это С++ (у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP [27], была придумана в 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 [28].
И для начала стоит посмотреть их tutorial [29] и попочитать блог на www.hakank.org [30].
Безусловно, если впервые писать на ASP, то первая модель не выйдет невероятно эффективной и быстрой, но скорее всего будет быстрее перебора с возвратом, написанным на скорую руку. Однако, если понять основные принципы работы системы, ASP может стать "regexp для NP-полных задач".
Проведем простой численный эксперимент с нашей ASP моделью. Я добавил 5 коварных ферзей в модель и запустил поиск решения для N от 1 до 150 и вот, что вышло (запущено на обычном домашнем ноутбуке):
Итого, наша ASP модель примерно в течении минуты может найти решения задачи о дополнении при N <= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.
Автор: varagian
Источник [31]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/269781
Ссылки в тексте:
[1] занятная статья: http://www.jair.org/papers/paper5512.html
[2] невразумительный пресс-релиз: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
[3] непонятная статья на гиктаймс: https://geektimes.ru/post/292631/
[4] История задачи: https://habr.ru/post/343738/#history
[5] Латинский квадрат: https://habr.ru/post/343738/#latin_square
[6] Задача о восьми ферзях: https://habr.ru/post/343738/#eight_queens
[7] Три типа задачи "о ферзях": https://habr.ru/post/343738/#types
[8] Расстановка N ферзей: https://habr.ru/post/343738/#classic
[9] Подсчет числа решений: https://habr.ru/post/343738/#counting_problem
[10] Дополнение до N ферзей: https://habr.ru/post/343738/#completion
[11] Вариации задачи: https://habr.ru/post/343738/#other
[12] Модели и сложность: https://habr.ru/post/343738/#problems
[13] Линейный поиск для N ферзей: https://habr.ru/post/343738/#linear
[14] Как считать число решений на практике: https://habr.ru/post/343738/#counting
[15] Дополнение до N: https://habr.ru/post/343738/#asp
[16] Выводы: https://habr.ru/post/343738/#conclusions
[17] ~ средних веков: http://vbn.aau.dk/files/13649565/R-2007-32.pdf
[18] шахматный композитор: https://ru.wikipedia.org/wiki/%D0%A8%D0%B0%D1%85%D0%BC%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%82%D0%BE%D1%80
[19] http://www.csplib.org/Problems/prob110: http://www.csplib.org/Problems/prob110
[20] статьи: https://www.researchgate.net/publication/221353569_Models_and_Symmetry_Breaking_for_%27Peaceable_Armies_of_Queens%27
[21] Зачем нам всем нужен SAT и все эти P-NP (часть первая): https://habrahabr.ru/post/207112/
[22] вторая вот тут: https://habrahabr.ru/post/208774/
[23] эту статью: https://www.researchgate.net/publication/234812180_Explicit_solutions_to_the_N_-queens_problem_for_all_N
[24] даже вот тут в Вики: https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions
[25] A000170: https://oeis.org/A000170
[26] было известно: http://www.sciencedirect.com/science/article/pii/0166218X84900751?via%3Dihub
[27] теория, лежащая в основе современного ASP: http://www.cs.utexas.edu/users/vl/papers/stable.ps
[28] Clingo: https://github.com/potassco/clingo
[29] tutorial: https://potassco.org/doc/start/
[30] www.hakank.org: http://www.hakank.org/constraint_programming_blog/2010/12/a_first_look_at_answer_set_programming.html
[31] Источник: https://habrahabr.ru/post/343738/
Нажмите здесь для печати.