Содержание

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Введение 

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

    Задача  о восьми ферзях — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.

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

    История:

    Любопытно, что многие авторы ошибочно приписывали  эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.

    Строгое доказательство того, что 92 решения  исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.

    Цель  задания:

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

    1) Построить одно, любое решение  задачи.

    2) Аналитически доказать, что решение  существует.

    3) Определить количество решений.

    4) Построить все возможные решения.

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

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

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

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

1. Рекуррентный  способ:

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

    таким образом, чтобы никакие два из них не угрожали друг другу.

          Решение:

       Рассмотрим шахматную доску, клетки которой помечены с помощью

    системы координат следующим образом:

 

Можно заметить, что два ферзя, которые  находятся в клетках с координатами (x1, y1) и (x2, y2), будут бить друг друга если выполняется хотя бы одно из следующих равенств:

    1) x1 = x2, то есть ферзи находятся  на одной вертикали;

    2) y1 = y2, то есть ферзи находятся  на одной горизонтали;

    3) x1+y1 = x2+y2, то есть ферзи находятся  на одной диагонали, идущей

снизу вверх слева направо. Это равенство верно только для приведен-

ной нумерации  клеток шахматной доски;

    4) x1−y1 = x2−y2, то есть ферзи находятся  на одной диагонали, идущей  сверху вниз слева направо.  Это равенство также верно  только для приведенной нумерации  клеток шахматной доски.

    Очевидно, что все восемь ферзей находятся  на разных вертикалях шахматной доски, иначе найдутся два из них, которые  бьют друг друга. Поэтому нам нужно  перебрать для каждого ферзя  все возможные горизонтали, где  он может встать и проверить, чтобы все ферзи не были под боем. Заведем массив q, индекс которого соответствует номеру ферзя, а значение q[i] указывает на какой по счету горизонтали находится i-й ферзь.

    Поскольку решение предполагает переборный алгоритм, заведем восемь переменных q1, . . . , q8, которые будут пробегать от 1 до 8 и устанавливать соответствующего ферзя на выбранную горизонталь. Например, если qi=4, это значит, что i-го ферзя необходимо поставить на 4-ю горизонталь. Зададим функцию boy(c), которая в качестве аргумента будет принимать номер ферзя и проверять, не бьют ли ферзя с номером «c» ферзи с 1-го до «c» − 1-го. Эта функция возвращает значение «истина» в случае если «c»-го ферзя бьет хотя бы один ферзь и «ложь» в противном случае. Это делается

