Методы решения задачи по расстановке фигур на шахматной доске. Сущность рекуррентного алгоритма и составление его программы. Особенности алгоритма поиска с возвратом, статистический анализ эффективности и вероятность успеха по эвристическому алгоритму.
Аннотация к работе
Исходная формулировка: «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8?8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы. Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N?N клеток (при этом при 1<N<4 задача не имеет решения). Рассмотрим шахматную доску, клетки которой помечены с помощью системы координат следующим образом: Можно заметить, что два ферзя, которые находятся в клетках с координатами (x1, y1) и (x2, y2), будут бить друг друга если выполняется хотя бы одно из следующих равенств: 1) x1 = x2, то есть ферзи находятся на одной вертикали; Решая это уравнение относительно 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;).В работе рассмотрены несколько видов алгоритмов: рекуррентный, алгоритм с возвратом (алгоритм Лас-Вегаса) и эвристический. Анализируя данные алгоритмы на «доске» NXN нужно отметить, что их эффективность напрямую зависит от размера «доски». Но при увеличении размера увеличивается шанс, что алгоритм не вернет ответа, т.к. пройти придется большое количество действий (предельный размер «доски» для этого алгоритма 20х20).
Введение
Задача о восьми ферзях - широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8?8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
1. Решения задачи доски 8*8
1.1 Постановка задачи
Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8?8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы.
Конечная цель, поставленная перед решающим эту задачу, может формулироваться в нескольких вариантах: 1) Построить одно, любое решение задачи.
2) Аналитически доказать, что решение существует.
3) Определить количество решений.
4) Построить все возможные решения.
5) Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N?N клеток (при этом при 1<N<4 задача не имеет решения).
Мы же подробнее рассмотрим классический “шахматный” случай для доски 8*8. А позже адаптируем возможные алгоритмы на доску размером N*N.
1.2 Рекуррентный алгоритм решения
Рассмотрим шахматную доску, клетки которой помечены с помощью системы координат следующим образом:
Можно заметить, что два ферзя, которые находятся в клетках с координатами (x1, y1) и (x2, y2), будут бить друг друга если выполняется хотя бы одно из следующих равенств: 1) x1 = x2, то есть ферзи находятся на одной вертикали;
2) y1 = y2, то есть ферзи находятся на одной горизонтали;
3) x1 y1 = x2 y2, то есть ферзи находятся на одной диагонали, идущей снизу вверх слева направо. Это равенство верно только для приведенной нумерации клеток шахматной доски;
4) x1?y1 = x2?y2, то есть ферзи находятся на одной диагонали, идущей сверху вниз слева направо. Это равенство также верно только для приведенной нумерации клеток шахматной доски.
Очевидно, что все восемь ферзей находятся на разных вертикалях шахматной доски, иначе найдутся два из них, которые бьют друг друга. Поэтому нам нужно перебрать для каждого ферзя все возможные горизонтали, где он может встать и проверить, чтобы все ферзи не были под боем. Заведем массив q, индекс которого соответствует номеру ферзя, а значение qi указывает, на какой по счету горизонтали находится i-й ферзь.
Поскольку решение предполагает переборный алгоритм, заведем восемь переменных q1,...,q8, которые будут пробегать от 1 до 8 и устанавливать соответствующего ферзя на выбранную горизонталь. Например, если qi=4, это значит, что i-го ферзя необходимо поставить на 4-ю горизонталь. Зададим функцию boy(c), которая в качестве аргумента будет принимать номер ферзя и проверять, не бьют ли ферзя с номером «c» ферзи с 1-го до «c ? 1»-го. Эта функция возвращает значение «истина» в случае если «с»-го ферзя бьет хотя бы один ферзь и «ложь» в противном случае. Это делается следующим алгоритмом: Функция проверки «мирных» ферзей:
Алгоритм основной программы:
Данный алгоритм ищет все возможные решения задачи и выводит их число: 92. Этот алгоритм, реализованный на языке Pascal, показан в Приложении №1.
Интересно отметить, что эти 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.3 Алгоритмы Лас-Вегаса или алгоритм поиска с возвратом
Алгоритмы Лас-Вегаса никогда не возвращают неправильный ответ, хотя иногда они не возвращают вообще никакого ответа. Чем дольше работают эти алгоритмы, тем выше вероятность того, что они вернут правильный ответ. Алгоритм Лас-Вегаса принимает случайное решение, а затем проверяет, приводит ли это решение к успеху. Программа, использующая алгоритм Лас-Вегаса, вызывает его раз за разом, пока он не достигнет результата. Если обозначить через 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;).
Эта формула означает, что время выполнения зависит от времени получения успешного результата, безуспешного результата и вероятности каждого из этих исходов. Интересно, что при убывании вероятности р(х) успешного результата время выполнения все равно может быть невысоким, если скорость получения безуспешного результата возрастает. Поэтому эффективность можно повысить, если быстрее получать безуспешный результат.
Как такой подход работает на практике? Обратимся к задаче о расстановке восьми ферзей на шахматной доске так, чтобы они не били друг друга:
На рис. изображено одно из решений этой задачи. Рекурсивный алгоритм ее решения помещает ферзя в первой клетке первой вертикали, а затем вызывает себя для того, чтобы поставить ферзя на вторую горизонталь. Если в какой-то момент алгоритму не удается найти положения для очередного ферзя на очередной горизонтали, то алгоритм возвращается на предыдущий шаг и пробует другое размещение ферзя на предыдущей строке.
Имеется вероятностная альтернатива детерминированному рекурсивному алгоритму. Мы можем поочередно размещать ферзей на доске случайным образом на очередной свободной горизонтали доски. Отличие алгоритма Лас-Вегаса от стандартного рекурсивного алгоритма состоит в том, что при невозможности разместить очередного ферзя алгоритм попросту сдается и сообщает о неудаче. Рекурсивный же алгоритм пытается добиться положительного результата. Вот как выглядит алгоритм Лас-Вегаса для расстановки восьми ферзей: 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)
Посмотрим, как работает этот алгоритм. В цикле «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, поскольку все ферзи будут расставлены. В первом случае алгоритм завершает свою работу и сообщает о неудачном исходе. Во втором проблема расстановки восьми ферзей решена, и алгоритм сообщает об удачном исходе.
Полный статистический анализ алгоритма показывает, что вероятность успеха равна 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 расстановок (решений задачи) могут заполнить при наложении всю доску NXN только при тех 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.
Вывод
В работе рассмотрены несколько видов алгоритмов: рекуррентный, алгоритм с возвратом (алгоритм Лас-Вегаса) и эвристический.
Для «доски» 8х8 более эффективным является алгоритм с возвратом. Но он выводит лишь одно решение. Рекуррентный выводит все 92, но его работа может занимать больше времени. Эвристический так же находит лишь одно существующее решение.
Анализируя данные алгоритмы на «доске» NXN нужно отметить, что их эффективность напрямую зависит от размера «доски». При небольшом размере по эффективности преобладает Алгоритм Лас-Вегаса. Но при увеличении размера увеличивается шанс, что алгоритм не вернет ответа, т.к. пройти придется большое количество действий (предельный размер «доски» для этого алгоритма 20х20). Рекуррентный алгоритм находит все решения, независимо от размера доски, но при увеличении «доски», его эффективность так же снижается. Эвристический находит лишь одно существующее решение, независимо от размера «доски» (кроме случаев 2х2 и 3х3, там решений не существует). Но существует шанс, что найденное решение может быть ошибочно, и проверить его, при большом размере «доски» довольно проблематично.
Список литературы
1) М. Гарднер Математические досуги. - М.: Мир, 2000.
2) Дж. Макконел Основы современных алгоритмов. - М.: Техномир, 2004.
3) Е. Корнилов Программирование шахмат и других логических игр. - С.-П.: БХВ-Петербург, 2005.
4) А. Левитин Введение в анализ и разработку алгоритмов - М.: Вильямс, 2006.
5) Вирт Н. Алгоритмы и структура данных - С.-П.: Невский Диалект, 2005.
6) А. Ахо, Дж. Хопфорт, Дж. Ульман Построение и анализ вычислительных алгоритмов - М.: Мир, 1979.
7) Д. Кнут Искусство программирования т.1,2,3 - М.: 1968.
2) Заносим в список все четные числа от 2 до 8: 2,4,6,8.
3) Остаток не равен 3 или 9, оставляем список без изменений.
4) Заносим в список все нечетные числа от 2 до 8. Т.к. остаток равен 8, то переворачиваем пары соседних чисел: 2,4,6,8,1,3,5,7.
5) Т.к. остаток не равен 2, оставляем список без изменений.
6) Т.к. остаток не равен 3 или 9, оставляем список без изменений.
7) Размещаем ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем помещаем следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т.д..
Проверим расположение:
Как мы видим, данное расположение полностью удовлетворяет условиям задачи.