Реализация задачи

Попробуем обобщить стратегию отката, которую я только что представил.

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

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

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

В противном случае, идет переход к следующему столбцу справа.

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

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

Откат может быть достигнут путем опустошения стека.

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

После отката, вместо того чтобы начинать с самого левого столбца, перемещать ферзя справа налево от столбца, как записано в стеке.

Вот часть Java программы, реализующей решение проблемы n-ферзей.

Программа начинается с импорта класса стека из пакета java.util.

Здесь устанавливается стек класса-оболочки целых чисел с именем S.

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

n это число ферзей, размещенных на NхN доске.

total это общее количество решений, которое установлено изначально в 0.

Часть программы для решения задачи – это метод solve, который берет n, число ферзей, в качестве параметра.

row и col это индексы строки и столбца шахматной доски, и индексы начинаются с 0, а не с 1.

Часть метода, которая выполняет большую часть работы, это два while цикла, один для индексов строк и другой для индексов столбцов.

Я буду использовать пример, чтобы проиллюстрировать, как это работает.

Два while цикла здесь дублируются, индексы строк и столбцов инициализируются 0.

Размещение 1-го ферзя находится в 0,0, что явно не вызывает конфликт, так как он является единственным ферзем и метод isConflict является логическим методом, который вернет false, если нет конфликтов ни с какими другими ферзями, которые были помещены на доску до сих пор.

Я вернусь к его реализации позже.

Когда тело if выражения выполняется, метод push вызывается для стека s, а текущая метка столбца 0 вносится в пустой стек.

Далее происходит выход из внутреннего while цикла.

Строка будет увеличена на 1 и получает значение 1, а столбец сбрасывается в 0.

То есть, делается попытка поместить второго ферзя на позицию 1,0.

В этом случае, isConflict возвращает true, потому что он находится в том же столбце, что и первый ферзь.

Часть else if выражения будет выполнена, что увеличит столбец на 1.

(1,1) позиция далее проверяется методом isСonflict, который снова возвращает true, потому что это в той же диагонали, что и первый ферзь.

Часть else выполняется снова.

Позиция (1,2) теперь проверяется методом isСonflict, который возвращает false, т.е. тут нет конфликта.

Таким образом, текущее значение сol или 2 вносится на вершину стека.

Далее происходит выход из внутреннего while цикла, после того как 2 вносится в стек.

Строка увеличивается на 1 и получает значение 2, в то время как столбец сбрасывается в 0.

Позиции (2,0), (2,1), (2,2) и (2,3) будут проверяться последовательно для конфликта и для всех из них возвратится true, до тех пор, пока позиция (2,4) не будет достигнута и isСonflict не возвратит false.

Таким образом, значение 4 будет внесено в стек.

Этот процесс будет продолжаться до тех пор, пока определенные условия не будут выполнены.

Эти условия проверяются в следующей части программы.

Первое условие, которое может привести к прекращению программы, это когда стек пуст.

Это может быть проверено с помощью метода empty класса стека.

Пустой стек означает либо нет решения, или все решения были найдены в задаче n-ферзей на данном n.

2-й условие, которое мы должны проверить, перемещается ли ферзь за пределы доски или, что тоже самое, если индекс столбца больше или равен n.

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

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

Когда столбец снова вырос на 1, ферзь будет перемещен за пределы доски.

То есть, мы закончили исследовать все возможные размещения ферзя в текущей строке и условие col >=n становится истиной.

Когда тело if выражения выполняется, строка будет сокращена на 1, то есть, мы вернемся к предыдущей строке.

Стек извлекается таким образом, что мы можем определить текущее размещение ферзя в строке, в этом случае, со столбцом 1.

Чтобы проверить следующую позицию столбца, 1 добавляется к этой метке столбца, то есть столбец получит новое значение 2.

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

Таким образом, ферзь перемещается за пределы доски или столбец больше или равен n.

Стек освобождается таким образом, что будет рассмотрена предыдущая строка, или 3-я строка.

Чтобы добавить 1 к метке 4 столбца, мы снова будем двигать ферзя за пределы доски.

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

Единица добавляется к нему так, что рассматривается следующий столбец, и никакого конфликта не будет найдено, так что метка столбца 3 вносится в стек.

Последняя часть метода solve будет проверять условие, когда будет найдено решение.

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

Если это правда, это означает, что все n ферзей были размещены на шахматной доске, и не конфликтуют друг с другом.

Когда решение найдено, total, представляющее общее число решений, будет увеличена на 1.

Метод System.out.println может быть использован для вывода результатов, сохраненных в стеке, указав S в качестве параметра.

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

Обратите внимание, что строка должна быть уменьшена на 1, потому что строка увеличивается на 1 каждый раз, когда внутренний while цикл заканчивается, то есть строке будет дано значение, равное n, когда решение найдено.

Важной частью программы, которая по-прежнему отсутствует, является реализация логического метода isСonflict для определения находится ли размещение нового ферзя в конфликте с предыдущими размещениями ферзей.

Вот реализация этого метода.

Давайте, используем пример, чтобы объяснить, как это работает.

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

Если предположить, что ферзь находится в строке 1 и столбце 2, легко определить, есть ли конфликт вдоль одной и той же строки или в одном столбце, так как мы можем просто проверить индекс строки или индекс столбца, но как насчет конфликта по диагоналям.

Вы можете сначала понаблюдать, какое свойство является общим для всех точек по диагонали.

Что вы найдете общего, когда вы посмотрите на индексы этих точек.

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

Является ли это просто совпадением?

Давайте посмотрим на другую диагональ в том же направлении.

Вы увидите, что их различия все приведены в значение 0.

Давайте посмотрим на еще одну диагональ.

В этом случае, различия дают 1 в качестве значения.

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

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

Но что интересно, их суммы все дают одно и то же значение, в данном случае 3.

Давайте рассмотрим еще пару диагоналей в том же направлении, суммы для одной дают значение 4, и для другой дают значение 5.

Так что в целом, точки на одной и той же диагонали либо дают одинаковые суммы индексов или одинаковые разницы индексов.

В реализации метода isСonflict, суммы и разницы показателей вычисляются и проверяются на равенство в дополнение к индексу столбца.

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

Отметим также, что метод get наследуется от класса вектора, который является суперклассом класса Stack.

Можно установить другой массив, чтобы отслеживать промежуточные шаги, если не хотите использовать метод get.

Вот другие решения для этой проблемы 5-ферзей.

Существует в общей сложности 10 решений.

Откроем IDEA, чтобы посмотреть на фактическое выполнение программы.