5.7.3. Третий способ решения

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

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

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

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

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

(см. скан)

(см. скан)

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

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

на пересечении вертикали и горизонтали III: На рис. 5.15 а представлена шахматная доска, на которой отмечены соответствующие запреты и импликации. Значения степеней свободы для оставшихся горизонталей соответственно равны 4, 3, затем 3, 4, 5 и, наконец, 4. Для вертикалей степени свободы равны: . Таким образом, одним из трех рядов, обладающих наименьшей степенью свободы, является горизонталь V; место для третьего ферзя мы будем искать именно на ней. Если мы решим поместить третьего ферзя в вертикали а (в первой свободной клетке данной горизонтали), наша шахматная доска примет вид, представленный на рис. 5.156.

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

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

ферзя является вынужденным. Так как при этом блокируется одна из двух свободных клеток в вертикали размещение пятого ферзя в клетке (VIII, е) также неизбежно.

Рис. 5.156. Задача о восьми ферзях (продолжение).

Рис. 5.16. Полное решение. Цифры в кружках обозначают местоположение ферзя; цифры в квадратиках — вынуж денное местоположение ферзя.

Клетка, (II, Ь) уже была обязательной, а клетка (VII, h) становится таковой. Эти два вынужденных значения неизбежно приводят

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

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

Рис. 5.17. Невозможность продолжения поиска после выбора местоположения третьего ферзя.

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

Вернувшись вначале к выбору местоположения третьего ферзя, мы запретим занимать клетку (V, а), отметив ее цифрой 2, поскольку теперь эта клетка связана с выбранным вариантом размещения второго ферзя. Поместим ферзя в следующую свободную клетку (V, е). Отметив запреты, мы увидим, что на этой стадии клетка (II, d) является обязательной, а в восьмой горизонтали при таких условиях нам не подойдет ни одна клетка. Эта ситуация показана на рис. 5.17.

Вернемся еще раз назад. Последний вариант размещения третьего ферзя при фиксированном положении ферзей 1 и 2 — йлетка (V, g). В этом случае мы получаем несколько горизонталей со степенью свободы, равной 2. Если поместить ферзя 4 на горизонтали II в клетке (II, Ь), то размещение ферзя 5 в

Рис. 5.18. Завершение поиска после выбора местоположения для двух ферзей.

клетке (VII, а) является вынужденным, но эти два варианта закрывают все возможности в последней вертикали. Выбор другой свободной клетки на горизонтали влечет за собой такие размещения и но тогда все остальные клетки уже оказываются под запретом, и мы не можем получить решения (рис. 5.18). Итак, мы доказали, что после осуществления двух первых выборов (VI, с) и (III, существует единственное решение, и оно соответствует частичному решению Данная конфигурация была выбрана произвольно. Исходя из этого, мы можем оценить усилия, необходимые для построения всех решений. Как только мы фиксируем положение первого ферзя, для второго — если он стоит на соседней горизонтали — остается пять возможностей (кооме случаев, когда первый стоит в одной из крайних клеток: тогда для второго существует шесть вариантов размещения). Учитывая симметрию шахматной доски (а следовательно, и симметричность решений по отношению к вертикальной оси симметрии), мы можем рассматривать только те четыре случая, когда первый ферзь стоит слева от данной оси. Так что в конечном счете нам придется вести поиск, примерно эквивалентный тому, который мы провели для конфигурации (IV, с), (III, f); число вариантов равно Следует отметить, что это число невелико. Итак, при удачных критериях выбора и эффективном управлении импликациями и возвратами для вывода о пригодности данной конфигурации

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

Для размещения третьего ферзя имеются в среднем только три возможности; следовательно, общее число ситуаций будет составлять (почти каждая из них дает вариант решения), в то время как вначале речь шла о числе перестановок. Мы перешли от случаев к 63, т. е. выиграли в 640 раз. Если мы захотим сохранить только основные решения, тогда в конце нужно рассортировать полученное множество и отбросить все решения, которые могут быть сведены к некоторым другим за счет горизонтальной симметрии или вращения. Тогда, наконец, останется двенадцать решений, среди которых полностью симметричным является только первое.

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

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