На этом шаге мы приведем некоторые рассуждения по поводу решения этой задачи.
Задача n ферзей была представлена ранее на 185 шаге. Напомним, что это задача удовлетворения ограничений (constraint satisfaction) или соблюдения заданных условий, решение которой сводится к перестановкам строк, в которых расположены ферзи. Поэтому для решения данной задачи методом перебора с возвратами можно использовать в качестве отправной точки код из примера 12.4, генерирующий перестановки. Хотя конечный алгоритм потребует некоторых модификаций, его структура будет очень похожа на метод генерации перестановок.
Рассмотрим метод generate_permutations_alt() и его входные параметры. Он переставляет элементы списка, которые могут содержать произвольные числа, символы или другие типы данных. В данном случае перестановке подлежат горизонтали (строки) шахматной доски. Поскольку их номера - это просто целые числа от 0 до n - 1, можно написать код без применения списка. Но мы всё же будем использовать для частичного решения список sol номеров строк размера n, параметр i для номера столбца, в котором размещается очередной ферзь, а также логический список размера n available, в котором помечены свободные строки - кандидаты для включения в частичные решения.
Мы поменяем имя этого списка на free_rows, так как даже в отсутствие ферзя в строке она может быть недоступной для включения в частичное решение из-за дополнительного ограничения, связанного с диагональю.
В дополнение к этим параметрам мы будем использовать ещё два логических списка для указания присутствия ферзя на диагоналях шахматной доски. Есть два вида диагоналей:
- a) основные, параллельные главной диагонали от верхнего левого угла до нижнего правого угла шахматной доски, и
- b) побочные, перпендикулярные основным.
Их ровно 2n - 1 каждого вида, как показано на рисунке 1 для n = 4.
Рис.1. Индексированные основные и побочные диагонали матрицы или шахматной доски
Таким образом, мы будем использовать логические списки free_pdiags и free_sdiags - оба длиной 2n - 1, которые будут содержать True, если нет ферзей на основных и побочных диагоналях соответственно. На рисунке также показан способ нумерации диагоналей, где пара чисел внутри клетки задаёт номера её строки и столбца на доске. Заметим, что, с одной стороны, сумма номера столбца и номера строки клетки в каждой побочной диагонали постоянна. Она меняется в диапазоне от 0 до 2n - 2 и может служить индексом в free_sdiags. С другой стороны, для каждой основной диагонали разность номера строки и номера столбца постоянна и меняется в диапазоне от -(n - 1) до n - 1. Поскольку индексы должны быть неотрицательными, можно просто увеличить эту разность на n - 1 и получить правильный индекс для основной диагонали, который после этого будет находиться в диапазоне от 0 до 2n - 2. Эти простые операции позволят нам по номеру строки и столбца быстро определить диагональ, на которой расположена клетка.
На следующем шаге мы рассмотрим поиск всех решений.
