Задача про вісім ферзів
Задача про вісім ферзів полягає в такому розміщенні восьми ферзів на шахівниці, що жодна з них не ставить під удар один одного. Тобто, вони не повинні стояти в одній вертикалі, горизонталі чи діагоналі. Задача про вісім ферзів є прикладом загальної задачі про n ферзів: задачі розміщення n ферзів на шахівниці розміром n × n, яка має розв'язки для n = 1 або n ≥ 4.
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Задача має 92 розв'язки. Якщо відкинути схожі композиції з точністю до відбиття (віддзеркалення позиції на шахівниці) та обертання (обертання позиції на шахівниці), залишиться 12 унікальних розв'язків.
Історія
Задачу показав у 1848 р. шахіст Макс Бецель (нім. Max Friedrich William Bezzel), і вже через три роки математики, зокрема, Карл Гаус, працювали над пошуком її розв'язків та узагальненого варіанту. Перші розв'язки були знайдені Францом Науком (Franz Nauck) 1850 р. Також Наук запропонував розширити задачу до n ферзів (на шахівниці розміром n × n). 1874 р. Ґюнтер (S. Günther) запропонував метод пошуку розв'язків із використанням визначників, а Джеймс Глейшер (англ. James Whitbread Lee Glaisher) його вдосконалив.
Едсгер Дейкстра використав цю задачу 1972 р. аби показати можливості того, що він назвав структурним програмуванням. Він надрукував докладне описання розробки алгоритму пошуку в глибину з поверненням[1].
Алгоритми пошуку розв'язків
Рекурсивний алгоритм з поверненням
Задача про ферзів є прикладом простої, але не тривіальної задачі, яку можна розв'язати із допомогою рекурсивного алгоритму, оскільки задача з n ферзями може бути представлена як задача розміщення ферзя для розв'язку з n − 1 ферзями. Нарешті, задачу можна звести до задачі з 8 ферзями, розв'язком якої є порожня шахівниця.
Наступна програма мовою Python знаходить всі розв'язки для задачі з n ферзями використовуючи рекурсивний алгоритм. Він рекурсивно досліджує шахівниці розміром n × n, n × n − 1, n × n − 2, …
В програмі враховано те, що ферзі не можуть стояти на одному рядку.
Також враховано те, що розв'язок з n − 1 ферзями на шахівниці n × n − 1 містить в собі розв'язок задачі з n − 2 ферзями на шахівниці розміром n × n − 2.
Тобто, алгоритм також отримує всі розв'язки, які входять до знайденого розв'язку на менших шахівницях.
Для шахівниці 8×8 програма переглядає 15 720 позицій.
def queenproblem(rows, cols):
if rows <= 0:
return [[]] # порожня дошка є розв'язком для випадку без ферзів
else:
return add_queen(rows - 1, cols, queenproblem(rows - 1, cols))
# Переглянути всі комбінації для часткового розв'язку,
# для яких можна додати ферзя в «new_row».
# Якщо відсутні конфлікти з частковим розв'язком,
# тоді знайдено новий розв'язок для додаткового рядка.
def add_queen(new_row, cols, known_solutions):
new_solutions = []
for solution in known_solutions:
# спробувати розмістити ферзя в кожну комірку додаткового рядка
for new_column in range(cols):
# print('Спроба: %s в рядку %s' % (new_column, new_row))
if no_conflict(new_row, new_column, solution):
# відсутні конфлікти, цей варіант є розв'язком
new_solutions.append(solution + [new_column])
return new_solutions
# Перевіряє, чи можна поставити ферзя в комірку «new_column»/«new_row» так,
# аби не ставити під удар вже розміщенні ферзі
def no_conflict(new_row, new_column, solution):
# Переконатись, що новий ферзь не знаходиться на одній колонці або діагоналі
for row in range(new_row):
if solution[row] == new_column or # Збігаються колонки
solution[row] + row == new_column + new_row or # Збігається діагональ
solution[row] - row == new_column - new_row: # Збігається діагональ
return False
return True
Цей рекурсивний алгоритм можна перетворити на ітеративний алгоритм без рекурсії.
Реалізація задачі про вісім ферзів на мові програмування С++
#include "stdafx.h"
#include <iostream>
using namespace std;
int main(){
int q[8],c,i;
int count = 1;
q[0] = 0;
c = 0;
NC:
c++;
if(c == 8) goto print;
q[c] = -1;
NR:
q[c]++;
if(q[c] == 8) goto back;
for (i = 0; i < c; i++) {
if((q[i] == q[c]) || ((c - i) == abs(q[c] - q[i]))) goto NR;}
goto NC;
back:
c--;
if (c == -1) return 0;
goto NR;
print:
cout << endl;
cout << "#" << count << endl;
for(i = 0;i < 8; i++){
cout << q[i] << " ";
}
cout << endl;
count++;
goto back;
system("pause");
return 0;
}
Програмування в обмеженнях
Засобами програмування в обмеженнях в обмеженій області визначення можна сформулювати задачу про ферзів компактніше.
Наступна програма мовою Пролог (діалект GNU Prolog) швидко знаходить розв'язок і для задач на більших шахівницях.
/* Цей предикат створює список, який відповідає розв'язку задачі.
Список містить числа від 1 до N без повторів. */
n_queens(N,Ls) :- length(Ls,N),
fd_domain(Ls,1,N),
fd_all_different(Ls),
constraint_queens(Ls),
fd_labeling(Ls,[variable_method(random)]).
/* Цей предикат вірний, якщо розміщення ферзів
задовольняє умовам задачі */
constraint_queens([]).
constraint_queens([X|Xs]) :- not_beats(X,Xs,1), constraint_queens(Xs).
/* Цей предикат вірний, якщо дві дами не стоять на одній
діагоналі */
not_beats(_,[],_).
not_beats(X,[Y|Xs],N) :- X#\=Y+N, X#\=Y-N, T#=N+1, not_beats(X,Xs,T).
Розв'язки
Класична задача
Всього задача про вісім ферзів має 92 розв'язки, але відкинувши розв'язки, які можна отримати відбиттям (віддзеркаленням позиції) та обертанням (обертанням позиції на шахівниці) лишиться 12 унікальних розв'язків. Оскільки кожен унікальний розв'язок має чотири відбиття (через діагональ, горизонталь, вертикаль, та середину шахівниці), та чотири повороти, можна отримати 8·12 = 96 розв'язки. Оскільки один з розв'язків (діаграма № 12), залишається незмінним при повороті на 180°, з нього можна отримати лише чотири розв'язки. Завдяки йому, загальна кількість розв'язків класичної задачі дорівнює 92.
Нижче наведено унікальні розв'язки задачі для 8 ферзів.
Унікальний розв'язок № 1
|
Унікальний розв'язок № 2
|
Унікальний розв'язок № 3
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Унікальний розв'язок № 4
|
Унікальний розв'язок № 5
|
Унікальний розв'язок № 6
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Унікальний розв'язок № 7
|
Унікальний розв'язок № 8
|
Унікальний розв'язок № 9
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Унікальний розв'язок № 10
|
Унікальний розв'язок № 11
|
Унікальний розв'язок № 12
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Узагальнена задача
Узагальнена задача про ферзів полягає в розміщенні n ферзів на шахівниці розміром n × n.
Кількість розв'язків на шахівницях до 26 × 26
В наступній таблиці наведено кількість унікальних розв'язків та загальну кількість розв'язків для задач про ферзі на шахівницях розміром до 26 × 26.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| унікальних | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1 787 | 9233 | 45 752 | 285 053 | 1 846 955 | 11 977 939 | 83 263 591 |
| взагалі | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14 200 | 73 712 | 365 596 | 2 279 184 | 14 772 512 | 95 815 104 | 666 090 624 |
| n | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|
| унікальних | 621 012 754 | 4 878 666 808 | 39 333 324 973 | 336 376 244 042 | 3 029 242 658 210 | 28 439 272 956 934 |
| взагалі | 4 968 057 848 | 39 029 188 884 | 314 666 222 712 | 2 691 008 701 644 | 24 233 937 684 440 | 227 514 171 973 736 |
| n | 25 (світовий рекорд 2005 р.) | 26 (світовий рекорд 2009 р.) |
|---|---|---|
| унікальних | 275 986 683 743 434 | 2 789 712 466 510 289 |
| взагалі | 2 207 893 435 808 352 | 22 317 699 616 364 044 |
На той час відома, але не перевірена кількість розв'язків для n = 12, була підтверджена 1969 р. незалежно Торбьорном Ліндельофом (нім. Torbjörn Lindelöf) та Берндом Шварцкопфом (нім. Bernd Schwarzkopf) на комп'ютері. Ліндельофу також вдалось обчислити кількість розв'язків для n = 13 та n = 14[2]. 1970 р. Ліндельофу вдалось обчислити кількість розв'язків для n = 15[3].
Кількість розв'язків для n = 26 була обчислена 11 липня 2009 р. проектом Queens@TUD[4] із використанням FPGA-процесорів, а 30 серпня 2009 р. була підтверджена проектом MC#[5]на двох російських суперкомп'ютерах зі списку TOP500.
Взагалі, можна стверджувати, що кількість розв'язків зростає дещо швидше за експоненційну. Слід відмітити, що кількість розв'язків для шахівниць 2 × 2 та 6 × 6 менша, аніж на шахівницях меншого від них розміру.
Кількість розв'язків для довільних n
Верхня границя кількості розв'язків D(n) задачі розміру n дорівнює n!, що дорівнює кількості розв'язків для n тур. Кількість ферзів, які не ставлять під удар одна одну, набагато менша за це число.
Асимптотична форма для D(n) не відома. Рівін та інші припускають, що[6]:
- .
Відомі результати дозволяють ще більше звузити оцінку для великих n до[7]: , де .
Див. також
Примітки
- O.-J. Dahl, Edsger W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3
- Karl Fabel: Das n-Damen-Problem. In: Die Schwalbe, Heft 1, Oktober 1969. S. 20
- Karl Fabel: Das n-Damen-Problem. In: Die Schwalbe, Heft 5, September 1970. S. 146
- Queens@TUD, TU Dresden, Deutschland. Архів оригіналу за 10 листопада 2017. Процитовано 13 квітня 2019.
- MC#-Projekt. Архів оригіналу за 1 березня 2012. Процитовано 3 січня 2011.
- I. Rivin, I. Vardi, P. Zimmermann: The n-Queens Problem. In: The American Mathematical Monthly. Band 101, 1994, S. 629—639
- послідовність A000170 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
Література
- John J. Watkins: Across the Board: The Mathematics of Chess Problems. Princeton University Press, Princeton 2004, ISBN 0-691-11503-6.