Сколькими способами можно расставить 4 ферзей на доске размера 44

Обновлено: 01.05.2024

Имеется квадратная доска 4 на 4. Расставить на доске 4 ферзя так, чтобы они не били друг друга. Ферзь бьет поля, расположенные на той же горизонтали, вертикали и диагоналях (на рисунке знаком Х отмечены те поля, которые бьет ферзь, помещенный в поле, отмеченное Q).
Рассмотреть граф поиска, предложить различные оценочные функции и сравнить их применение.

сергей кротегов Искусственный Интеллект (117624) Какое тут подробное, ставь на доску и смртри. В перво столбе 2 сверху, во втором 4 в третьем 1 в четвертом 3

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

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

получается матрица (вместо 9 пишу 09, что бы выровнять строки по ширине)
09 09 09 09
09 11 11 09
09 11 11 09
09 09 09 09

Теперь от каждой ячейки каждой строки отнимем значение, стоящее в самой левой ячейке этой же строки (сама ячейка обнулится). И так сделаем, пока не останется один необнулённый столбец
00 | 00 00 00
00 | 02 02 00
00 | 02 02 00
00 | 00 00 00

00 00 | 00 00
00 00 | 00 -2
00 00 | 00 -2
00 00 | 00 00

00 00 00 | 00
00 00 00 | -2
00 00 00 | -2
00 00 00 | 00

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

В итоге получим 2 возможных варианта, которые по сути являются зеркальными отражениями.
Такое решение может быть чистым совпадением, конечно. А может и нет (по крайней мере звучит очень правдоподобно, при чём нарочно решение под результат не подгонялось).

Но от Вас ожидают в любом случае другого, то что я написал, просто весёлая заметка :)) . От Вас ожидают граф поиска (который, если я правильно понимаю, будет древовидным). А "оценочные функции" скорее всего имеется ввиду критерии, по которым сразу можно сказать, что такая комбинация невозможна, и перебор указанной ветки продолжать не имеет смысла. Ну например, если при установке на доске первых двух ферзей, они уже бьют друг-друга, продолжать не имеет смысла и следует одного из них переставить.

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

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

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

Отличная статья ---пресс служба университета--->невразумительный пресс-релиз.
Пресс релиз ---занятный перевод--->непонятная статья на гиктаймс

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

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

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

Латинский квадрат

Задача известна еще с древности (~ средних веков), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:

Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.

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

Задачу придумал в 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 ферзей

Визуально все как на КПДВ:

(картинка также из оригинальной статьи)

Вариации задачи

В подобной вариации решения существенно отличаются (белые не бьют белых, а черные черных: в случае путаницы — см. комментарии тут):

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

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

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

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

Существует целый ряд алгоритмов расстановки, например см. вот эту статью или даже вот тут в Вики.

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

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

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

Решение: выписываем табличку и по 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: и они определяют каким ограничениям должно удовлетворять решение: не может быть ферзя в одном и том же ряду, не может быть ферзя в одной и той же колонке (опущено, в силу симметрии) и не может быть ферзя на одной и той же диагонали.

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

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

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

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

Учёные отмечают, что эта задача может быть самой простой среди 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 ферзях быстрым и эффективным способом. За доказательство, что существует более эффективный способ решения задачи, чем простой перебор всех вариантов, дадут миллион долларов.

Научная статья опубликована в августе 2017 года в журнале Journal of Artificial Intelligence Research (doi:10.1613/jair.5512, pdf).

Недавно разбирался в старых своих наработках/скриптах и наткнулся на скрипт где решалась задача о ферзях. Собственно это послужило написанию статьи о том как проходили этапы написания его алгоритма. Возможно пригодится начинающим программистам для решения похожих задач (код в примерах написан на java).

Вступление

4 года назад была шумиха по поводу задачи о расположении 1000 ферзей на доске 1000х1000. Дело в том что расположение ферзей так чтобы они не били друг друга на доске является задачей с большим количество итераций и как результат долгой по времени выполнения. Как и многим мне захотелось проверить можно ли её решить за приемлемое время.

