5.7.2. Второй способ решения

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

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

Тогда (непосредственно вытекает из того, что 1 и 2 запрещены из-за

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

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

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

Теперь алгоритм проверки метода неявного перебора принимает описанный ниже вид.

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

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

векторе возможных значений они отмечаются номером соответствующего ферзя.

(см. скан)

Рис. 5.14. Размещение четырех ферзей (второй вариант).

Теперь для решения нашей задачи мы имеем способ, очень похожий на метод Люка прохождения лабиринта (рис. 5.14).

Выбор порядка расстановки ферзей

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

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

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