5.7. Неявный перебор с распространением ограничений

Решим методом Люка одну классическую задачу, условие которой существенно отличается от условия задачи о лабиринте: расположить на шахматной доске размером

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

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

5.7.1. Первый способ решения

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

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

Рис. 5.8. Задача о размещении ферзей на шахматной доске.

Рис. 5.9. Выбор поля для второго ферзя.

Рис. 5.10. Второй вариант выбора поля для второго ферзя в задаче о четырех ферзях.

Для второй горизонтали первым не приводящим сразу же в тупик вариантом является размещение второго ферзя в третьей вертикали (рис. 5.9). Выбрав эти два варианта, мы не можем поместить третьего ферзя на третьей горизонтали: на пересечении с вертикалями 1 и 3 из-за первого ферзя, а на пересечении с вертикалями 2 и 4 — из-за второго. Это частичное решение, при котором удается разместить лишь двух ферзей, не может составить часть полного решения, поскольку мы не сумеем найти место для ферзя на третьей горизонтали. Следовательно., мы должны пересмотреть вопрос о размещении второго ферзя. Поставим его на четвертую вертикаль (рис. 5.10).

Поскольку размещение третьего ферзя на пересечении -с первой вертикалью нарушает условия мы поставим его на вторую вертикаль. Размещение четвертого ферзя на вертикалях 1, 2, 3 или 4 вступает в противоречие с заданными условиями. Следовательно, нужно вернуться к последнему разветвлению, когда мы выбирали место для второго ферзя.

Рис. 5.11. Третий вариант размещения двух первых ферзей.

Рис. 5.12. Решение задачи о четырех ферзях.

Но при этом не осталось ни одной вертикали, на которой можно было бы его разместить. Следовательно, на самом деле нужно вернуться к вопросу о размещении первого ферзя. Поставим его на пересечении первой горизонтали со второй вертикалью. Размещение второго ферзя на пересечении с первой, второй третьей вертикалями невозможно; поэтому поставим его на четвертую вертикаль (рис. 5.11).

На третьей горизонтали условиям удовлетворяет первая клетка, а из-за невозможности расположить четвертого ферзй на 1 и 2 вертикалях место для него остается только на четвёртой вертикали (рис. 5.12).

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

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

Итак, обозначим каждое частичное решение, содержащее ферзей, которые расположены на А: первых горизонталях, через

вектор

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

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

Рис. 5.13. Дёрево поиска для случая неявного перебора.

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

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

произведением

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

Общий алгоритм неявного перебора:

(см. скан)

В задаче о восьми ферзях эта схема принимаёт вид, описанный ниже.

Восемь ферзей. Первый вариант

Шахматная доска является декартовым произведением из 8 строк меняется от I до 8). Поиск ведется по возрастающему от 1 до 8. В произвольный момент времени на Любой горизонтами обозначает текущий элемент т. е. первую вертикаль:

(см. скан)

Теперь мы улучшим этот алгоритм двумя способами.

Импликации, связанные с выбором места для ферзя

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

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