Изучение задачи

На картинке расположено 8 ферзей которые не пересекаются по горизонтальной, вертикальной или диагональным линиям.

Надо написать скрипт который будет расставлять на доске ферзей по таким правилам.

Алгоритм нахождения ферзей

Для поиска фигур была выбрана рекурсия.

Описание метода который вызывает сам себя:

Если переданная клетка пересекается с другими фигурами то возвращаем false

Если переданная клетка не пересекается ни с кем то:

устанавливает флаг на доске в true для этой позиции.

Если мы дошли до конца (нету следующего ряда) то возвращаем true .

Находит первую клетку в следующем ряду и вызывает сам себя с новой клеткой.

Если вернулся false то отправляем следующую клетку из ряда или если не осталось клеток то возвращаем false ) Предварительно ставим флаг в false на доске у клетки которую изначально получили.

Если вернулся true то возвращаем результат.

Такой метод для досок 8x8, 32x32, 50x50 отрабатывает хоть как то. Но если больше то уходит много времени.

Оптимизация

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

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

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

После этого результат можно было получить вплоть до 400x400.

Уменьшение возможных комбинаций

Есть множество комбинаций как расположить ферзей на доске.
Это и есть самая главная сложность в задаче.
Но в данном случае нужно найти лишь одну правильную комбинацию.

Обратите внимание на картинку.
Часть ферзей можно расположить заранее на доску в соответствии с правилами.
Нужно лишь начать с второй клетки первого ряда и дальше добавлять новые фигуры по формуле "row+1" и "column+2" Этот алгоритм заполнит половину ферзей на доске, а дальше всё сделает скрипт оптимизации который будет находить ряды с наименьшим числом клеток и устанавливать там фигуры.

Поиск на доске 1000x1000 занял ~4 минуты (на процессоре: Intel Core i5-10400H CPU 2.60GHz).

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

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

Обратный поиск состоит из трех частей: рекурсивной функции, получающей набор решений, который может быть незавершенным n, мутации — дополнения к n, добавляемой к набору n, а также проверки решения на завершенность и верность, которая проверяет завершение мутаций набора решений — полноценно ли данное решение? и верность — является ли решение приемлемым с подставленными на данный момент значениями?.

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

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

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

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

Решение методом грубой силы (brute-force) будет следующим: нужно перебрать каждую комбинацию N-ферзей в каждой из N на N точек — N² и выбрать N возможных вариантов.

Если изобразить график, где x представляет N, а y — число вероятностей для поиска, то он устремится вверх.

Только для стандартной сетки 8 на 8 существует 4,426,165,368 возможных комбинаций, перебор которых займет непозволительно много времени. Это можно частично улучшить, никогда не располагая двух ферзей в одном ряду или столбце, но нам по-прежнему потребуется перебрать каждый ряд и каждую клетку — время выполнения O(N²) будет недостаточно быстрым.

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

Можно ли построить частичные решения?

Да. Мы можем частично построить решение, поместив на доску определенное число ферзей.

Можно ли оценить эти частичные решения как верные или неверные?

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

Можно ли оценить решение как конечное?

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

Давайте построим алгоритм обратного поиска для решения этой задачи за более короткое время.

Получает N и список чисел board .
Инициализирует board как пустой список, если он не определен, и count как 0 .
Для каждого столбца x в N
>> добавляет индекс столбца x к board .
>> Если board верна — добавляет вывод n_queens с вводами N и board к count , что инициализирует очередной цикл функции и представляет туннелирование или процесс построения дерева обратного поиска. Поскольку частичное решение рассматривается в данном кейсе как верное, оно инициирует еще один экземпляр функции n_queens .
>> В противном случае удаляет столбец x .
Возвращает count .

Функция для оценки верности доски действует следующим образом:

