Шахматная задача о восьми ферзях: Разбираемся, что же там нового открыли в задаче о ферзях / Хабр

задача о 8 ферзях | C++ для приматов

#include <iostream>

#include <stdio.h>

#include<fstream>

using namespace std;

 

const int n = 8;// Размер поля

int count_test = 0;// Количество тестов

int mincountstep = n + 1; //Количество ходов

int frtest[n]; //расстановка теста

int fr[n]; //правильная расстановка

 

bool check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 )  return false; //На всякий случай, чтобы не проверять поля где нет ферзей

    for (int i = 0; i < n && fr[i] >= 0; i++) {          

        if ( i == nf ) continue;

        if (fr[nf] == fr[i]  ) return false;  // (Горизонталь)

        if ( (nf + fr[nf]) ==  (i + fr[i]) ) return false; // Нисходящая диагональ

        if ( (nf — fr[nf]) ==  (i — fr[i]) ) return false; // Восходящая диагональ

    }  

    return true; //если поле свободно

}

 

void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

   int countstep = 0; // количество ходов

   for (int i = 0; i < n; i++){

      if ( frtest[i] != fr[i] ) countstep++;

   }

   if ( mincountstep > countstep ) mincountstep = countstep;

 

}

 

bool line_up(int i)

//рекурсивня функция установки ферзей (стек расстановок)

{

    if ( i > n-1) return false ;

    for (int j = 0; j < n; j++) {

        fr[i] = j;

        if ( check(i) == true ) {              

            if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

            calc_min_strok();

            } else {

                line_up(i+1);

            }

        }

        fr[i] = -1 ;  

    }

  return false ;

}

 

int main()

{

cin >> count_test;

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

   mincountstep = n + 1;

       for (int i = 0; i < n; i++) fr[i] = -1;

       //ввод данных теста

   for (int i = 0; i < n; i++) {    

         cin >> frtest[i];  

    frtest[i]—;    

   }

       line_up(0);    

       cout << mincountstep;

}  

    

    return 0;

}

Задача о восьми ферзях — это… Что такое Задача о восьми ферзях?

Задача о восьми ферзях.
Одно из решений: a7, b4, c2, d8, e6, f1, g3, h5:(87)

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

Формулировка

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

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

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

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

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

Особенности решения

Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4426165368. Общее число возможных расположений, удовлетворяющих условию задачи равно 92. В принципе, современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16777216 (то есть ) вместо 4426165368. Генерируя перестановки, которые являются решениями задачи о восьми ладьях и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40320 (то есть 8!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.

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

Ниже приведена программа, реализующая этот алгоритм на QBasic-е.

 CLS
 DEFINT A-I
 OPEN "ferz" FOR OUTPUT AS #1
 FOR a = 1 TO 8
 FOR b = 1 TO 8
  IF b = a THEN 8
  IF ABS(b - a) = 1 THEN 8
   FOR c = 1 TO 8
 IF c = a OR c = b THEN 7
 IF ABS(c - b) = 1 OR ABS(c - a) = 2 THEN 7
 FOR d = 1 TO 8
 IF d = a OR d = b OR d = c THEN 6
 IF ABS(d - c) = 1 OR ABS(d - b) = 2 OR ABS(d - a) = 3 THEN 6
 FOR e = 1 TO 8
 IF e = a OR e = b OR e = c OR e = d THEN 5
  IF ABS(e - d) = 1 OR ABS(e - c) = 2 OR ABS(e - b) = 3 OR ABS(e - a) = 4 THEN 5
 FOR f = 1 TO 8
 IF f = a OR f = b OR f = c OR f = d OR f = e THEN 4
   IF ABS(f - e) = 1 OR ABS(f - d) = 2 OR ABS(f - c) = 3 OR ABS(f - b) = 4 >
 OR ABS(f - a) = 5 THEN 4
 FOR g = 1 TO 8
 IF g = a OR g = b OR g = c OR g = d OR g = e OR g = f THEN 3
  IF ABS(g - f) = 1 OR ABS(g - e) = 2 OR ABS(g - d) = 3 OR ABS(g - c) = 4  >
 OR ABS(g - b) = 5 OR ABS(g - a) = 6 THEN 3
 FOR h = 1 TO 8
 IF h = a OR h = b OR h = c OR h = d OR h = e OR h = f OR h = g THEN 2
 IF ABS(h-g) = 1 OR ABS(h-f) = 2 OR ABS(h-e) = 3 OR ABS(h-d) = 4 OR ABS(h-c) = 5     >
 OR ABS(h-b) = 6 OR ABS(h-a) = 7 THEN 2
 i = i + 1 
 PRINT i; " "; "a"; a; " "; "b"; b; " "; "c"; c; " "; "d"; d;
 PRINT " "; "e"; e; " "; "f"; f; " "; "g"; g; " "; "h"; h
 PRINT #1, i; " "; "a"; a; " "; "b"; b; " "; "c"; c; " "; "d";
 PRINT #1, d; " "; "e"; e; " "; "f"; f; " "; "g"; g; " "; "h"; h
 2 NEXT h
 3 NEXT g
 4 NEXT f
 5 NEXT e
 6 NEXT d
 7 NEXT c
 8 NEXT b
 NEXT a
 END

Результаты работы программы (вывод)

Список позиций, выдаваемый программой, является списком решений исходной задачи:

1  a 1  b 5  c 8  d 6  e 3  f 7  g 2  h 4 
2  a 1  b 6  c 8  d 3  e 7  f 4  g 2  h 5 
3  a 1  b 7  c 4  d 6  e 8  f 2  g 5  h 3 
4  a 1  b 7  c 5  d 8  e 2  f 4  g 6  h 3 
5  a 2  b 4  c 6  d 8  e 3  f 1  g 7  h 5 
6  a 2  b 5  c 7  d 1  e 3  f 8  g 6  h 4 
7  a 2  b 5  c 7  d 4  e 1  f 8  g 6  h 3 
8  a 2  b 6  c 1  d 7  e 4  f 8  g 3  h 5 
9  a 2  b 6  c 8  d 3  e 1  f 4  g 7  h 5 
10  a 2  b 7  c 3  d 6  e 8  f 5  g 1  h 4 
11  a 2  b 7  c 5  d 8  e 1  f 4  g 6  h 3 
12  a 2  b 8  c 6  d 1  e 3  f 5  g 7  h 4 
13  a 3  b 1  c 7  d 5  e 8  f 2  g 4  h 6 
14  a 3  b 5  c 2  d 8  e 1  f 7  g 4  h 6 
15  a 3  b 5  c 2  d 8  e 6  f 4  g 7  h 1 
16  a 3  b 5  c 7  d 1  e 4  f 2  g 8  h 6 
17  a 3  b 5  c 8  d 4  e 1  f 7  g 2  h 6 
18  a 3  b 6  c 2  d 5  e 8  f 1  g 7  h 4 
19  a 3  b 6  c 2  d 7  e 1  f 4  g 8  h 5 
20  a 3  b 6  c 2  d 7  e 5  f 1  g 8  h 4 
21  a 3  b 6  c 4  d 1  e 8  f 5  g 7  h 2 
22  a 3  b 6  c 4  d 2  e 8  f 5  g 7  h 1 
23  a 3  b 6  c 8  d 1  e 4  f 7  g 5  h 2 
24  a 3  b 6  c 8  d 1  e 5  f 7  g 2  h 4 
25  a 3  b 6  c 8  d 2  e 4  f 1  g 7  h 5 
26  a 3  b 7  c 2  d 8  e 5  f 1  g 4  h 6 
27  a 3  b 7  c 2  d 8  e 6  f 4  g 1  h 5 
28  a 3  b 8  c 4  d 7  e 1  f 6  g 2  h 5 
29  a 4  b 1  c 5  d 8  e 2  f 7  g 3  h 6 
30  a 4  b 1  c 5  d 8  e 6  f 3  g 7  h 2 
31  a 4  b 2  c 5  d 8  e 6  f 1  g 3  h 7 
32  a 4  b 2  c 7  d 3  e 6  f 8  g 1  h 5 
33  a 4  b 2  c 7  d 3  e 6  f 8  g 5  h 1 
34  a 4  b 2  c 7  d 5  e 1  f 8  g 6  h 3 
35  a 4  b 2  c 8  d 5  e 7  f 1  g 3  h 6 
36  a 4  b 2  c 8  d 6  e 1  f 3  g 5  h 7 
37  a 4  b 6  c 1  d 5  e 2  f 8  g 3  h 7 
38  a 4  b 6  c 8  d 2  e 7  f 1  g 3  h 5 
39  a 4  b 6  c 8  d 3  e 1  f 7  g 5  h 2 
40  a 4  b 7  c 1  d 8  e 5  f 2  g 6  h 3 
41  a 4  b 7  c 3  d 8  e 2  f 5  g 1  h 6 
42  a 4  b 7  c 5  d 2  e 6  f 1  g 3  h 8 
43  a 4  b 7  c 5  d 3  e 1  f 6  g 8  h 2 
44  a 4  b 8  c 1  d 3  e 6  f 2  g 7  h 5 
45  a 4  b 8  c 1  d 5  e 7  f 2  g 6  h 3 
46  a 4  b 8  c 5  d 3  e 1  f 7  g 2  h 6 
47  a 5  b 1  c 4  d 6  e 8  f 2  g 7  h 3 
48  a 5  b 1  c 8  d 4  e 2  f 7  g 3  h 6 
49  a 5  b 1  c 8  d 6  e 3  f 7  g 2  h 4 
50  a 5  b 2  c 4  d 6  e 8  f 3  g 1  h 7 
51  a 5  b 2  c 4  d 7  e 3  f 8  g 6  h 1 
52  a 5  b 2  c 6  d 1  e 7  f 4  g 8  h 3 
53  a 5  b 2  c 8  d 1  e 4  f 7  g 3  h 6 
54  a 5  b 3  c 1  d 6  e 8  f 2  g 4  h 7 
55  a 5  b 3  c 1  d 7  e 2  f 8  g 6  h 4 
56  a 5  b 3  c 8  d 4  e 7  f 1  g 6  h 2 
57  a 5  b 7  c 1  d 3  e 8  f 6  g 4  h 2 
58  a 5  b 7  c 1  d 4  e 2  f 8  g 6  h 3 
59  a 5  b 7  c 2  d 4  e 8  f 1  g 3  h 6 
60  a 5  b 7  c 2  d 6  e 3  f 1  g 4  h 8 
61  a 5  b 7  c 2  d 6  e 3  f 1  g 8  h 4 
62  a 5  b 7  c 4  d 1  e 3  f 8  g 6  h 2 
63  a 5  b 8  c 4  d 1  e 3  f 6  g 2  h 7 
64  a 5  b 8  c 4  d 1  e 7  f 2  g 6  h 3 
65  a 6  b 1  c 5  d 2  e 8  f 3  g 7  h 4 
66  a 6  b 2  c 7  d 1  e 3  f 5  g 8  h 4 
67  a 6  b 2  c 7  d 1  e 4  f 8  g 5  h 3 
68  a 6  b 3  c 1  d 7  e 5  f 8  g 2  h 4 
69  a 6  b 3  c 1  d 8  e 4  f 2  g 7  h 5 
70  a 6  b 3  c 1  d 8  e 5  f 2  g 4  h 7 
71  a 6  b 3  c 5  d 7  e 1  f 4  g 2  h 8 
72  a 6  b 3  c 5  d 8  e 1  f 4  g 2  h 7 
73  a 6  b 3  c 7  d 2  e 4  f 8  g 1  h 5 
74  a 6  b 3  c 7  d 2  e 8  f 5  g 1  h 4 
75  a 6  b 3  c 7  d 4  e 1  f 8  g 2  h 5 
76  a 6  b 4  c 1  d 5  e 8  f 2  g 7  h 3 
77  a 6  b 4  c 2  d 8  e 5  f 7  g 1  h 3 
78  a 6  b 4  c 7  d 1  e 3  f 5  g 2  h 8 
79  a 6  b 4  c 7  d 1  e 8  f 2  g 5  h 3 
80  a 6  b 8  c 2  d 4  e 1  f 7  g 5  h 3 
81  a 7  b 1  c 3  d 8  e 6  f 4  g 2  h 5 
82  a 7  b 2  c 4  d 1  e 8  f 5  g 3  h 6 
83  a 7  b 2  c 6  d 3  e 1  f 4  g 8  h 5 
84  a 7  b 3  c 1  d 6  e 8  f 5  g 2  h 4 
85  a 7  b 3  c 8  d 2  e 5  f 1  g 6  h 4 
86  a 7  b 4  c 2  d 5  e 8  f 1  g 3  h 6 
87  a 7  b 4  c 2  d 8  e 6  f 1  g 3  h 5 
88  a 7  b 5  c 3  d 1  e 6  f 8  g 2  h 4 
89  a 8  b 2  c 4  d 1  e 7  f 5  g 3  h 6 
90  a 8  b 2  c 5  d 3  e 1  f 7  g 4  h 6 
91  a 8  b 3  c 1  d 6  e 2  f 5  g 7  h 4 
92  a 8  b 4  c 1  d 3  e 6  f 2  g 7  h 5 


Интересно отметить, что эти 92 расположения разбиваются на 12 групп:11 групп по 8 и 1-у из 4-х расположений. Положения внутри групп получаются из одного положения путем преобразований симметрии:отражения от вертикальной и горизонтальной осей, отражения от диагоналей доски и поворотов на 90,180 и 270 градусов.Пары расположений,симметричные относительно горизонтальной оси,имеют сумму номеров равную 93,т.е. для каждой группы эта суммма равна 93*4.Программу,получающую эти группы,программу,получающую позиции ферзей при любом n и другие программы на эту тему см.на сайте:

[ http://nabasice.narod2.ru/]
     

1

  a 1  b 5  c 8  d 6  e 3  f 7  g 2  h 4 :1
  a 4  b 2  c 7  d 3  e 6  f 8  g 5  h 1 :33
  a 8  b 4  c 1  d 3  e 6  f 2  g 7  h 5 :92
  a 1  b 7  c 5  d 8  e 2  f 4  g 6  h 3 :4  +(3)
  a 6  b 3  c 5  d 7  e 1  f 4  g 2  h 8 :71
  a 8  b 2  c 4  d 1  e 7  f 5  g 3  h 6 :89
  a 5  b 7  c 2  d 6  e 3  f 1  g 4  h 8 :60
  a 3  b 6  c 4  d 2  e 8  f 5  g 7  h 1 :22

2

  a 1  b 6  c 8  d 3  e 7  f 4  g 2  h 5 :2
  a 5  b 2  c 4  d 7  e 3  f 8  g 6  h 1 :51
  a 8  b 3  c 1  d 6  e 2  f 5  g 7  h 4 :91
  a 1  b 7  c 4  d 6  e 8  f 2  g 5  h 3 :3  +(2)
  a 6  b 4  c 7  d 1  e 3  f 5  g 2  h 8 :78
  a 8  b 2  c 5  d 3  e 1  f 7  g 4  h 6 :90
  a 4  b 7  c 5  d 2  e 6  f 1  g 3  h 8 :42
  a 3  b 5  c 2  d 8  e 6  f 4  g 7  h 1 :15

3

  a 2  b 4  c 6  d 8  e 3  f 1  g 7  h 5 :5  +(1)
  a 5  b 7  c 1  d 3  e 8  f 6  g 4  h 2 :57
  a 7  b 5  c 3  d 1  e 6  f 8  g 2  h 4 :88
  a 6  b 1  c 5  d 2  e 8  f 3  g 7  h 4 :65
  a 5  b 2  c 6  d 1  e 7  f 4  g 8  h 3 :52
  a 3  b 8  c 4  d 7  e 1  f 6  g 2  h 5 :28
  a 4  b 2  c 8  d 6  e 1  f 3  g 5  h 7 :36
  a 4  b 7  c 3  d 8  e 2  f 5  g 1  h 6 :41

4

  a 2  b 5  c 7  d 1  e 3  f 8  g 6  h 4:6
  a 4  b 6  c 8  d 3  e 1  f 7  g 5  h 2:39
  a 7  b 4  c 2  d 8  e 6  f 1  g 3  h 5:87
  a 4  b 1  c 5  d 8  e 2  f 7  g 3  h 6:29 +(4)
  a 3  b 6  c 2  d 7  e 1  f 4  g 8  h 5:19
  a 5  b 8  c 4  d 1  e 7  f 2  g 6  h 3:64
  a 5  b 3  c 1  d 6  e 8  f 2  g 4  h 7:54
  a 6  b 3  c 7  d 2  e 8  f 5  g 1  h 4:74  

5

  a 2  b 5  c 7  d 4  e 1  f 8  g 6  h 3 :7
  a 3  b 6  c 8  d 1  e 4  f 7  g 5  h 2 :23
  a 7  b 4  c 2  d 5  e 8  f 1  g 3  h 6 :86
  a 5  b 1  c 8  d 4  e 2  f 7  g 3  h 6 :48  +(5)
  a 3  b 6  c 2  d 7  e 5  f 1  g 8  h 4 :20
  a 4  b 8  c 1  d 5  e 7  f 2  g 6  h 3 :45
  a 6  b 3  c 1  d 8  e 5  f 2  g 4  h 7 :70
  a 6  b 3  c 7  d 2  e 4  f 8  g 1  h 5 :73

6

  a 2  b 6  c 1  d 7  e 4  f 8  g 3  h 5 :8
  a 5  b 3  c 8  d 4  e 7  f 1  g 6  h 2 :56
  a 7  b 3  c 8  d 2  e 5  f 1  g 6  h 4 :85
  a 3  b 1  c 7  d 5  e 8  f 2  g 4  h 6 :13  +(6)
  a 3  b 5  c 7  d 1  e 4  f 2  g 8  h 6 :16
  a 6  b 8  c 2  d 4  e 1  f 7  g 5  h 3 :80
  a 4  b 6  c 1  d 5  e 2  f 8  g 3  h 7 :37
  a 6  b 4  c 2  d 8  e 5  f 7  g 1  h 3 :77

7

  a 2  b 6  c 8  d 3  e 1  f 4  g 7  h 5 :9
  a 5  b 7  c 4  d 1  e 3  f 8  g 6  h 2 :62
  a 7  b 3  c 1  d 6  e 8  f 5  g 2  h 4 :84
  a 5  b 1  c 4  d 6  e 8  f 2  g 7  h 3 :47  +(7)
  a 6  b 2  c 7  d 1  e 3  f 5  g 8  h 4 :66
  a 4  b 8  c 5  d 3  e 1  f 7  g 2  h 6 :46
  a 4  b 2  c 5  d 8  e 6  f 1  g 3  h 7 :31
  a 3  b 7  c 2  d 8  e 6  f 4  g 1  h 5 :27

8

  a 2  b 7  c 3  d 6  e 8  f 5  g 1  h 4 :10
  a 4  b 1  c 5  d 8  e 6  f 3  g 7  h 2 :30
  a 7  b 2  c 6  d 3  e 1  f 4  g 8  h 5 :83
  a 7  b 1  c 3  d 8  e 6  f 4  g 2  h 5 :81  +(8)
  a 4  b 7  c 5  d 3  e 1  f 6  g 8  h 2 :43
  a 2  b 8  c 6  d 1  e 3  f 5  g 7  h 4 :12
  a 5  b 8  c 4  d 1  e 3  f 6  g 2  h 7 :63
  a 5  b 2  c 4  d 6  e 8  f 3  g 1  h 7 :50

9

  a 2  b 7  c 5  d 8  e 1  f 4  g 6  h 3 :11
  a 3  b 6  c 4  d 1  e 8  f 5  g 7  h 2 :21
  a 7  b 2  c 4  d 1  e 8  f 5  g 3  h 6 :82
  a 5  b 1  c 8  d 6  e 3  f 7  g 2  h 4 :49  +(9)
  a 5  b 7  c 2  d 6  e 3  f 1  g 8  h 4 :61
  a 4  b 8  c 1  d 3  e 6  f 2  g 7  h 5 :44 
  a 6  b 3  c 5  d 8  e 1  f 4  g 2  h 7 :72
  a 4  b 2  c 7  d 3  e 6  f 8  g 1  h 5 :32

10

  a 3  b 5  c 2  d 8  e 1  f 7  g 4  h 6 :14
  a 6  b 4  c 7  d 1  e 8  f 2  g 5  h 3 :79
  a 6  b 4  c 7  d 1  e 8  f 2  g 5  h 3 :79 
  a 5  b 3  c 1  d 7  e 2  f 8  g 6  h 4 :55 +(12)
  a 5  b 3  c 1  d 7  e 2  f 8  g 6  h 4 :55
  a 4  b 6  c 8  d 2  e 7  f 1  g 3  h 5 :38
  a 3  b 5  c 2  d 8  e 1  f 7  g 4  h 6 :14
  a 4  b 6  c 8  d 2  e 7  f 1  g 3  h 5 :38

11

  a 3  b 5  c 8  d 4  e 1  f 7  g 2  h 6 :17
  a 6  b 2  c 7  d 1  e 4  f 8  g 5  h 3 :67
  a 6  b 4  c 1  d 5  e 8  f 2  g 7  h 3 :76
  a 5  b 7  c 1  d 4  e 2  f 8  g 6  h 3 :58  +(10)
  a 6  b 3  c 1  d 7  e 5  f 8  g 2  h 4 :68
  a 4  b 2  c 8  d 5  e 7  f 1  g 3  h 6 :35
  a 3  b 7  c 2  d 8  e 5  f 1  g 4  h 6 :26
  a 3  b 6  c 8  d 2  e 4  f 1  g 7  h 5 :25  

12

  a 3  b 6  c 2  d 5  e 8  f 1  g 7  h 4 :18
  a 4  b 7  c 1  d 8  e 5  f 2  g 6  h 3 :40
  a 6  b 3  c 7  d 4  e 1  f 8  g 2  h 5 :75
  a 6  b 3  c 1  d 8  e 4  f 2  g 7  h 5 :69  +(11)
  a 4  b 2  c 7  d 5  e 1  f 8  g 6  h 3 :34
  a 3  b 6  c 8  d 1  e 5  f 7  g 2  h 4 :24
  a 5  b 2  c 8  d 1  e 4  f 7  g 3  h 6 :53
  a 5  b 7  c 2  d 4  e 8  f 1  g 3  h 6 :59  
                
 Вот как выглядит это разделение.Причём сумма номеров позиций 
 в каждой группе :372.Группа номер 10 – симметрическая.


В этой группе при повороте на 180 градусов позиции переходят сами в себя. Характерной особенностью симметрических положений является пустой квадрат 4*4 в середине доски и пустые диагонали. Таким образом,имея 12 расположений — по одному из каждой группы, можно получить все остальные,что,впрочем,известно из шахматной литературы: (Е.Я.Гик:Шахматы и математика,Наука,Москва 1983). В списке крестиком отмечены позиции,которые выбраны в качестве базовых (т.е. тех,с которыми производятся преобразования симметрии) в английской и украинской версии данной статьи в Википедии и указаны номера, под которыми они в ней фигурируют. Здесь же базовые позиции (первые позиции в каждой группе) выбраны по признаку минимального номера в группе. Очевидно, что наборов базовых позиций можно составить (8^11)*4.

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

Ниже приведен только класс, непосредственно реализующий алгоритм решения. (Полный код программы можно скачать по ссылке: http://adels.zp.ua/other/queens_cs.zip).

  class QueensProblem : IProblem {
    private int size;
    private int[] positions;
    private List<int[]> saved;
    private IProblemCallback cb;
 
    public void Init(int size, IProblemCallback cb) {
      this.size = size;
      this.cb = cb;
      positions = new int[size];
      saved = new List<int[]>();
    }
 
    private void Save() {
      saved.Add((int[]) positions.Clone());
    }
 
    private bool Step() {
      int s = size;
      for (int i = 1; i < s; i++) {
        int pos = positions[i];
        while (true) {
          bool found = false;
          for (int j = 0; j < i; j++) {
            int epos = positions[j];
            if (epos == pos || pos - i == epos - j || pos + i == epos + j) {
              if (++pos >= s) {
                if (!Next(i)) return false;
                while (++i < s) positions[i] = 0;
                return true;
              }
              positions[i] = pos;
              found = true;
              break;
            }
          }
          if (!found) break;
        }
      }
      Save();
      return Next(s - 1);
    }
 
    private bool Next(int pos) {
      int s = size;
      if (++positions[pos] < s) return true;
      do {
        positions[pos] = 0;
        if (++positions[--pos] < s) return true;
      } while (pos > 0);
      return false;
    }
 
    public int Solve() {
      float prev = 0;
      int sq = size * size;
      while (Step()) {
        int part = positions[0] * size + positions[1];
        if (part != prev) cb.Progress((float) (prev = part) / sq);
      }
      return saved.Count;
    }
 
    public List<int[]> GetResults() {
      return saved;
    }
 
    public int Size {
      get { return size; }
    }
 
  }

Время выполнения алгоритма

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

Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором 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

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

Альтернативный подход

Если решать более общую задачу об 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 результат работы этого алгоритма показан на картинке.

Решение, полученное с помощью эвристики.(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++

#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
        int N, Mod;
        std::vector < int > L;
 
        std::cin >> N;
 
        Mod = N % 12;
 
        for ( int x = 2; x <= N; x += 2 )
                L.push_back( x );
 
        if ( Mod == 3 || Mod == 9 )
        {
                L.push_back( 2 );
                L.erase( L.begin() );
        }
 
        if ( Mod == 8 )
        {
                std::vector < int > V;
                for ( int x = 1; x <= N; x += 2 )
                        V.push_back( x );
                for ( int i = 1; i < V.size(); i += 2 )
                        std::swap( V.at( i ), V.at( i - 1 ) );
                for ( int i = 0; i < V.size(); ++i )
                        L.push_back( V.at( i ) );
        }
        else
                for ( int x = 1; x <= N; x += 2 )
                        L.push_back( x );
 
        if ( Mod == 2 && N >= 3 )
        {
                std::swap( *std::find( L.begin(), L.end(), 1 ), *std::find( L.begin(), L.end(), 3 ) );
                if ( N >= 5 )
                {
                        L.erase( std::find( L.begin(), L.end(), 5 ) );
                        L.push_back( 5 );
                }
        }
 
        if ( Mod == 3 || Mod == 9 )
        {
                L.erase( std::find( L.begin(), L.end(), 1 ) );
                L.push_back( 1 );
                L.erase( std::find( L.begin(), L.end(), 3 ) );
                L.push_back( 3 );
        }
 
        for ( int i = 0; i < L.size(); ++i )
                std::cout << L.at( i ) << " ";
 
        return 0;
}

Реализация на Haskell

position n = evenPosition ++ oddPosition where
  modN = n `mod` 12
  evenPosition
    | modN == 3 || modN == 9    = [4,6..n] ++ [2]
    | otherwise                 = [2,4..n]
  oddPosition = oneThree $ fiveSeven others where
    others
      | modN == 8       = swapPairs [9,11..n]
      | otherwise       = [9,11..n]
      where
        swapPairs []    = []
        swapPairs [x]   = [x]
        swapPairs (y:x:xs) = x:y:swapPairs xs   
    fiveSeven
      | modN == 2 && n >= 5     = ([7] ++) . (++ [5])
      | modN == 8               = ([7,5] ++)
      | n < 7                   = ([5,7..n] ++)
      | otherwise               = ([5,7] ++)
    oneThree
      | modN == 3 || modN == 9                  = (++ [1,3])
      | modN == 8 || (modN == 2 && n >= 3)      = ([3,1] ++)
      | n < 3                                   = ([1] ++)
      | otherwise                               = ([1,3] ++)
 
main = print $ map position [8,14,15,20]
-- [[2,4,6,8,3,1,7,5],
--  [2,4,6,8,10,12,14,3,1,7,9,11,13,5],
--  [4,6,8,10,12,14,2,5,7,9,11,13,15,1,3],
--  [2,4,6,8,10,12,14,16,18,20,3,1,7,5,11,9,15,13,19,17]]

Ссылки

Задачу о N ферзях признали NP-полной задачей / Хабр


Первый вариант головоломки 1850 года, когда два ферзя заранее установлены на доску, а игрок должен расставить остальных ферзей (два решения задачи см. под катом)

Задача о N ферзях состоит в том, чтобы разместить N ферзей на доске размером N×N таким образом, чтобы ни один ферзь не находился под боем другого, при этом на доске заранее установлены несколько ферзей. То есть в итоге никакие два ферзя не должны находиться на одной линии или диагонали. Впервые задачку сформулировали в 1848 году, а в 1850 году придумали вариант головоломки, когда некоторое количество ферзей заранее поставлено на доску, а игрок должен расставить остальных, если это возможно.

Исследователи из Сент-Эндрюсского университета (Шотландия) опубликовали научную статью, в которой доказывают, что задача о N ферзях является не только #P-полной задачей, но также NP-полной задачей. Более того, Математический институт Клэя (США) готов заплатить миллион долларов любому, кто сможет оптимизировать решение этой задачи как задачи на доказательство P=NP.

Как известно, в теории сложности #P является классом проблем, решением которых является количество успешных, то есть, завершающихся в допускающих состояниях, путей вычислений для некой недетерминированной машины Тьюринга, работающей полиномиальное время. Вычислительные задачи класса #P (counting problems) связаны с соответствующими задачами разрешимости (decision problems) класса NP.

Учёные отмечают, что эта задача может быть самой простой среди NP-полных задач, чтобы объяснить суть этих проблем любому человеку, который знает правила игры в шахматы. У этой задачи вообще очень интересная история. В своё время она привлекла внимание Гаусса, который даже сделал небольшую ошибку в её решении (на доске 8×8 он сообщил о 76 решениях, но потом сам признал четыре из них ошибочными, так что остались только 72, а позже Гаусс установил все 92 решения для доски 8×8).

Обобщение задачи для доски N×N привлекло внимание многих математиков. За последние полвека вышло несколько десятков научных работ, посвящённых этой проблеме. Как минимум шесть из них цитируются более 400 раз на Google Scholar: это Golomb & Baumert, 1965; Bitner & Reingold, 1975; Mackworth & Freuder, 1985; Minton, Johnston, Philips, & Laird, 1992; Selman, Levesque & Mitchell, 1992; Crawford, Ginsberg, Luks, & Roy, 1996.

Сложность задачи о N ферзях часто неправильно оценивают. Даже в обильно цитируемых работах её часто называют NP-сложной задачей (NP-hard), но она будет таковой только при условии, что P=NP. На самом деле вычислительный вариант задачи, то есть определение количества решений для N ферзей, представляет собой последовательность A000170 из Онлайн-энциклопедии целочисленных последовательностей. Эта последовательность сейчас известна максимум для n=27, где количество решений превышает 2,34×1017. Не известно ни одно более эффективное решение проблемы, чем простой перебор. Так, для n=27 в 2016 году использовался масштабный параллельный поиск на FPGA.

В то же время, если компьютер начнёт перебор возможных положений ферзей на доске 1000×1000 клеток, то он загрузится этой задачей навечно. По мнению учёных, если некто найдёт действительно быстрый и эффективный способ решения, то сможет извлечь из этого гораздо бóльшую выгоду, чем один миллион долларов от Математического института Клэя. «Если вы напишете программу, которая может решить проблему действительно быстро, вы могли бы адаптировать её для решения многих важных задач, с которыми мы сталкиваемся ежедневно, — говорит профессор информатики Ян Гент (Ian Gent), один из авторов научной работы. — Среди них тривиальные проблемы, такие как поиск самой большой группы ваших друзей в Facebook, которые не знают друг друга, или очень важные задачи, например, взлом кодов, которые обеспечивают безопасность всех наших онлайн-транзакций».

Но это чисто теоретические измышления. На практике никто пока не приблизился к решению задачи о N ферзях быстрым и эффективным способом. За доказательство, что существует более эффективный способ решения задачи, чем простой перебор всех вариантов, дадут миллион долларов.

Научная статья опубликована в августе 2017 года в журнале Journal of Artificial Intelligence Research (doi:10.1613/jair.5512, pdf).



P.S. Два решения задачи с КДПВ:

Кто может сделать быстрее? «Задача о восьми Ферзях»

  • include ‘%fasminc%\win32ax.inc’

  •  

  • .data

  •  

  • cnt dd 0

  • title   db ‘test time’,0

  • msg db ‘F( 0’

  • n   db ‘)=         0’

  • v   db »,13,’time=      0′

  • t   db ‘ ms’,13,’continue?’,0

  •  

  • .code

  •  

  • ;единичные биты в ebx — свободные горизонтали

  • ;единичные биты в esi,edi — свободные диагонали

  • ;ebp — уровень рекурсии

  • work:

  •     push eax

  •     mov eax,ebx

  •     and eax,esi

  •     and eax,edi  ;единичные биты соответствуют доступным клеткам

  •     jmp work_1

  • work_0:

  •     shl edx,cl   ;1 в клетке куда ставим ферзя

  •     xor eax,edx  ;исключаем эту клетку из списка

  •     dec ebp      

  •     jz work_draw ;если последний уровень, то найден новый вариант

  •     push ebx

  •     push esi

  •     push edi

  •  

  •     xor ebx,edx  ;помечаем что горизонталь,

  •     xor esi,edx  ;обе диагонали

  •     xor edi,edx  ;заняты

  •  

  •     stc          ;при переходе к новому ряду у нас выбывают две диагонали

  •     lea esi,[esi+esi+1] ;проходящие через крайние клетки предыдущего ряда

  •     rcr edi,1    ;и добавляются две диагонали, проходящие через крайние

  •                      ;клетки нового ряда  

  •     call work

  •     pop edi

  •     pop esi

  •     pop ebx

  •     inc ebp

  • work_1:

  •     bsf ecx,eax ;ищем свободную клетку в текущем ряду

  •     mov edx,1

  •     jnz work_0  ;переход, если нашли

  •     pop eax

  •     ret

  • work_draw:

  •     inc ebp

  •     inc [cnt] ;увеличиваем счётчик найденных вариантов

  •     bsf ecx,eax

  •     mov edx,1

  •     jnz work_0

  •     pop eax

  •     ret

  •  

  • eaxtostr:

  •     xor edx,edx

  •     mov ecx,10

  •     div ecx

  •     add dl,’0′

  •     dec edi

  •     mov [edi],dl

  •     test eax,eax

  •     jnz eaxtostr

  •     ret

  •  

  • start:

  •     mov ebp,13

  •     .l0:

  •     invoke GetTickCount

  •     push eax

  •     mov [cnt],0

  •     mov eax,ebp

  •     mov edi,n

  •     call eaxtostr

  •  

  •     mov ebx,1

  •     mov ecx,ebp

  •     shl ebx,cl

  •     dec ebx

  •     mov esi,-1

  •     mov edi,-1

  •     call work

  •  

  •     invoke GetTickCount

  •     pop edx

  •     sub eax,edx

  •     mov edi,t

  •     call eaxtostr

  •     mov eax,[cnt]

  •     mov edi,v

  •     call eaxtostr

  •     invoke MessageBox,0,msg,title,MB_YESNO

  •     inc ebp

  •     cmp eax,6

  •     jz .l0

  •     invoke ExitProcess,0

  •  

  • .end start

  • Решение задачи о восьми ферзях методом ООП

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

    В шахматах ферзь может бить любую фигуру, стоящую в одном с ним ряду, столбце или диагонали

    Необходимо расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого

    Одно из решений задачи о восьми ферзях

    8Q

    5Q

     

     

     

    4

     

    Q

    3

     

    Q

    2

     

    Q

    1

    Q

     

     

    a b

    c d e f g h

    2

    Традиционное (процедурное) решение задачи

    Для описания позиций фигур используется матрица

    Программа решает задачу, систематически перебирая значения в матрице и проверяя каждую позицию: не удовлетворяет ли она условию?

    Традиционная программа подобна человеку, находящемуся над доской и передвигающему безжизненные фигуры

    3

    Объектно-ориентированное решение задачи

    В объектно-ориентированном подходе фигуры наделяются жизнью, чтобы они решили проблему самостоятельно

    Вместо одного существа, управляющего процессом, ответственность за нахождение решения разделяется среди многих взаимодействующих агентов

    Шахматные фигуры выступают одушевленными существами, взаимодействующими между собой, которым поручено найти решение

    4

    Исследование задачи

    В любом случае никакие два ферзя не могут занимать один столбец и, следовательно, все столбцы заняты

    Каждый ферзь должен знать только о своем соседе слева

    Приемлемое решение для столбца N — это такая конфигурация столбцов с 1 по N, в которой ни один

    5 ферзь из этих столбцов не бьет другого

    Исследование задачи

    Каждому ферзю будет поручено найти приемлемое решение для себя и своих соседей слева

    Решение всей задачи будет получено, когда самый правый ферзь отыщет приемлемое решение

    Получение общего решения

    Сначала все ферзи располагаются на первой строке разных столбцов доски

    Последовательно для каждого ферзя, начиная с крайнего левого, находится приемлемое решение для него и его соседей слева

    Решение будет получено, когда получим приемлемое решение для крайнего правого ферзя или когда

    7 он не будет никем атакован

    Получение приемлемого решения для ферзя и его соседей слева

    Ферзь проверяет, находится ли он под атакой ферзей слева

    Если его атакуют, то он смещается вверх

    Если смещаться некуда, то он просит сместиться соседей слева для получения приемлемого решения и сам смещается на первую строку

    Крайний левый ферзь перемещается вверх, а если 8 смещаться некуда, то — на первую строку

    Расстановка первых трех ферзей

    8

     

     

     

     

     

     

     

     

    8

     

     

     

     

     

     

     

     

     

    8

     

     

     

     

     

     

     

     

     

    7

     

     

     

     

     

     

     

     

    7

     

     

     

     

     

     

     

     

     

    7

     

     

     

     

     

     

     

     

     

    6

     

     

     

     

     

     

     

     

    6

     

     

     

     

     

     

     

     

     

    6

     

     

     

     

     

     

     

     

     

    5

     

     

     

     

     

     

     

     

    5

     

     

     

     

     

     

     

     

     

    5

     

     

    Q

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    4

     

     

     

     

     

     

     

     

    4

     

     

     

     

     

     

     

     

     

    4

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    3

     

     

     

     

     

     

     

     

    3

     

    Q

     

     

     

     

     

     

    3

     

    Q

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    2

     

     

     

     

     

     

     

     

    2

     

     

     

     

     

     

     

     

     

    2

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    1

     

     

     

     

     

     

     

     

     

    1

     

     

     

     

     

     

     

     

     

    1

    Q

    Q

    Q

    Q

    Q

    Q

    Q

    Q

    Q

     

     

    Q

    Q

    Q

    Q

    Q

    Q

    Q

     

     

     

    Q

    Q

    Q

    Q

    Q

     

     

     

     

     

     

    a b c d e f g h

     

    a b c d e f g h

     

    a b c d e f g h

    шаг 1

    шаг 2

    шаг 3

    Задача восьми королев

    Эту головоломку очень легко расширить (и сжать) на шахматные доски других размеров.

    Справа — таблица количества решений для плат n x n разного размера.

    Для платы каждого размера я показал количество полных решений, а также количество различных типов решений (уникальных перед поворотами и отражениями).

    Тривиально, есть только одно решение для платы 1 x 1 , и нетрудно увидеть, что нет возможных решений для платы 2 x 2 или 3 x 3 .

    Интересно, что хотя на плате 5 x 5 имеется 10 решений, количество решений падает с до 4 решений на плате 6 x 6 .

    (в настоящее время) не существует известной формулы для определения количества возможных решений для платы n x n , и поиск в Интернете показывает, что самый высокий расчетный размер платы на сегодняшний день составляет 26 x 26 .

    ,148 ,148 9000,658
    Board Total Solutions Unique Solutions
    1 x 1 1 1
    2 x 2 0 0
    3 x 3 0 0
    4 x 4 2 1
    5 x 5 10 2
    6 x 6 4 1
    7 x 7 40 6
    8 x 8 92 12
    9 x 9 352 46
    10 x 10 724 92
    11 x 11 2,680 341
    12 x 12 14,200 1,787
    13 x 13 73,71 2 9,233
    14 x 14 365,596 45,752
    15 x 15 2,279,184 285,053
    16 x 16 14,772,512 1,846,955 1,846,955 900 95,815,104 11,977,939
    18 x 18 666,090,624 83,263,591
    19 x 19 4,968,057,848 621,012,754
    48 621,012,754
    621,012,754
    х 21 314,666,222,712 39,333,324,973
    22 х 22 2,691,008,701,644 336,376,244,042
    23 x 23 24,233,937,684,440 429 63 24,233,937,684,440 429 227,514,171,973,736 28,439,272,956,934
    25 x 25 2,207,893,435,808,350 275,986,683,743,434
    26 x 26 22,317,699,616,364,54,2536 22,317,699,616,364,54,2936
    .

    Решите шахматную задачу, выиграйте миллион долларов

    Фредерик Фридель

    04.09.2017 — Старая головоломка, предложенная в 1848 году: разместить восемь ферзей на шахматной доске так, чтобы ни одна из них не атаковала другую. Решение было опубликовано двумя годами позже, но проблема n ферзей на шахматной доске n x n (например,г. 100 ферзей на доске 100 x 100) призрачны. Современным компьютерам потребуются тысячи лет, чтобы решить загадку больших чисел. Если вы можете написать программу, которая будет намного быстрее, вы можете выиграть крутой миллион долларов. Действуй!


    ChessBase 15 — Мега пакет

    Найдите правильную комбинацию! Программа ChessBase 15 + новая база данных Mega Database 2020 с 8 миллионами партий и более 80 000 мастер-анализов.Плюс журнал ChessBase (DVD + журнал) и членство в CB Premium на 1 год!

    Больше…

    Пазл «Расширение восьми королев»

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

    Задача была предложена Максом Беззелем в 1848 году, первые решения были предложены в 1850 году Францем Науком, который распространил головоломку на n ферзей на шахматной доске n × n клеток. С тех пор многие математики, включая Карла Фридриха Гаусса, работали как над головоломкой о восьми ферзях, так и над ее обобщенной версией n-ферзей.

    Бесконечная шахматная доска — изображение из этого крутого видео Infinite Chess | Источник: канал PBS Infinite Series на YouTube

    Вы можете попробовать решить задачу 8×8 на этой замечательной доске JavaScript, предоставленной Рональдом Дэнзером, которая доступна в разделе «Источник JavaScript» (если доска не отображается слева, перейдите сюда).

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

    Все двенадцать решений приведены внизу страницы.

    Гарднер развил задачу дальше: поместите трех белых ферзей и пять черных ферзей на шахматную доску 5 x 5 так, чтобы ни один ферзь одного цвета не атаковал одну ферзя другого цвета.Есть только одно решение этой проблемы, исключая отражения и вращения. Вы можете попытаться найти решение этой проблемы — хотя это не является предметом сегодняшней статьи.

    Вызов на миллион долларов

    Загадка с восемью ферзями является примером более общей «задачи n ферзей», которая требует размещения n не атакующих ферзей на шахматной доске размером n × n . Решения существуют для всех натуральных чисел n (за исключением n = 2 и n = 3 ).

    Профессор Ян Гент и доктор Питер Найтингейл | Фото: Phys.org © Stuart Nicol

    Теперь компьютерные ученые, профессор Ян Гент и доктор Питер Найтингейл из Университета Сент-Эндрюс в Шотландии бросают вызов компьютерным программистам, чтобы решить задачу для очень больших значений n . Решения, использующие грубую силу для 8×8, занимают микросекунды, но команда обнаружила, что как только шахматная доска достигает 100 x 100 клеток или 1000 на 1000, компьютерные программы больше не могут обрабатывать очень большие числа за разумный промежуток времени.Фактически, для решения текущих программ теоретически потребуется 1000 лет.

    Итак, Гент и Найтингейл предлагают приз в размере 1 000 000 долларов каждому, кто найдет более быстрое решение. Это очень важно, потому что, по словам Гента, «если бы вы могли написать компьютерную программу, которая могла бы решить проблему очень быстро, вы могли бы адаптировать ее для решения многих наиболее важных проблем, с которыми мы все сталкиваемся ежедневно. Это включает в себя тривиальные задачи, такие как работа из самой большой группы ваших друзей в Facebook, которые не знают друг друга, или из очень важных, например, взлома кодов, обеспечивающих безопасность всех наших онлайн-транзакций.«

    Решения

    Вот двенадцать решений, исключающих повороты и отражения:

    Обновление
    , 5 сентября:

    В ответ на критику Айгереха в комментариях (что отчасти верно), вот заявление Института Клея:

    Новое исследование касается задачи завершения n-ферзей , где не только доска больше, но также уже размещено несколько ферзей. То есть, если некоторые ферзи уже были размещены на доске n -by- n , можете ли вы найти решение загадки n -Queens, не перемещая ни одной из этих ферзей? Технический вклад, заявленный в этой статье, заключается в том, что задача завершения n -Queens попадает в класс, известный как NP-Complete .Если это верно, это означает, что любой алгоритм, который может решить задачу завершения n -Queens, может косвенно использоваться для решения любой другой задачи в классе NP. Это не относится к исходной головоломке n -Queens, потому что добавление заранее размещенных ферзей имеет решающее значение.

    «К сожалению, в некоторых отчетах о нашей работе сложилось впечатление, что решение головоломки с 8 ферзями или головоломки с числами n для всех n может привести к присуждению Премии тысячелетия.Это не так по двум причинам. Во-первых, как только что упоминалось, статья посвящена проблеме завершения n -Queens, а не исходной головоломке n -Queens. Во-вторых, даже открытия алгоритмического решения головоломки n -Queens Completion для всех n было бы недостаточно. Было бы необходимо либо доказательство того, что существует алгоритм, который может решить головоломку n -Queens Completion за полиномиальное время, либо доказательство того, что такого алгоритма не существует.”

    Ссылки
    .

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    Theme: Overlay by Kaira Extra Text
    Cape Town, South Africa