Теорема о N ферзях

    Полный  статистический анализ алгоритма показывает, что вероятность успеха равна 0.1293, а среднее число повторений, необходимых для его достижения, около 6.971. Приведенное выше уравнение показывает, что алгоритм выполнит при этом 55 проходов. Рекурсивному же алгоритму понадобится, по крайней мере, вдвое больше проходов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Глава 2. Алгоритмы решения задачи доски N*N.

 
 

    2.1. Рекуррентный алгоритм: 

    На  доске 1х1 один ферзь ставится на одно-единственное поле, и решение существует. На доске 2х2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзя поставить некуда. На доске 3х3 умещаются только два мирных ферзя. Итак, для досок 2х2 и 3х3 задача не имеет решения. Эти два случая представляют собой исключение. Для всех N > 3 на доске NxN можно расставить n не угрожающих друг другу ферзей.

    На  доске 4x4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5x5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5х5.

    Заметим, что в общем случае N расстановок (решений задачи) могут заполнить при наложении всю доску NхN только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.

    Классическим  решением задачи N ферзей является прямой перебор с отсечением. Прямой перебор заключается в испытании на конфликтность всех возможных комбинаций. Например, на доске существуют N^2 позиции, таким образом, мы имеем N^2 возможных позиций для первого ферзя, N^2-1 для второго и т.д. Общее число возможных расположений всех ферзей составляет (N^2, N) = (N^2)!/((N^2-N)! * n!). Если перебрать все эти позиции, можно найти все правильные решения. Для n=10 число всех позиций равно ~1.73*10^13. 

      Поскольку в неконфликтном расположении  на одной горизонтали может  стоять только один ферзь, то мы можем ограничиться расстановкой одного ферзя на первой горизонтали, второго -  на второй и т.д. Это дает нам N возможных положений для каждого ферзя и N^N различных расположений. Для N=10 это будет 10^10. Заметим, что на каждой вертикали также может быть только один ферзь: i-й ферзь имеет только n-i+1 возможных положений, поскольку предыдущие i-1 ферзей уже заняли i-1 вертикалей. Теперь общее количество возможностей сократилось до N! или 3.6*10^6 вариантов для n=10.

      И последний способ уменьшить количество возможных вариантов – контролировать положение ферзей на одной диагонали. Хотя это просто запрограммировать, бывает трудно дать оценку количества перебираемых вариантов.  

    2.2. Алгоритмы Лас-Вегаса или Алгоритм поиска с возвратом: 

    Если решать более общую задачу об N ферзях, то такой перебор вариантов даже с использованием описанных выше сокращений будет весьма долго работать уже при N = 20, так как 20! = 2.433×10^18. 

    2.3. Эвристический алгоритм: 

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

    Для решения поставленной задачи эвристический  алгоритм будет выглядеть так:

    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) Разместить ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем поместить следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т.д..

    Примеры:

    8 ферзей   (остаток 8): 2, 4, 6, 8, 1, 3, 5, 7.

    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. 
 
 
 
 

    Заключение 

    Анализируя  данные алгоритмы нужно отметить, что их эффективность напрямую зависит  от размера «доски». При небольшом  размере по эффективности преобладает Алгоритм Лас-Вегаса. А при увеличении размера преобладают рекуррентный и эвристический. Но, т.к. эвристический правилен не при всех значениях N, то самым эффективным из предложенных является рекуррентный.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Список  литературы 

    

1. М. Гарднер Математические досуги. -  2-е изд., испр. и доп. Москва; Мир, 2000.
2. Дж. Макконел Основы современных алгоритмов. - 2-е изд., Москва; Техномир, 2004.
3. Е. Корнилов Программирование шахмат и других логических игр. – 1-ое изд., Санкт-Петербург; БХВ-Петербург, 2005.
4. А. Левитин Введение в анализ и разработку алгоритмов – Москва; Вильямс, 2006.
5. Вирт Н. Алгоритмы и структура данных – Санкт-Петербург; Невский Диалект, 2005.
6. А. Ахо, Дж. Хопфорт, Дж. Ульман Построение и анализ вычислительных алгоритмов – Москва; Мир, 1979.
7. Д. Кнут Искусство программирования т.1,2,3 – Москва; 1968.

 
 
 
 
 
 
 
 
 
 

    Приложения 
 

    Приложение 1:

    1.  program Queens ;

    2. var q : array [ 1 . . 8 ] of integer ;

    3.  I , q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 , n : integer ;

    4.  function boy ( c : integer ) : boolean ;

    5. var j : integer ; 

    6.  r e s : boolean ; 

    7.  begin

    8.  r e s :=fal se ;

    9.  for j :=1 to c−1 do

    10.  r e s :=r e s or ( ( c=j ) or ( q [ c ]=q [ j ] ) or

    11 . ( ( c+q [ c ] )=( j+q [ j ] ) ) or ( ( c−q [ c ] )=( j−q [ j ] ) ) ) ;

    12. boy:=r e s ;

    13.  end;

    14.

    15.  begin

    16.  n:=1;

    17.  for i :=1 to 8 do q [ i ] :=1 ;

    18.  for q1 :=1 to 8 do

    19.  begin

    20.  q [ 1 ] := q1 ;

    21. for q2 :=1 to 8 do

    22.  begin

    23.  q [ 2 ] := q2 ;

    24.  i f ( not ( boy ( 2 ) ) ) then

    25.  for q3 :=1 to 8 do

    26.  begin

    27.  q [ 3 ] := q3 ;

    28.  i f ( not ( boy ( 3 ) ) ) then

    29.  for q4 :=1 to 8 do

    30.  begin

    31.  q [ 4 ] := q4 ;

    32.  i f ( not ( boy ( 4 ) ) ) then

    33.  for q5 :=1 to 8 do

    34.  begin

    35.  q [ 5 ] := q5 ;

    36. i f ( not ( boy ( 5 ) ) ) then

    37.  for q6 :=1 to 8 do

    38.  begin

    39.  q [ 6 ] := q6 ;

    40.  i f ( not ( boy ( 6 ) ) ) then

    41.  for q7 :=1 to 8 do

    42.  begin

    43.  q [ 7 ] := q7 ;

    44.  i f ( not ( boy ( 7 ) ) ) then

    45.  for q8 :=1 to 8 do

    46.  begin

    47.  q [ 8 ] := q8 ;

    48.  i f ( not ( boy ( 8 ) ) ) then

    49.  begin

    50.  writeln ( ’Solution ’ ,n ) ;

    51.  for i :=1 to 8 do writeln ( ’(’ , i , ’,’ , q [ i ] , ’) ’ , boy ( i ) ) ;

    52. inc (n ) ;

    53.  end;

    54. end;

    55. end;

    56. end;

    57. end;

    58. end;

    59. end;

    60. end;

    61. end;

    62. end. 

    Приложение 2:

Queens(result)

result содержит номера  вертикалей для  ферзей

с соответствующих  горизонталей

возвращает 1 в случае успеха и 0 в случае неудачи

row=l

repeat 

// ферзи уже расставлены  в горизонталях l..row-l

spotsPossible=0

for i=l to 8 do

if клетка (row.i) атакована then

spotsPossible=spotsPossible+l

if uniform(l,spotsPossible)=l then

try=i

end if

end if

end for

if spotsPossible>0 then

result[row]=try

row=row+l

end if

return (spotsPossible>0)