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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Задача о восьми ферзях.
Одно из решений: a7, b4, c2, d8, e6, f1, g3, h5:(87)

Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям. Обобщение задачи — расставить максимальное количество взаимно не бьющих друг друга ферзей на прямоугольном поле, в частности, квадратном поле, со стороной n.

Формулировка[править | править вики-текст]

В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».

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

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

Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N×N клеток (при этом при 1<N<4 задача не имеет решения).

Мы же подробнее рассмотрим классический “шахматный” случай для доски 8*8.

Особенности решения[править | править вики-текст]

Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4 426 165 368 (= 64!/(8!(64-8)!)). Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16 777 216 (то есть 88) вместо 4 426 165 368. Генерируя перестановки, которые являются решениями задачи о восьми ладьях и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40 320 (то есть 8!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.

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

Программа, реализующая этот алгоритм на QBasic.

В этой группе при повороте на 180 градусов позиции переходят сами в себя. Характерной особенностью симметрических положений является пустой квадрат 4×4 в середине доски и пустые диагонали. Таким образом, имея 12 расположений — по одному из каждой группы, можно получить все остальные, что, впрочем, известно из шахматной литературы[1]. В списке знаком «плюс» отмечены позиции, которые выбраны в качестве базовых (то есть тех, с которыми производятся преобразования симметрии) в английской и украинской версии данной статьи в Википедии и указаны номера, под которыми они в ней фигурируют. Здесь же базовые позиции (первые позиции в каждой группе) выбраны по признаку минимального номера в группе. Очевидно, что наборов базовых позиций можно составить 4×811.

Вариант решения для доски произвольного размера на C#[править | править вики-текст]

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

Время выполнения алгоритма[править | править вики-текст]

График зависимости времени от размера (экспоненциальный)

Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core2 Q6600 @ 2.4 ГГц):

Размер Решений Время (мс)
4 2 1
5 10 2
6 4 2
7 40 2
8 92 3
9 352 6
10 724 16
11 2 680 69
12 14 200 376
13 73 712 2 311
14 365 596 15 411
15 2 279 184 108 587
16 14 772 512 812 945

Характер зависимости времени выполнения от размера доски — экспоненциальный (как показано на графике).

Вариант решения для доски произвольного размера на C[править | править вики-текст]

Здесь приведена программа, решающая задачу для размеров доски от 1 до 17. Программа измеряет и выводит время работы алгоритма.

Время выполнения алгоритма[править | править вики-текст]

Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core i5-2410M @ 2.3 ГГц):

Размер Решений Время (с)
1 1 0.000 003
2 0 0.000 001
3 0 0.000 001
4 2 0.000 004
5 10 0.000 008
6 4 0.000 025
7 40 0.000 091
8 92 0.000 347
9 352 0.001 508
10 724 0.008 023
11 2 680 0.031 750
12 14 200 0.114 120
13 73 712 0.538 676
14 365 596 3.267 996
15 2 279 184 21.486 720
16 14 772 512 147.388 255
17 95 815 104 1 088.978 601
18 666 090 624 8 776.579 792

Вариант решения для доски размера до 10-11 на Oracle 11 SQL[править | править вики-текст]

В Oracle SQL возможно решение одним рекурсивным оператором. Время выполнения — секунды для доски 8*8, до 1 минуты для доски 9*9.

Использован усовершенствованный метод поиска с возвратом:

На доске есть четыре типа ресурсов: вертикали, горизонтали, левые и правые диагонали. Каждая поставленная фигура на доску «потребляет» одну горизонталь, одну вертикаль, и две диагонали. Соответственно, следующего ферзя мы будем пробовать ставить на ту клетку, для которого есть оставшиеся незанятые горизонталь, вертикаль и диагонали. Этим существенно сокращаем время перебора.

Рекурсивное решение для доски произвольного размера на C++[править | править вики-текст]

Альтернативный подход[править | править вики-текст]

Если решать более общую задачу об N ферзях при помощи описанного выше алгоритма, то такой перебор вариантов даже с использованием описанных выше сокращений будет весьма долго работать уже при N = 20, так как 20! = 2.433·1018. Поэтому представляет особенный интерес следующий эвристический алгоритм, решающий задачу об N ферзях на поле размером N x N. Он работает для всех N ≥ 4 или N = 1:

  1. Разделить N на 12 и запомнить остаток (N будет равно 8 для задачи о восьми ферзях).
  2. Занести в список все четные числа от 2 до N по порядку.
  3. Если остаток равен 3 или 9, перенести 2 в конец списка.
  4. Добавить в список все нечетные числа от 1 до N по порядку, но, если остаток равен 8, перевернуть пары соседних чисел (например: 3, 1, 7, 5, 11, 9, …).
  5. Если остаток равен 2 и N ≥ 3, поменять местами 1 и 3, затем, если N ≥ 5, перенести 5 в конец списка.
  6. Если остаток равен 3 или 9, переместить 1 и 3 (именно в этом порядке, а не в котором они сейчас) в конец списка.
  7. Разместить ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем поместить следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т. д.

Для N = 8 результат работы этого алгоритма показан на картинке.

a b c d e f g h
8
Chessboard480.svg
d8 white queen
g7 white queen
c6 white queen
h5 white queen
b4 white queen
e3 white queen
a2 white queen
f1 white queen
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Решение, полученное с помощью эвристики.(5)

Ещё несколько примеров:

  • 14 ферзей (остаток 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 ферзей (остаток 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 ферзей (остаток 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.

Реализация на C++[править | править вики-текст]

Реализация на Haskell[править | править вики-текст]

Реализация на Erlang[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Гик Е. Я. Шахматы и математика. — М.: Наука, 1983. — 176 с.

Ссылки[править | править вики-текст]