Ni boyinsha

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

Таким образом, игра начинается с начального состояния и может закончиться набором конечных состояний. Два промежуточных состояний связаны, если существует операция между двумя состояниями. Чтобы найти выигрышный путь (или, по крайней мере, ничью), нужно искать путь через пространство состояний с помощью представления дерева, как на графике, который вы видите здесь. Широко используемая стратегия для поиска решения в пространстве состояний называется откатом. Откат это общая стратегия решения задачи для систематического поиска решения проблемы среди всех возможных вариантов и стеки часто используются в реализации алгоритмов отката.
Легче всего проиллюстрировать, как откат работает с использованием примеров. Классическим примером использования отката в поиске решения является проблема n-ферзей. Для тех, кто играл в шахматы раньше, вы знаете, что ферзь является самой сильной фигурой в шахматах. Он может перемещаться на любое количество шагов по вертикали, горизонтали и даже по диагонали. В шахматной игре, каждый игрок имеет только одного ферзя, но в задаче n-ферзей, есть в общей сложности n ферзей, то есть, для обычной 8x8 шахматной доски, там будет 8 ферзей. В общем, n может быть любым числом.
Цель задачи n-ферзей является размещение n ферзей на шахматной доске nxn так, чтобы никакие два ферзя не смогут нападать друг на друга. Давайте использовать n равный 5 в качестве примера. Вот 5x5 шахматная доска.

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

Размещение этого второго ферзя устранит все остальные позиции в этой строке и все другие позиции в столбце с индексом 2. Что касается диагонали, в действительности существует два диагонали, как показано на схеме здесь. По аналогии разместим остальных ферзей и у нас есть наше первое решение проблемы 5-ферзей. Вы можете проверить, чтобы убедиться, что в этом решении, никакие два ферзя не могут нападать друг на друга по горизонтали, вертикали или диагонали.
Прежде чем двигаться дальше, вы можете сначала подумать о том, существуют ли другие варианты решения проблемы 5-ферзей.Теперь, когда вы понимаете, что представляет собой проблема n-ферзей, давайте подумаем о том, как мы можем решить эту проблему. Я буду использовать пример здесь, чтобы проиллюстрировать стратегию, которую мы собираемся использовать, чтобы решить проблему n-ферзей.

Мы разместим ферзей с первой строки по последней строки, и будем двигаться от самого левого столбца до самого правого столбца в каждой строке. Давайте поместим первого ферзя в 0,0 положение, и мы будем использовать стек для хранения промежуточных решений. Значение, сохраненное в стеке, является меткой столбца, в данном случае, 0. Нам не нужно хранить метку строки, потому что мы можем использовать позицию элемента стека для обозначения метки строки.
После того, как у нас есть ферзь на определенной строке, мы не должны пытаться поставить другого ферзя в той же строке, потому что они могут нападать друг на друга в горизонтальном направлении. Теперь мы можем двигаться дальше, чтобы попытаться поместить второго ферзя на 2-й строке. Мы начнем с 1-го столбца, это не является правильным шагом. И мы постараемся двигать ферзя вправо или на 2-й столбец. Опять же, есть конфликт, потому что первый ферзь может атаковать по диагонали.
2-й ферзь перемещается в следующий столбец снова, и это будет признано безопасной позицией, и это положение, то есть столбец с индексом 2, как метка записывается в стек. Теперь мы можем попытаться поместить третьего ферзя в 3-й строке, начиная с 1-го столбца.Конфликт возникает с первым ферзем, так что он перемещается в следующий столбец. Это не хорошо, потому что конфликт возникает со 2-м ферзем. Следующий столбец тоже не хорош, потому что это находится в противоречии как с 1-м, так и со 2-м ферзем.
Точно так же, 4-й столбец также исключен из-за 2-го ферзя. Так мы остались в последнем столбце, и к счастью, нет конфликтов с остальными ферзями. И позиция 4 теперь может быть записана в стек. Размещение 4 ферзя может быть получена с использованием той же стратегии и метка 1 записывается в стек. Точно так же, правильное размещение получается и для последнего ферзя и метка 3 помещается в стек. Так что это первое решение, которое мы получили в задаче 5-ферзей. Что делать, если мы хотим получить все решения?
Где мы должны возвратиться к предыдущему шагу и определить, где продолжать искать другое решение. Поскольку нынешние позиции всех ферзей записываются в стек, мы можем удалить верхний элемент из стека, чтобы узнать местоположение предыдущего движения. Установлено, что 5-й ферзь был помещен в столбец с меткой 3, так что вместо того, чтобы начинать с самого левого столбца, как то, что мы делали раньше, мы можем начать проверять следующий столбец с этой позиции. Установлено, что эта позиция в конфликте с обеими, первым и третьим ферзем.
В этом случае, если мы будем двигаться дальше вправо, ферзь будет перемещен за пределы доски, что не позволительно. Это означает, что не будет другого решения с текущим размещением предыдущих 4 ферзей. Так что мы должны вернуться к предыдущей строке, и начать поиск решения. Чтобы узнать текущее размещение ферзя на 4-й строке, верхний элемент в стеке удаляется и дает метку 1 или второй столбец. Так он может двигаться вправо от этой позиции, а не из первого столбца.
К сожалению, все остальные позиции в строке находятся в противоречии с предыдущими ферзями. Когда ферзь перемещается за пределы доски, мы знаем, что новое решение не может быть найдено с текущим размещением предыдущих 3 ферзей. Таким образом, мы должны двигаться на одну строку вверх, вынимая верхний элемент из стека и пробуя еще раз. В случае, если ферзь уже в последнем столбце, следующая позиция будет двигать его за пределы доски. Таким образом, мы должны двигаться на одну строку вверх снова. Мы обнаружили, что второй ферзь в настоящее время в столбце с меткой 2.
Перемещение его в следующий столбец не найдет никакого конфликта с каким-либо другим ферзем, так он может стать частью нового решения и его метка 3 помещается в стек. Таким образом, второе решение будет: