Нахождение всех комбинаций расстановки n ферзей на доске n X n
Государственный комитет
Российской Федерации
по высшему и среднеспециальному образованию
Красноярский Государственный Технический
Университет
Курсовая работа
по курсу
Математическая логика и теория алгоритмов
Выполнил студент гр. ВТ27-4
Попов А.В.
Проверила:
Пестунова
Т.М.
1998
Содержание.
1. Постановка
задачи (стр.3).
2. Построение
модели (стр.3).
3. Описание
алгоритма (стр.4).
4. Доказательство
правильности алгоритма (стр.7).
5. Блок-схема
алгоритма (стр.8).
6. Описание
переменных и программа (стр.9).
7. Расчёт
вычислительной сложности (стр.11).
8. Тестирование
(стр.11).
9. Список
литературы (стр.12).
Постановка
задачи.
Перечислить
все способы расстановки n ферзей на шахматной доске n на n, при которых они не
бьют друг друга.
Построение модели.
Очевидно, на каждой из n
горизонталей должно стоять по ферзю. Будем называть k-позицией (для k = 0,
1,...,n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи
могут бить друг друга). Нарисуем "дерево позиций": его корнем будет
единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в
(k+1)-позиции. Эти n позиций отличаются положением ферзя на (k+1)-ой
горизонтали. Будем считать, что расположение их на рисунке соответствует
положению этого ферзя: левее та позиция, в которой ферзь расположен левее.
Дерево
позиций для n = 2
Данное дерево представлено только для наглядности и
простоты представления для n=2.
Среди позиций этого дерева нам
надо отобрать те n-позиции, в которых ферзи не бьют друг друга. Программа будет
"обходить дерево" и искать их. Чтобы не делать лишней работы,
заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших
ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение
дерева в этом направлении.
Точнее, назовем k-позицию
допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга.
Наша программа будет рассматривать только допустимые позиции.
Описание алгоритма.
Разобьем
задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева
допустимых позиций.
Сформулируем задачу обхода произвольного дерева.
Будем считать, что у нас имеется Робот, который в каждый момент находится в
одной из вершин дерева. Он умеет выполнять команды:
вверх_налево (идти по самой левой из
выходящих вверх стрелок)
вправо (перейти в соседнюю справа
вершину)
вниз
(спуститься
вниз на один уровень)
вверх_налево
вправо
вниз
и проверки, соответствующие возможности выполнить каждую
из команд, называемые "есть_сверху", "есть_справа",
"есть_снизу" (последняя истинна всюду, кроме корня). Обратите
внимание, что команда "вправо" позволяет перейти лишь к "родному
брату", но не к "двоюродному".
Будем считать, что у Робота есть
команда "обработать" и что его задача - обработать все листья
(вершины, из которых нет стрелок вверх, то есть где условие
"есть_сверху" ложно). Для нашей шахматной задачи команде обработать
будет соответствовать проверка и печать позиции ферзей.
Доказательство правильности
приводимой далее программы использует такие определения. Пусть фиксировано
положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются
на три категории: над Роботом, левее Робота и правее Робота. (Путь из корня в
лист может проходить через вершину с Роботом, сворачивать влево, не доходя до
нее и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие
"обработаны все листья левее Робота", а через (ОЛН) - условие
"обработаны все листья левее и над Роботом".
Нам понадобится такая процедура:
procedure вверх_до_упора_и_обработать
{дано: (ОЛ), надо: (ОЛН)}
begin
while есть_сверху do begin
вверх_налево
end
{ОЛ, Робот в листе}
обработать;
{ОЛН}
end;
Основной алгоритм:
дано: Робот в корне, листья не обработаны
надо: Робот в корне, листья обработаны
{ОЛ}
вверх_до_упора_и_обработать
{инвариант: ОЛН}
while есть_снизу do begin
if есть_справа then begin {ОЛН, есть справа}
вправо;
{ОЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
end;
end;
{ОЛН, Робот в корне => все листья обработаны}
Осталось воспользоваться
следующими свойствами команд Робота (сверху записаны условия, в которых
выполняется команда, снизу - утверждения о результате ее выполнения):
(1)
{ОЛ,
не есть_сверху} обработать {ОЛН}
(2)
{ОЛ}
вверх_налево {ОЛ}
(3)
{есть_справа,
ОЛН} вправо {ОЛ}
(4)
{не
есть_справа, ОЛН} вниз{ОЛН}
Теперь решим задачу об обходе
дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).
Решение. Пусть x - некоторая
вершина. Тогда любая вершина y относится к одной из четырех категорий.
Рассмотрим путь из корня в y. Он может:
а) быть частью пути из корня в x
(y ниже x);
б) свернуть налево с пути в x (y
левее x);
в) пройти через x (y над x);
г) свернуть направо с пути в x
(y правее x);
В частности, сама вершина x
относится к категории в). Условия теперь будут такими:
(ОНЛ) обработаны все вершины
ниже и левее;
(ОНЛН) обработаны все вершины
ниже, левее и над.
Вот как будет выглядеть программа:
procedure вверх_до_упора_и_обработать
{дано: (ОНЛ), надо: (ОНЛН)}
begin
{инвариант: ОНЛ}
while есть_сверху do begin
обработать
вверх_налево
end
{ОНЛ, Робот в листе}
обработать;
{ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
if есть_справа then begin {ОНЛН, есть справа}
вправо;
{ОНЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
end;
end;
{ОНЛН, Робот в корне => все вершины обработаны}
Приведенная только что программа обрабатывает
вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы
каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а
другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу:
Под "обработано ниже и
левее" будем понимать "ниже обработано по разу, слева обработано
полностью (листья по разу, остальные по два)". Под "обработано ниже,
левее и над" будем понимать "ниже обработано по разу, левее и над -
полностью".
Программа будет такой:
procedure вверх_до_упора_и_обработать
{дано: (ОНЛ), надо: (ОНЛН)}
begin
{инвариант: ОНЛ}
while есть_сверху do begin
обработать
вверх_налево
end
{ОНЛ, Робот в листе}
обработать;
{ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
if есть_справа then begin {ОНЛН, есть справа}
вправо;
{ОНЛ}
вверх_до_упора_и_обработать;
end else begin
{ОЛН, не есть_справа, есть_снизу}
вниз;
обработать;
end;
end;
{ОНЛН, Робот в корне => все вершины обработаны
полностью}
Доказательство правильности
алгоритма.
Докажем, что приведенная программа
завершает работу (на любом конечном дереве).
Доказательство. Процедура вверх_налево
завершает работу (высота Робота не может увеличиваться бесконечно). Если
программа работает бесконечно, то, поскольку листья не обрабатываются повторно,
начиная с некоторого момента ни один лист не обрабатывается. А это возможно,
только если Робот все время спускается вниз. Противоречие.
Блок-схема алгоритма.
Описание переменных и программа.
Теперь реализуем операции с
деревом позиций. Позицию будем представлять с помощью переменной k: 0..n
(число ферзей) и массива c: array [1..n] of 1..n (c [i] - координаты ферзя на
i-ой горизонтали; при i > k значение c [i] роли не играет). Предполагается,
что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг
друга).
program queens;
const n = ...;
var k: 0..n;
c: array [1..n] of 1..n;
procedure begin_work; {начать работу}
begin
k := 0;
end;
function danger: boolean; {верхний ферзь под боем}
var b: boolean;
i: integer;
begin
if k <= 1 then begin
danger := false;
end else begin
b := false; i := 1;
while i <> k do begin
b := b or (c[i]=c[k]) {вертикаль}
or (abs(c[i]-c[k])=abs(i-k)); {диагональ}
i := i+ 1;
end;
danger := b;
end;
end;
function is_up: boolean {есть_сверху}
begin
is_up := (k < n) and not danger;
end;
function is_right: boolean {есть_справа}
begin
is_right := (k > 0) and (c[k] < n);
end;
{возможна ошибка: при k=0 не определено c[k]}
function is_down: boolean {есть_снизу}
begin
is_up := (k > 0);
end;
procedure up; {вверх_налево}
begin {k < n}
k := k + 1;
c [k] := 1;
end;
procedure right; {вправо}
begin {k > 0, c[k] < n}
c [k] := c [k] + 1;
end;
procedure down; {вниз}
begin {k > 0}
k := k - 1;
end;
procedure work; {обработать}
var i: integer;
begin
if (k = n) and not danger then begin
for i := 1 to n do begin
write ('<', i, ',' , c[i], '> ');
end;
writeln;
end;
end;
procedure UW; {вверх_до_упора_и_обработать}
begin
while is_up do begin
up;
end
work;
end;
begin
begin_work;
UW;
while is_down do begin
if is_right then begin
right;
UW;
end else begin
down;
end;
end.
Расчёт вычислительной сложности.
Емкостная сложность:
В программе используется одномерный
массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество
пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к нему, то
временная сложность T(n) = n0+n1+n2+n3+…+nn
.
Но в случае, когда каждая вершина проверяется, временная сложность T(n) =
o(n0+n1+n2+n3+…+nn). И
это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже
статистических данных:
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Общее кол-во листьев
|
2
|
7
|
40
|
341
|
3906
|
55987
|
960800
|
Кол-во вершин построенного дерева.
|
2
|
3
|
4
|
17
|
54
|
153
|
552
|
Время построения(сек)
|
<0.01
|
<0.01
|
<0.01
|
<0.01
|
<0.01
|
<0.01
|
<0.01
|
|
8
|
9
|
10
|
11
|
12
|
13
|
Общее кол-во листьев
|
|
|
|
|
|
|
Кол-во вершин построенного дерева.
|
2057
|
8394
|
35539
|
166926
|
856189
|
4674890
|
Время построения(сек)
|
<0.01
|
0.21
|
1.20
|
6.48
|
37.12
|
231.29
Построенная по описанному алгоритму
программа при различных n выдаёт следующие данные:
n=4
<1,2><2,4><3,1><4,3>
<1,3><2,1><3,4><4,2>
Т.е. количество расстановок равно
2. Ниже приведена таблица зависимости от n количества решений (R).
n =
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
R=
|
1
|
0
|
0
|
2
|
10
|
4
|
40
|
92
|
352
|
724
|
2680
|
14200
|
73712
|
Cписок литературы.
1)
Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера.
– М.: Энергоатомиздат, 1988.
2)
Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука,
1984.
3)
Основной алгоритм находился на BBS “Master of Univercity” в файле
shen.rar в файловой области “Bardak” (тел. 43-27-03;
время работы 21.00 – 7.00; FTN адрес – 2:5090/58).
Похожие работы на - Нахождение всех комбинаций расстановки n ферзей на доске n X n
|