Получает список чисел board , где каждое число соответствует одному столбцу.
Ряд последнего добавленного ферзя представляет текущую длину доски минус один, так как индексация начинается с 0, а столбец текущего ферзя является последним элементом доски.
Для каждого ряда R и столбца C на доске, состоящей только из расставленных ферзей.
>> находит разницу между столбцом только что добавленного ферзя и текущим столбцом C . Если она равна 0 , т.е. два столбца одинаковы, то возвращает False и выходит из функции.
>> находит разницу между столбцом только что добавленного ферзя и текущим столбцом R . Если она равняется 0 , т.е. оба столбца одинаковы, то возвращает False и выходит из функции.
В противном случае возвращает True .

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

Результаты, где индекс указывает значение N:

Дается начальный аэропорт и неупорядоченный список рейсов, каждый из которых представлен парой откуда-куда. Нужно вычислить маршрут пассажира. Если таковой не существует — вернуть na , при этом в маршруте должны быть использованы все рейсы.

Давайте в качестве примера возьмем эти рейсы:

HNL ➔ AKL
YUL ➔ ORD
SFO ➔ HNL
ORD ➔ SFO

С помощью грубой силы переберем пермутацию рейсов и проверим, является ли она верным маршрутом, делая это O(n!) раз.

Давайте снова пройдем по чек листу вопросов.

Можно ли построить частичные решения?

Да, такие решения можно построить путем составления неполного маршрута наподобие SFO ➔ HNL ➔ ORD ➔ ?.

Можно ли оценить эти частичные решения как верные или неверные?

Решение можно оценить как неверное, если из последнего пункта “куда” маршрута нет доступных рейсов и при этом остаются рейсы, которые можно осуществить. А поскольку использовать необходимо все рейсы, можно считать, что мы достигли заключительного узла.

Можно ли оценить решение как конечное?

Да, решение оценивается как конечное, когда маршрут включает все рейсы.

Построение логики решения:

Получает неупорядоченный список flights с элементами в форме origin/destination (откуда/куда) и current_itinerary , представляющим список маршрута, где первый элемент представляет начальный аэропорт, а второй пункт “куда” первого рейса (он же пункт “откуда” для второго рейса и т.д.).
Если все flights были использованы, возвращает current_itinerary .
last_stop будет равна последнему элементу current_itinerary .
Для каждой пары origin/destination в рейсах:
>> добавляет destination к current_itinerary .
>> Если origin равняется last_stop (это проверка, определяющая верность связи рейсов) —
>>>> возвращает еще одно выполнение get_itinerary со всеми рейсами за исключением текущей пары origin/destination и выходит из функции.
>> В противном случае удаляет последнюю destination .
Возвращает None , если ни один из предыдущих поисков по дереву не смог вернуть решение.

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

Обратите внимание, что для конкретно этой задачи существует гораздо более эффективное решение, и поиск с возвратом здесь мы использовали просто в качестве примера. В реальности быстрее было бы просто взять начальный аэропорт (например, SFO), найти среди рейсов связанный с ним аэропорт (SFO в HNL) и добавить пункт “куда” в расписание, продолжая это делать рекурсивно.

Можем ли мы применить поиск с возвратом для решения стандартной загадки судоку?

Можно ли построить частичное решение?

Да, можно частично заполнить позиции на доске судоку.

Можно ли оценить эти частичные решения как верные или неверные?

Да, если в частичном решении присутствуют какие-либо числа, совпадающие с числами в строке, столбце или блоке — такое решение будет неверным. В противном случае — верным.

Можно ли оценить решение как конечное?

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

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

Получает переменную board , являющуюся массивом, где каждое значение представляет ячейку доски.
Если board заполнена, возвращает board и выходит из функции.
Пусть r и c представляют строку и столбец первого пустого значения на доске.
Для каждого значения i в [1, 2, 3, 4, 5, 6, 7, 8, 9]
>> устанавливает ячейку r строки и c столбца как i .
>> Если board остается верна,
>> >> выполняет еще один экземпляр sudoku для данной board .

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

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

Читайте также: