Ферзи на шахматной доске
Back Home Up Next

Простой и наглядный алгоритм перебора с возвратом реализуется в следующей хорошо известной задаче Гаусса о расстановке ферзей на шахматной доске. Нам удобно формулировать (и решать) эту задачу сразу для доски размером n´n (n=1, 2, …). Будем считать, что её строки и столбцы пронумерованы соответственно сверху вниз и слева направо цифрами от 0 до n-1 (см. рис.1 при n=8).

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

Решение. В соответствии с описанной ранее общей схемой 2 алгоритма перебора с возвратом предложенную задачу можно было бы решать по приведенному ниже алгоритму “Все расстановки”. По нему ферзи расставляются последовательно на вертикалях с номерами от нуля и далее. В процессе выполнения предписания возможны снятия ферзей с доски (возвраты).

Рис. 1. Схема использования вспомогательных массивов в задаче 1

Алгоритм “Все расстановки”

  1. Полагаем D = Æ, j = 0 (D - множество решений, j - текущий столбец для очередного ферзя).

  2. Пытаемся в столбце j продвинуть вниз по вертикали или новый (если столбец j пустой), или уже имеющийся там ферзь на ближайшую допустимую строку. Если это сделать не удалось, то переходим к пункту 4.

  3. j ¬ j+1. Если j < n-1, то переходим к пункту 2. В противном случае j = n-1, то есть все вертикали уже заняты. Найденное частичное решение запоминаем в множестве D и переходим к пункту 2.

  4. 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);

Home Содержание Схемы ООД Доска объявлений Поиск