Задача про вісім ферзів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
g7 білий ферзь
c6 білий ферзь
h5 білий ферзь
b4 білий ферзь
e3 білий ферзь
a2 білий ферзь
f1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Один з розв'язків задачі про вісім ферзів.

Задача про вісім ферзів полягає в такому розміщенні восьми ферзів на шаховій дошці, що жодна з них не ставить під удар іншу. Тобто, вони повинні не стояти на одному стовпчику, рядку, або діагоналі. Задача про вісім ферзів є прикладом загальної задачі про n ферзів: задачі розміщення n ферзів на дошці розміром n × n, яка має розв'язки для n = 1 або n ≥ 4.

Задача має 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 ферзями. Нарешті, задачу можна звести до задачі з 0 ферзями, розв'язком якої є порожня дошка.

Наступна програма мовою 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 ферзів.

a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
g7 білий ферзь
c6 білий ферзь
h5 білий ферзь
b4 білий ферзь
e3 білий ферзь
a2 білий ферзь
f1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 1
a b c d e f g h
8
Chessboard480.svg
e8 білий ферзь
b7 білий ферзь
d6 білий ферзь
g5 білий ферзь
c4 білий ферзь
h3 білий ферзь
f2 білий ферзь
a1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 2
a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
b7 білий ферзь
g6 білий ферзь
c5 білий ферзь
f4 білий ферзь
h3 білий ферзь
e2 білий ферзь
a1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 3
a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
f7 білий ферзь
h6 білий ферзь
c5 білий ферзь
a4 білий ферзь
g3 білий ферзь
e2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 4
a b c d e f g h
8
Chessboard480.svg
c8 білий ферзь
f7 білий ферзь
h6 білий ферзь
a5 білий ферзь
d4 білий ферзь
g3 білий ферзь
e2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 5
a b c d e f g h
8
Chessboard480.svg
e8 білий ферзь
c7 білий ферзь
h6 білий ферзь
d5 білий ферзь
g4 білий ферзь
a3 білий ферзь
f2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 6
a b c d e f g h
8
Chessboard480.svg
e8 білий ферзь
g7 білий ферзь
d6 білий ферзь
a5 білий ферзь
c4 білий ферзь
h3 білий ферзь
f2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 7
a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
a7 білий ферзь
e6 білий ферзь
h5 білий ферзь
f4 білий ферзь
c3 білий ферзь
g2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 8
a b c d e f g h
8
Chessboard480.svg
c8 білий ферзь
f7 білий ферзь
d6 білий ферзь
a5 білий ферзь
h4 білий ферзь
e3 білий ферзь
g2 білий ферзь
b1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 9
a b c d e f g h
8
Chessboard480.svg
f8 білий ферзь
b7 білий ферзь
g6 білий ферзь
a5 білий ферзь
d4 білий ферзь
h3 білий ферзь
e2 білий ферзь
c1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 10
a b c d e f g h
8
Chessboard480.svg
d8 білий ферзь
g7 білий ферзь
a6 білий ферзь
h5 білий ферзь
e4 білий ферзь
b3 білий ферзь
f2 білий ферзь
c1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 11
a b c d e f g h
8
Chessboard480.svg
f8 білий ферзь
d7 білий ферзь
g6 білий ферзь
a5 білий ферзь
h4 білий ферзь
b3 білий ферзь
e2 білий ферзь
c1 білий ферзь
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Унікальний розв'язок № 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]:

\lim_{n \to \infty} \frac{\log{D(n)}}{n \log{n}}=\beta>0 .

Відомі результати дозволяють ще більше звузити оцінку для великих n до[7]: D(n)\approx n! \cdot c^n , де c\approx 0.39.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. O.-J. Dahl, Edsger W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3
  2. Karl Fabel: Das n-Damen-Problem. In: Die Schwalbe, Heft 1, Oktober 1969. S. 20
  3. Karl Fabel: Das n-Damen-Problem. In: Die Schwalbe, Heft 5, September 1970. S. 146
  4. Queens@TUD, TU Dresden, Deutschland
  5. MC#-Projekt
  6. I. Rivin, I. Vardi, P. Zimmermann: The n-Queens Problem. In: The American Mathematical Monthly. Band 101, 1994, S. 629—639
  7. Послідовність A000170 з Енциклопедії цілочисельних послідовностей

Література[ред.ред. код]

  • John J. Watkins: Across the Board: The Mathematics of Chess Problems. Princeton University Press, Princeton 2004, ISBN 0-691-11503-6.

Посилання[ред.ред. код]