Разбираемся, что же там нового открыли в задаче о ферзях

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


    image
    Сможете поставить ещё шесть? А найти все решения?
    (картинка из статьи)


    Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:



    Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.


    Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.


    О чём пойдёт речь:



    Задачу придумал в 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, специально для этого предназначенных
    Поделиться публикацией

    Комментарии 44

      –1
      для доски любого размера можно всегда расставить ферзей один за одним лесенкой
      Спорное утверждение. Хотел бы увидеть для нечётного N. Например, для 9.
        0
        -
          +1
          Почта сохранила Ваш ответ. Не буду его цитировать, но остальным напомню про диагонали — в случае нечётного N именно там идут пересечения, если пользоваться лесенкой.
          +1

          Давайте сначала разберемся с тем, что кажется спорным:


          • Что для любого N >=4 есть решение? Подсчет числа решений вот в этой части даёт больше нуля всюду (N >= 4)
          • Что их можно один за одним расставить? Ну так обе ссылки в этой части описывают это в деталях
          • То, что "лесенкой"? В оригинале используется научный жаргон в духе "explicit solutions exhibit stair-stepped patterns" — который перевел "лесенкой" (если прям педантично переводить, то там должно быть "явные решения показывают закономерность сходную со ступеньками") и нужный пример вам пример даже есть по ссылке:
            0
            То, что я вижу на приведённом примере — совсем не «один за одним лесенкой».
            Да, определённые паттерны есть, причём для N разной кратности можно найти свои паттерны. Но это не лесенка. Это больше напомнит Г — ход шахматного коня, потому что это самые ближайшие друг к другу клетки, с которых ферзи не бьют друг друга.
              +3

              Они не стоят "один за одним" — она ставятся один за одним (ставим первого, потом второго, третьего и никогда не меняем предыдущих позиций) — в этом разница с дополнением, там их нельзя поставить один за одним — их нужно ставить все сразу.


              "Лесенка" тут взялась из того, что шаг алгоритма делает что-то похожее на ступеньку (иногда выскакивая за доску и делая mod оказывается на другой стороне) — хотите можете дать этому другое название — здесь это нужно исключительно в качестве иллюстрации, если не помогает, а буква Г помогает, то почему бы и нет.

              +1
              Более шахматный вариант — расположение по ходам коня друг от друга.
              0
              image
                +1

                4b атакует 1e, нет?

                  +1
                  b4-e1, c6-f3, d8-g5…
                  +2
                  Зарегистрироваться ради комментария и забыть про диагонали…
                +7
                На мой взгляд, Answer Set Programming — одна из самых недооцененных технологий сегодня. Постараюсь как-нибудь рассказать, как с ее помощью мы вполне себе прикладные задачи решали.
                  +3
                  Забавно. По ASP даже русской вики нет.
                    +6

                    Отлично, надо бы организовать Хабра-цикл статей по ASP :-)

                      +3
                      Можно скооперироваться в личке, но я в любом случае адски занят до января. :)
                        +3

                        Не вопрос — мне тут еще диссертацию надо доредактировать, так что к январю — это еще хорошо :-)

                          +6
                          У меня защита кандидатской по ASP в этот четверг. :)
                            0

                            Ого, эту сужает список возможных университетов где-то до 10 (на самом деле нет) :) Потсдам?

                              +1
                              Все куда более прозаично. Я при физтехе в Москве решал одну прикладную задачу с использованием ASP, ну и заодно в теории покопался знатно. До Постдама не дорос еще. :)
                                +1

                                Если это опубликовать, то в Потсдаме будут всегда рады — они активно ищут людей :-)

                                  +3
                                  Да, я думал уже с ними как-то связаться, показать, что мы тут на практике умеем. Но тут защита подкралась незаметно и стало резко не до того. :)
                                    0

                                    ок, хорошо, как что — можно мне писать: скину Торстену, ему всегда интересно на приложения ASP посмотреть

                      +1
                      Быть может в большей мере используется 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
                      	];

                        +1

                        Ну технологии и правда родственные: главные CP и ASP конференции в этом году вообще вместе проводили. Где-то ASP чуть интересней, где-то CP. На мой вкус ASP как-то естественней, чем CP, особенно для реляционных задач, но тут я совсем biased :-)

                      +4
                      Вот же ж хитрые ж… Я вспоминаю областную олимпиаду по информатике, куда я (девятиклассник тогда), приехал из своей деревни поучаствовать потому, что в моём районе особо не с кем было соперничать. Причем олимпиада была для 10 и 11 классов. И вот там было задание посчитать количество возможных расстановок ферзей. Короче не решил я ее тогда… да и про NP-полные задачи я не знал.
                        +3
                        Мне довелось лично встретиться с автором статьи в Великобритании и обсудить в чем же конкретно заключается сложность задачи. Из-за невразумительного пресс-релиза у многих людей, которые не совсем в теме, возникло столько трактовок и предположений, что на авторов посыпалась лавина вопросов. В беседе со мной у одного из авторов статьи чувствовалось некоторое раздражение от необходимости в который раз отвечать на одни и те же вопросы. Немалую роль в этой ситуации сыграло упоминание вознаграждения в $1M.
                        Короче говоря, есть несколько задач связанных между собой, которые неразрешимы на данный момент для достаточно большой доски, например, 1000x1000:
                        1) нахождение числа всех возможный расстановок ферзей;
                        2) нахождение числа возможных расстановок, когда на доске уже установлены одна или более фигур;
                        3) нахождение хотя бы одной правильной расстановки, когда на доске уже установлены одна или более фигур (либо указание невозможности расставить остальные фигуры).
                        Последняя задача интуитивно кажется наиболее простой, однако так ли это на самом деле — неизвестно. Чтобы понять сложность задачи попробуйте расставить несколько ферзей случайным образом на большой доске и затем отыскать хотя бы одно решение, в котором фигуры не бьют друг друга.
                        Можно высказать предположение, что для достаточно большой доски существует алгоритм, расставляющий фигуры за меньшее количество операций, чем банальный поиск перебором (при условии что на доске уже стоит хотя бы одна фигура!). Если такой алгоритм будет найден или это предположение будет доказано иным способом, можно утверждать, что P=NP.
                          +1

                          SAT не делает "банального поиска с перебором" — но это никак не даёт нам P=NP

                            0
                            Можно высказать предположение, что для достаточно большой доски существует алгоритм, расставляющий фигуры за меньшее количество операций, чем банальный поиск перебором (при условии что на доске уже стоит хотя бы одна фигура!). Если такой алгоритм будет найден или это предположение будет доказано иным способом, можно утверждать, что P=NP.


                            можно утверждать = будет доказано?

                              0

                              Если этот алгоритм полиномиальный для вообще любой NP полной задачи, то отсюда напрямую следует, что P = NP.

                              0
                              Вот хорошее пояснение к тем проблемам, что вы описали
                                0

                                А можно весьма наивный вопрос?


                                есть несколько задач связанных между собой, которые неразрешимы на данный момент для достаточно большой доски, например, 1000x1000:
                                [...]
                                3) нахождение хотя бы одной правильной расстановки, когда на доске уже установлены одна или более фигур

                                Если рассмотреть вырожденный случай, когда у нас уже есть готовое корректное решение для доски 999х999, правильно ли я понимаю, что задача дополнения до доски в 1000 тривиальна: надо просто проверить диагональ в доске 999? И аналогичное верно для любого перехода от расставленной доски n-1 к доске n?


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


                                Ну и в качестве второго вопроса: вот тут человек, вроде как, пишет, что разработал алгоритм дополнения за линейное (!) время. Пора хоронить P vs NP, или я неправильно что-то прочитал?

                                  0
                                  Если вся доска 999х999 заполнена корректно, то дополнить в принципе несложно (надо перебрать все оставшиеся клетки, например) — только задача не в этом.

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

                                  Я уже отвечал этому человеку в личной переписке, кажется, он не очень понимает некоторых вещей, если честно. Есть алгоритм для P = NP за линейное время? Мы хотим результатов на стандартных SAT benchmarks с корректными результатами и линейным временем исполнения. Доказательств нет, но есть громкие заявления.
                                    0
                                    Если вся доска 999х999 заполнена корректно, то дополнить в принципе несложно (надо перебрать все оставшиеся клетки, например) — только задача не в этом.

                                    Я понимаю, что задача не в этом. Я просто не так давно начал смотреть на n-queens, и хотел проверить свою интуицию для конкретного очень простого случая — просто потому, что если я и в таком простом случае ошибаюсь, то рассуждать дальше мне не стоит.


                                    Спасибо за ответ.

                                +3

                                "Если, говорить упрощенно" — я завис на этой запятой

                                  0

                                  Упси, спасибо — исправлено :-)

                                  –2
                                  (белые не бьют белых, а черные черных)

                                  Судя по иллюстрации, всё как раз наоборот?

                                  у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP, была придумана в 1988ом году Михаилом Гельфондом и Владимиром Лифшицем

                                  О да, фамилии выдают в них истинных носителей загадочной русской души
                                    0
                                    (белые не бьют белых, а черные черных)
                                    Судя по иллюстрации, всё как раз наоборот?

                                    Если белые бьют белых, то как они стоят на одной строке? см. например самую верхнюю


                                    О да, фамилии выдают в них истинных носителей загадочной русской души

                                    Пушкину, она судя по этой логике, тоже не полагается?

                                      +1

                                      Пушкину полагается, а вот Фету нет :^)

                                        0
                                        (белые не бьют белых, а черные черных)
                                        Судя по иллюстрации, всё как раз наоборот?

                                        Если белые бьют белых, то как они стоят на одной строке? см. например самую верхнюю

                                        Наоборот — это «белые не бьют чёрных, а чёрные белых».
                                          +3

                                          Тут видимо у нас какая-то путаница в определениях: "белые не бьют белых" = белые не атакуют белых в принципе, т.е., это ок для решения, если белый ферзь стоит на одной диагонали, строке или столбце с другим белым ферзём — но это НЕ ок, если белый стоит на одной диагонали/строке/колонке с черным.


                                          Видимо ваша интерпретация примерно такая, решение — это два множества пар W = { (x,y) } и B = { (x,y) }, таких ни один ферзь (x_w,y_w) из W "не бьёт" (= стоит на одной...) ни одного ферзя (x_b, y_b) из B.


                                          Так? Если да, то это вопрос того, что означает фраза естественного языка: "белые не бьют белых" итд.

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

                                            Что касается загадочной русской души Пушкина: нам неизвестно, считал ли он себя русским, или его провозгласили русским «задним числом». Есть даже анекдот про это.
                                              0
                                              Уточню, две разные задачи. Вначале все ферзи равные — каждая не должна бить ни одну другую.
                                              Во второй задаче, где черные и белые, белые не должны бить черных и наоборот (благо, для ферзей это одновременно).
                                              +2
                                              Говоря, что фигура А «бьёт» фигуру Б, обычно имеют в виду, что фигура Б находится на поле, на которое фигура А может пойти. То есть «бить» и «атаковать» обычно используются как точные синонимы.
                                              Посмотрите статью, например. Там формулировка исходной задачи именно такая: "расставить на шахматной доске 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.

                                              А вы используете эти слова по-разному. Для вас «не бьёт», кажется, означает «не может срубить». То есть пусть себе атакует, последствий не будет всё равно.

                                              И это несколько сбивает, да.
                                                +1

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

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

                                      Самое читаемое