Простой и наглядный алгоритм перебора с возвратом реализуется в следующей хорошо известной задаче Гаусса о расстановке ферзей на шахматной доске. Нам удобно формулировать (и решать) эту задачу сразу для доски размером n´n (n=1, 2, …). Будем считать, что её строки и столбцы пронумерованы соответственно сверху вниз и слева направо цифрами от 0 до n-1 (см. рис.1 при n=8).
адача 1. Расстановки ферзей. Составить рекурсивную программу-функцию, находящую все возможные расстановки n ферзей на шахматной доске размером n´n так, чтобы они не били друг друга.
Решение. В соответствии с описанной ранее общей схемой 2 алгоритма перебора с возвратом предложенную задачу можно было бы решать по приведенному ниже алгоритму “Все расстановки”. По нему ферзи расставляются последовательно на вертикалях с номерами от нуля и далее. В процессе выполнения предписания возможны снятия ферзей с доски (возвраты).
Рис. 1. Схема использования вспомогательных массивов в задаче 1
Алгоритм “Все расстановки”
Полагаем D = Æ, j = 0 (D - множество решений, j - текущий столбец для очередного ферзя).
Пытаемся в столбце j продвинуть вниз по вертикали или новый (если столбец j пустой), или уже имеющийся там ферзь на ближайшую допустимую строку. Если это сделать не удалось, то переходим к пункту 4.
j ¬ j+1. Если j < n-1, то переходим к пункту 2. В противном случае j = n-1, то есть все вертикали уже заняты. Найденное частичное решение запоминаем в множестве D и переходим к пункту 2.
j ¬ j-1, то есть снимаем ферзь со столбца j и переходим к предыдущему столбцу. Если j ³ 0, то выполняем пункт 2. Иначе вычисления прекращаем. Решения задачи находятся в множестве D, которое, вообще говоря, может быть и пустым.
Никто и ничто не мешает нам при небольших n пытаться выполнить этот алгоритм “вручную”. Но чтобы идти дальше и пытаться переложить эти заботы на компьютер, необходимо остановиться на каком-либо представлении для данных.
Введем в рассмотрение четыре вспомогательных вектора: pos, ho, dd и du c длинами n, n, 2×n-1 и 2×n-1 соответственно. Использовать их будем следующим образом (см. рис.1):
hoi = 1, если на горизонтали с номером i (i = 0, 1, …, n-1) имеется ферзь, и hoi = 0 - в противном случае; | |
dus = 1, если на диагонали с номером s (s = 0, 1, …, 2×n-2), идущей слева направо и снизу вверх, имеется ферзь, и dus = 0 - в противном случае; | |
dds = 1, если на диагонали с номером s (s = 1, 2, …, 2×n-1), идущей слева направо и сверху вниз, имеется ферзь, и dds+1 = 0 - в противном случае; | |
posj = i , если в позиции (i, j) (i, j = 0, 1, …, n-1) стоит ферзь. |
Использование этих соглашений позволяет получить такие утверждения:
В позицию (i, j) можно поставить ферзь, если hoi + dui+j +j + ddn+i-j+i-j = 0. | |
Поставить ферзь в позицию (i, j) равносильно присваиваниям: hoi := 1, dui+j := 1, ddn+i-j := 1. | |
Убрать ферзь из позиции (i, j) равносильно присваиваниям: hoi := 0, dui+j := 0, ddn+i-j := 0. |
С учетом сказанного достаточно компактный рекурсивный вариант алгоритма решения задачи 1 можно было бы задать следующими двумя функциями:
Дадим краткое описание функций queen() и qu().
Головная функция queen(n) организует обращение к рекурсивной функции qu(), передавая ей в качестве фактических параметров:
n - размер доски; | |
ho, du, dd, pos - начальные значения вспомогательных векторов (с нулевыми компонентами); | |
j = 0 - начальное значение номера столбца текущей позиции (i, j) ферзя; | |
ot - вспомогательный вектор (с нулевыми компонентами), к которому последовательно будут присоединяться найденные решения. |
Возвращает функция queen() матрицу ot, столбцы которой, кроме нулевого, содержат решения задачи. Если (i0, i1, ..., in-1)T- один из таких столбцов, то решением являются позиции ферзей: (i0, 0), (i1, 1), ..., (in-1, n-1).
Функция qu() в рекурсивном варианте реализует алгоритм “Все расстановки”. Нелишне отметить, что рекурсия здесь осуществляется по не совсем стандартной схеме. В каждом рекурсивном вызове глубины j делается попытка поместить ферзь в некоторую позицию i столбца j (i, j = 0, 1, …, n-1), а сам вызов соответствует переходу от работы с текущим столбцом к работе со следующим столбцом. При этом в начале вычислений и при переходах к любому последующему рекурсивному вызову параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. Если в текущем столбце ферзь установить уже не удается, то создавшуюся ситуацию (позицию) назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему столбцу и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии мы должны считать совокупность всех тупиков. Заметим, что в данном случае элементы базы заранее до вычислений неизвестны.
После установки ферзя в одну из строк i последнего столбца j = n-1 формируется одно из решений задачи. Вычисления прекращаются, когда мы попадаем в тупик при работе со столбцом 0. Полученные решения задачи, если они есть, возвращаются в виде столбцов матрицы ot, начиная от первого и далее.
Попробуем теперь понять, как реализуется декомпозиция. Для этого вместо исходной задачи удобно решать её следующее обобщение.
Задача E(n, m, w). На доске размера n´m (m = n, n-1,…0) требуется установить m ферзей так, чтобы они не били друг друга. При этом имеются некоторые клетки доски, на которые ферзь заведомо ставить нельзя. Множество этих “запретных” клеток обозначим через w .
Исходная задача есть E(n, n, Æ). Проведем её декомпозицию. Представим доску в виде двух частей: нулевого столбца (A) и оставшейся части (B). Соответственно этому разбиению будем решать задачи E(n, 1, Æ) и E(n, n-1, w). Каждое из n возможных решений i (ферзь установлен в строке i = 0, 1, …, n-1) первой задачи однозначно определяет множество w = w(i) запретных клеток для второй задачи. При этом в w(i) попадают те клетки B, которые в “объединенной” доске бьет ферзь, установленный в строке i доски A. Пусть i зафиксировано и найдено множество d(i) решений второй задачи E(n, n-1, w(i)) для доски B. Тогда расположение ферзя в строке i доски A и любое из полученных решений xÎd(i) на B в совокупности дают различные решения ot(i) исходной задачи E(n, n, Æ). Для получения всех решений этой задачи остается лишь взять объединение по i множеств ot(i): ot = È ot(i).
Контрольные примеры:
1. b := queen(8), x := b<1>, y := b<11>,
xT = [0 4 7 5 2 6 1 3], yT = [1 6 4 7 0 3 5 2];
2. c := queen(3), cols(c) = 1, то есть решений нет!
Замечание. В функции qu() можно вообще отказаться от использования цикла, организовав рекурсию как по i, так и по j. В этом случае qu() и queen() могли бы выглядеть так:
Обратите внимание на то, как реализована в qu() рекурсия. Во-первых, её глубина равна n2 - при каждом рекурсивном вызове по j (j = 0, 1, …, n-1) происходит n рекурсивных вызовов по i (i = 0, 1, …, n-1). Поскольку при каждом рекурсивном вызове с фиксированными значениями i и j осуществляется попытка установить ферзь на поле (i, j), то и сами вызовы здесь удобно не нумеровать от 0 до n2-1, а обозначать упорядоченными парами индексов (i, j).
Другой вариант для функции qu() получится, если поменять местами порядок рекурсивных обращений по i и по j. В этом случае отпадает надобность в снятии меток (предпоследняя строка qu()). Функция queen() при этом останется прежней. Но решения будут возвращаться в порядке, обратном тому, который был раньше:
Впрочем, для возвращения решений по этому варианту qu() в прежнем порядке достаточно при проведении рекурсии по параметру i менять его не от 0 до n-1, а от n-1 до 0. При этом при обращениях к qu() на месте параметра i в программы необходимо внести такие изменения (в тексте они выделены):
адача 2. Количество расстановок. Составить рекурсивную программу-функцию, находящую количество возможных расстановок n ферзей на шахматной доске размером n´n так, чтобы они не били друг друга.
Решение. Предложенную задачу можно решать по приведенным в задаче 1 функциям, упростив их следующим образом. Вместо запоминания найденных решений будем подсчитывать в переменной ot их количество. В этом случае становится ненужным и вспомогательный вектор pos для формирования очередного решения. Эта модификация функций qu() и queen() приводит нас соответственно к функциям qun() и queennum():
Рекурсия в qun() организована точно так же, как и в функции qu().
Контрольные примеры.
Просчеты по программе queennum(n) при разных значениях n приводят к следующим результатам:
n |
1 |
2 |
3 |
4 |
8 |
9 |
10 |
11 |
12 |
13 |
Число расстановок |
1 |
0 |
0 |
2 |
92 |
352 |
724 |
2680 |
14200 |
73712 |
Для формулировки следующей задачи введем одно понятие. Среди всех расстановок n ферзей на доске n´n выделим отдельные непересекающиеся классы Hs (s = 0, 1, ..., q) расстановок так, что все элементы данного класса можно получить из любого его представителя какими-либо элементарными преобразованиями типа:
поворот доски в её плоскости вокруг центра на 900, 1800 и 2700; | |
преобразования симметрии относительно диагоналей; | |
преобразования симметрии относительно прямых, проходящих через центр доски по границам клеток. |
Взяв по одному представителю из каждого класса Hs (s = 0, 1, ..., q), получим некоторое множество, называемое основными расстановками.
адача 3. Основные расстановки. Составить рекурсивную программу-функцию, находящую какое-либо множество основных расстановок n ферзей на шахматной доске размера n´n.
Решение. Эта задача решается с помощью функций quaf(), qua() и sift() практически тем же самым способом, что и задача 1. Отличия здесь такие. Рекурсивная функция qua(), как и функция qu() задачи 1, последовательно формирует каждую из возможных расстановок ферзей на доске, но не все из них запоминаются в матрице ответа ot. Очередная, полученная в qua(), расстановка pos в функции sift() подвергается проверке - включать или не включать её в матрицу ot. Делается это следующим образом. Из вектора pos описанными выше элементарными преобразованиями формируются еще семь расстановок (некоторые из них могут оказаться совпадающими). Если ни одна из них не входит в текущую матрицу ответов ot, то ot дополняется новым решением pos и т.д. Следовательно, по завершении вычислений ot будет содержать некоторое множество основных расстановок.
Контрольный пример.
n := 8, M := quaf(n), co := cols(M)-1, M := sm(M, 0, n-1, 1, co);