так:

      См. Приложение 1. 

    Данная  программа ищет решения все возможные  решения задачи и выводит их число: 92. Интересно отметить, что эти 92 расположения разбиваются на 12 групп: при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам:

    

    Например, из расстановки, показанной на рис. А, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. В. А при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, – на рис. Г. При помощи других поворотов и отражений доски можно получить еще пять решений. Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок. Вот один из таких наборов:

    1) см. рис. А;

    2) см. рис. Б;

    3) a4, b1, c5, d8, e6, f3, g7, h2;

    4) a4, b2, c5, d8, e6, f1, g3, h7;

    5) a4, b2, c7, d3, e6, f8, g1, h5;

    6) a4, b2, c7, d3, e6, f8, g5, h1;

    7) a3, b5, c2, d8, e6, f4, g7, h1;

    8) a4, b1, c5, d8, e2, f7, g3, h6;

    9) a4, b7, c3, d8, e2, f5, g1, h6;

    10) a6, b4, c2, d8, e5, f7, g1, h3;

    11) a4, b8, c1, d5, e7, f2, g6, h3;

    12) a4, b2, c7, d5, e1, f8, g6, h3.

    Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений  доски. Основная расстановка на рис. Б является симметрической. Другие одиннадцать основных расстановок – простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

       

      Алгоритмы Лас-Вегаса никогда не возвращают неправильный ответ, хотя иногда они не возвращают вообще никакого ответа. Чем дольше работают эти алгоритмы, тем выше вероятность того, что они вернут правильный ответ. Алгоритм Лас-Вегаса принимает случайное решение, а затем проверяет, приводит ли это решение к успеху. Программа, использующая алгоритм Лас-Вегаса, вызывает его раз за разом, пока он не достигнет результата. Если обозначить через success(aj) и failure(a;) время, необходимое для того, чтобы получить соответственно положительный или отрицательный ответ на входных данных, а через р(х) вероятность успешного завершения работы алгоритма, то мы приходим к равенству:

    time(x) = р(х) * success(a;) + (1 - р ( х ) ) * (failure(:r) + time(a;)).

    Это равенство означает, что в случае успеха затраченное время совпадает  с временем получения успешного  результата, а в случае неудачи  затраченное время равно сумме времени на достижение неудачного результата и еще на один вызов функции. Решая это уравнение относительно times(a;), мы получаем: 

        time(a;) = р(х) * success(a;) + (1 - р(х}} * failure(a;) + (1 — p(a;))time(a;).

          time(a;) — (1 — p(a;))time(a;) = p(x) * success(z) + (1 — p ( x ) ) * failure(a;).

        time(a;) — time(x) + р(х) * time(a;) = р(х) * success(x) +

    + (1 -р(х)} *failure(x).

    р(х) * time(ar) — р(х) * success(x) + (1 - р ( х ) ) * failure(o).

    time(x) = success(a;) + ((1 -p(x))/p(x)} * failure(a;). 

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

       Как такой подход работает  на практике? Обратимся к задаче  о расстановке восьми ферзей на шахматной доске так, чтобы они не били

    Друг  друга: 

      

    На  рис. изображено одно из решений этой задачи. Рекурсивный алгоритм ее решения помещает ферзя в первой клетке первой вертикали, а затем вызывает себя для того, чтобы поставить ферзя на вторую горизонталь. Если в какой-то момент алгоритму не удается найти положения для очередного ферзя на очередной горизонтали, то алгоритм возвращается на предыдущий шаг и пробует другое размещение ферзя на предыдущей строке.

    Имеется вероятностная альтернатива детерминированному рекурсивному алгоритму. Мы можем поочередно размещать ферзей на доске случайным образом на очередной свободной горизонтали доски. Отличие алгоритма Лас-Вегаса от стандартного рекурсивного алгоритма состоит в том, что при невозможности разместить очередного ферзя алгоритм попросту сдается и сообщает о неудаче. Рекурсивный же алгоритм пытается добиться положительного результата. Вот как выглядит алгоритм Лас-Вегаса для расстановки восьми ферзей:

      См. Приложение 2. 

    Посмотрим, как работает этот алгоритм. В цикле «repeat» мы проходим по всем восьми горизонталям доски. Для каждой из горизонталей мы последовательно просматриваем все ее клеточки и если клетка не атакована, то переменная «spotsPossible» увеличивается на единицу. Следующий оператор «if» выглядит несколько странно, но посмотрим, что происходит, если опустить первую горизонталь, на которой не атакована ни одна клетка. На первой вертикали функция «uniform»  генерирует случайное число между 1 и 1, т.е. 1, поэтому переменная «try» будет указывать на первую вертикаль. Во второй вертикали «uniform» генерирует число между 1 и 2, которое с 50%-ной вероятностью будет единицей и с 50%-ной вероятностью двойкой, поэтому вероятность того, что новым значением переменной «try» станет двойка, равна 50%. В третьей вертикали «uniform» генерирует число между 1 и 3; это число с вероятностью 33% будет 1, и также с вероятностью 33% значение «try» станет равно 3. Окончательно мы заключаем, что для каждой из свободных вертикалей вероятность быть опробованной на данном проходе равна 1/«spotsPossible». Затем все повторяется для остальных горизонталей. Такие действия продолжаются до тех пор пока либо значение «spotsPossible» не станет нулевым, ввиду отсутствия неатакованных клеток, либо переменная «rows» не примет значение 9, поскольку все ферзи будут расставлены. В первом случае алгоритм завершает свою работу и сообщает о неудачном исходе. Во втором проблема расстановки восьми ферзей решена, и алгоритм сообщает об удачном исходе.