Демонстрация задачи

Давайте посмотрим на выполнение задачи n-ферзей.

Это программа, которую мы обсуждали в лекции.

Как вы можете видеть, здесь есть два while цикла.

Один для управления строками, другой для управления столбцами.

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

И здесь есть условие проверки, является ли стек пустым.

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

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

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

Мы опустошим стек, чтобы определить следующий шаг для поиска следующего решения.

Давайте cкомпилируем и запустим программу, создавая экземпляр класса.

Метод demo запросит n, и введем n равным 5, и вы можете увидеть, что было найдено 10 решений.

Хотя трудно сказать, являются ли эти решения правильными.

Давайте попробуем найти решения для другого n.

Скажем, n, равным 8.

И у нас есть 92 решений.

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

Прежде, чем мы снова запустим программу, давайте уберем выражение вывода.

И снова скомпилируем, и запустим эту программу;

Давайте опять попробуем использовать большой n.

Скажем 13.

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

У вас есть здесь более 73 000 решений для проблемы 13-ферзей.

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

Поэтому у нас здесь есть графическая версия программы NQueens.

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

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

Мы проверяем, является ли стек пустым.

Вышел ли ферзь за пределы шахматной доске.

И было ли найдено решение.

И метод isConflict такой же, как и раньше.

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

Давайте генерировать экземпляр с использованием n, равным 5.

Это означает, что мы будем решать задачу 5-ферзей.

Здесь отображается шахматная доска.

Давайте посмотрим выполнение программы шаг за шагом.

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

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

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

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

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

Представление будет изменено на черного ферзя, что означает, что это не противоречит какому-либо другому ферзю.

Если мы будем продолжать выполнение, "i" будет увеличен на 1 или вторую строку.

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

Таким образом, if выражение не выполняется.

Вместо этого, метка столбца будет увеличиваться на 1.

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

И мы сможем продолжить процесс.

И этот процесс будет продолжаться, пока не будут найдены все решения.

Пример

Давайте посмотрим еще один пример, чтобы проиллюстрировать использование стека.

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

Если вы до сих пор помните, задача квадратных яблок в том, чтобы определить, может ли червь съесть все яблоки, которые размещаются в сетке NхN, следуя определенным правилам.

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

Легко увидеть, что для конфигурации сетки 3x3, решения существуют, когда червь начинает свое движение из средней ячейки.

Мы видели демонстрационную программу для иллюстрации процесса поиска решения.

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

Посмотрим сначала выполнение программы на паре примеров.

Это то, что вы найдете, если червь начнет с середины.

Как и ожидалось, были найдены 8 возможных решений.

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

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

Вот реализация неграфической версии программы.

Вы можете видеть, что структура программы очень похожа на программу n-ферзей.

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

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

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

В случае сетки 3x3, существует максимум 27 или 3*3 перемещения, и 2-й цикл для 4 возможных ходов, вправо, влево, вверх и вниз для каждого положения, и эти четыре движения соответствуют 4 случаям в switch выражении.

Методы move здесь определяют положение после каждого хода.

Логический метод isLegalMove аналогичен методу isConflict в программе n-ферзей.

Каждое правильное перемещение вносится в стек.

Три условия здесь также похожи на те, в задаче n-ферзей.

Вот условие для проверки пустого стека.

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

Когда есть maxStep элементов в стеке, решение найдено.

Последний шаг вынимается из стека в целях поиска нового решения.

Давайте скомпилируем и запустим программу для 3х3 и начнем с середины.

Как и ожидалось, есть 8 решений.

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

Вы обнаружите, что сложность проблемы растет очень быстро.

При n = 5, если мы начнем с угла, существует более 700 решений.

Вы найдете, что для n = 7, это займет более двух часов, чтобы найти более 1,5 млн решений для запуска в позициях, где существуют решения.

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

Вы найдете, что сложность программы составляет порядка 2 в степени n в квадрате, и для n, равного 7, это 2 в степени 49.

Так что сложность задачи здесь аналогична сложности задачи башня Ханоя.

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

В этом примере, не существует решения, если червь начинает с зеленого яблока, потому что есть только 4 зеленых яблок, в то время как есть 5 яблок красного цвета.

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

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

И поиск будет выполняться только тогда, когда решение существует.

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

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

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