Программное решение задачи о 8 ферзях

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Факультет ВИС

КАФЕДРА ТЕХНИЧЕСКИХ И ИНФОРМАЦИОННЫХ СРЕДСТВ СИСТЕМ УПРАВЛЕНИЯ

Курсовая работа

«Программное решение задачи о 8 ферзях»

Выполнил: студент группы ВАИ 03-07

Титов Андрей Владимирович

МОСКВА 2008



Содержание

1. Введение

2. Календарный план

3. Теоретическая часть

3.1 Поиск алгоритма

3.2 Проблемы хранения результатов

3.3 Графического отображения

4. Практическая часть

Заключение

Список используемой литературы



1. Введение

Умение программировать является очень важным для изучаемой специальности. Важно не только знание изучаемых языков программирования, но и правильное использование их возможностей. При создании программ необходимо учитывать особенности их реализации на разных языках. Так же необходимо учитывать время которое будет затрачено на воплощение проекта в жизнь. От хорошего специалиста требуется не только знания языков программирование, но и знание оптимальных алгоритмических решений. Одним из таких решений является реализованный в данной работе алгоритм. Выбор оптимального алгоритма влияет на скорость выполнения и на затраты ресурсов компьютера. Не мало важным фактором является знание операционной системы для которой создается программа.

Одной из целей этой работы является поиск оптимального алгоритма решения задачи о 8 ферзях, и его реализация в ОС Windows. Выбор языка программирования пал на Delphi, благодаря простоте создания в нем проектов. Проведенная предварительно оценка необходимых затрат ресурсов для реализации данной программы с учетом конкретного опыта осуществления прикладных задач в различных языках программирования обосновывает данный выбор на взгляд автора.



2. Календарный план

№	Дата окончания планируемых работ	Перечень разрабатываемых вопросов	Фактическая дата Окончания работ
1	23.04.2008	Подбор литературы	23.04.2008
2	29.04.2008	Изучение материала	29.04.2008
3	5.05.2008	Написание программы	25.05.2008
4	7.05.2008	Написание теоретической части работы	25.05.2008



3.Теоретическая часть

3.1 Поиск алгоритма

Задача состоит в том, чтобы сделать программу, генерирующую все конфигурации восьми ферзей на шахматной доске из 8x8 полей, так, чтобы ни один ферзь не мог взять никакого другого ферзя. Это значит, что в искомых конфигурациях никакие два ферзя не могут находиться на одной горизонтали, на одной вертикали или на одной диагонали. У нас нет оператора, генерирующего все эти конфигурации: именно этот оператор мы и должны получить. Ныне (весьма общий!) подход для решения такой проблемы состоит в следующем. Назовем искомое множество конфигураций множеством A; будем искать множество конфигураций B со следующими свойствами:

1. множество A является подмножеством множества B; мы можем получить оператор, генерирующий все элементы множества B.

2. если задан элемент из множества B, то нетрудно установить, принадлежит ли он также множеству A;

3. мы можем сделать оператор, генерирующий все элементы множества B.

При помощи генератора (3) элементов множества B можно генерировать по очереди все элементы из B; к ним будет применяться логический критерий (2), который решает, должны ли эти элементы пропускаться или передаваться дальше, генерируя таким образом элементы множества A. Благодаря условию (1) этот алгоритм выработает все элементы множества A.

Следует сделать три замечания:

1. Если все наши рассуждения имеют смысл, то множество B не идентично множеству A, и, поскольку оно должно содержать A в качестве подмножества, оно должно быть больше. Лучше однако, выбрать множество B "как можно меньшим": чем больше элементов будет в нем, тем больше придется отбрасывать элементов в соответствии с критерием (2).

2. Мы должны искать такой критерий принятия решения, который «дешев» в применении или, по крайней мере, «дешевым» (в среднем) должно быть установление того, что некий элемент из B не принадлежит множеству A.

3. Предполагается, что генерировать элементы множества B легче, чем непосредственно генерировать элементы множества A. Если, тем не менее, генерация элементов множества B все же представляет трудности, то мы пересмотрим наш шаблон рассуждений, повторно применим тот же прием и будем искать еще большее множество конфигураций C, содержащее B как подмножество и т. д.

Выше мы наметили весьма общий подход, применимый для многих очень различных задач. Когда мы сталкиваемся с конкретной задачей, т. е. с конкретным искомым множеством A, то, конечно, проблема состоит в выборе подходящего множества B. Оптимист мог бы подумать, что это легкое дело, так как возможен следующий прием. Мы перечисляем все взаимно независимые условия, которым должны удовлетворять наши элементы множества B, и затем отбрасываем одно из этих условий. Иногда этот прием срабатывает, но как общий прием, он слишком наивен; если мы захотим увидеть его недостатки, нужно только вслепую применить его к задаче восьми ферзей. Мы можем охарактеризовать наши решения двумя условиями:

1. на доске есть восемь ферзей

2. никакие два ферзя не могут взять друг друга.

Отбрасывание любого из этих условий дает для множества B следующие альтернативы

B1: все такие конфигурации из N ферзей на доске, в которых никакие два ферзя не могут взять друг друга

B2: все конфигурации из 8 ферзей на доске.

Ну, хорошо, на этом этапе нашего рассмотрения, находясь в некотором «недоумении», мы заботимся не столько об эффективности нашей конечной программы, сколько об эффективности нашего процесса мышления! Так что, если мы решаем сделать список свойств решений в надежде найти ключ, то это, скорее, обходной, мы не должны затрачивать слишком много мыслительной энергии на такой поиск, другими словами: для начала мы должны ограничиться его очевидными свойствами.

a) Никакая горизонталь не может содержать более одного ферзя; нужно разместить 8 ферзей, и доска содержит 8 горизонталей. Как результат, мы можем заключить, что каждая горизонталь будет содержать ровно одного ферзя.

b) Аналогично мы заключаем, что каждая вертикаль будет содержать ровно одного ферзя.

c) Есть 15 "восходящих" диагоналей, каждая из которых содержит не более одного ферзя, т. е. 8 восходящих диагоналей содержат ровно по одному ферзю, 7 восходящих диагоналей являются пустыми.

d) Аналогично заключаем, что 8 нисходящих диагоналей содержат ровно по одному ферзю, а 7 являются пустыми.

e) Если задана какая-то непустая конфигурация ферзей, в которой никакие два ферзя не могут взять друг друга, то удаление любого одного из этих ферзей приведет к появлению конфигурации, сохраняющей это свойство.

Последнее свойство является очень важным. В нашей прежней терминологии это свойство кое-что говорит нам о любой непустой конфигурации из множества B1. И наоборот, оно говорит нам, что любая непустая конфигурация из множества B1 может быть сгенерирована (N разными способами!) расширением конфигурации из B1 с N-1 ферзями еще одним ферзем. Если мы начинаем с какого-то решения (которое является конфигурацией восьми ферзей из множества B1) и удаляем одного ферзя, то мы получаем конфигурацию семи ферзей из множества B1; удаление еще одного ферзя приведет снова к конфигурации из множества B1, и мы можем продолжать этот процесс, пока шахматная доска не опустеет. Мы забраковали B1 из-за того, что оно слишком большое, но, может быть, мы сможем найти подходящее его подмножество, такое, что каждая непустая конфигурация в нем окажется одно-ферзевым расширением только одной конфигурации из этого подмножества. Это "свойство расширения" подразумевает, что мы собираемся рассматривать конфигурации, в которых меньше 8 ферзей, и что мы хотели бы формировать новые конфигурации, добавляя по одному ферзю к имеющимся конфигурациям - по-видимому, это сравнительно простая операция. Итак, мы сосредоточим наше внимание непосредственно на генерации элементов (все еще таинственного) множества B. В каком порядке это делать? И тут опять возникает вопрос, которому до сих пор мы не уделяли ни малейшего внимания: в каком порядке мы собираемся генерировать решения, т. е. элементы множества A? Можно ли сделать разумное предположение на этот счет в надежде, что оно поможет нам распутать клубок?

Но до этого нам нужно спросить себя: как мы будем характеризовать решения, когда они у нас будут? Чтобы охарактеризовать решение, мы должны задать позиции 8 ферзей. Ферзи сами по себе являются неупорядоченными, но для горизонталей и вертикалей это не так: мы можем предположить, что они нумеруются от 0 до 7. Согласно свойству а), которое говорит нам, что каждая горизонталь содержит ровно одного ферзя, мы можем упорядочить ферзей в соответствии с номерами занимаемых ими горизонталей. Тогда каждая конфигурация из 8 ферзей может быть задана значением integer array x[0:7], где x[i] - номер вертикали, занимаемой ферзем в i-й горизонтали.

Каждое решение тогда представляет собой "8-цифорвое слово" (х[0]... х[7]), единственным имеющим смысл порядком генерации этих слов является, я думаю, алфавитный порядок.

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

Сначала мы должны сгенерировать все решения с х[0] = 0, затем решения с х[0] = 1 и т. д.; из решений с фиксированным значением х[0] = 0 (должны сначала генерироваться те, у которых х[1] = 0 если они есть), затем те, у которых х[1] = 1 (если есть), затем те, у которых х[1] = 2 (если есть) и т. д. Другими словами, ферзь с горизонтали 0 помещается на вертикаль 0 - скажем, в клетку в верхнем левом углу доски - и остается там до тех пор, пока не все элементы A (и B) с ферзем 0 в этой позиции не будут сгенерированы, и только затем он перемещается на одну клетку вправо, в следующую вертикаль. Для каждой позиции ферзя 0 ферзь 1 будет перемещаться слева направо в горизонтали 1 - перескакивая через клетки, которые находятся под угрозой ферзя 0; - для каждой комбинированной позиции первых двух ферзей ферзь 2 перемещается по горизонтали 2 слева направо, пропуская все клетки, находящиеся под угрозой предыдущих ферзей, и т. д.

Но теперь мы уже нашли множество B! Оно несомненно является подмножеством множества B1: множество B состоит из всех конфигураций, в которых по одному ферзю в каждой из первых N горизонталей, причем никакие два ферзя не могут взять друг друга.

Установив наш вариант множества B, мы обнаруживаем, что столкнулись с задачей генерации его элементов в алфавитном порядке. Мы попытаемся проделать это при посредстве оператора "ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B", что приведет к программе следующей структуры:

ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ;

repeat ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ В;

if N = 8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ

until В ИСЧЕРПАНО

но она не очень удобна для нас по двум причинам.

Во-первых, мы не имеем готового критерия распознавания последнего элемента из B, если мы его встретим, и, по всей вероятности, мы должны обобщить оператор "ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B" так, чтобы он вырабатывал индикацию порождал указание "B ИСЧЕРПАНО", когда он применяется к последнему "истинному" элементу множества B. Во-вторых, не вполне очевидно, как реализовать оператор "ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B": число ферзей на доске может оставаться неизменным, может уменьшаться и может увеличиваться.

Итак, эта структура не слишком привлекательна. Что тут можно сделать? До тех пор пока мы рассматриваем последовательность конфигураций из множества B как единую и однородную, не разделяем ее на ряд подпоследовательностей, соответствующая программная структура будет оставаться единственным циклом, как в только что очерченной программе. Поскольку мы ищем альтернативную программную структуру программы, то следовательно мы должны спросить себя: "Как мы можем сгруппировать последовательности конфигураций из множества B в ряд подпоследовательностей?"

Понимая, что последовательность конфигураций из множества B должна генерироваться в алфавитном порядке, и думая об главном подразделении в словаре - а именно по первой букве - первое группирование является очевидным: по позиции ферзя 0.

Генерация всех элементов множества B - если мы забудем на время о необходимости печатать элементы, которые принадлежат также подмножеству A, - представляется в первом приближении такой

h:= 0;

repeat УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H;

ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ФЕРЗЕМ 0;

ПЕРЕМЕСТИТЬ ФЕРЗЯ;

h:= h + 1

until h = 8

где операторы "УСТАНОВИТЬ ФЕРЗЯ" и "ПЕРЕМЕСТИТЬ ФЕРЗЯ" относятся к нулевой горизонтали, т.е., к первой свободной горизонтали или последней занятой соответственно.

Но теперь вопрос повторяется: как мы сгруппируем все конфигурации с фиксированным положением ферзя 0? Мы уже получили ответ: в порядке возрастания номеров вертикалей позиции ферзя 1, т. е.

H2:= 0;

repeat if ПОЛЕ H2 СВОБОДНО do

begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ H2;

ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМИ ПЕРВЫМИ ДВУМЯ ФЕРЗЯМИ;

ПЕРЕМЕСТИТЬ ФЕРЗЯ

end;

H2:= H2 + 1

until H2 = 8

Для "ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ C ФИКСИРОВАННЫМИ ПЕРВЫМИ ДВУМЯ ФЕРЗЯМИ" можно написать аналогичный фрагмент программы, и т. д.: вкладывая эти их один в другой, мы получили бы корректную программу с восемью вложенными циклами, но они будут очень-очень похожими. Это имеет два недостатка:

1. требуется слишком много писанины

2. дается программное решение нашей задачи для шахматной доски из 8 * 8 клеток, но решение той же головоломки для доски из, скажем, 10x10 клеток, потребовало бы новой (еще более длинной) программы. Мы захотим обойти это, используя схожесть циклов.

Тогда мы должны ответить на два вопроса:

1. можем ли мы сделать циклы совершенно идентичными?

2. можем ли мы получить выгоду из их схожести?

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

if ПОЛЕ [0, h] СВОБОДНО do

Самый внутренний цикл отличается тем, что коль скоро на доске должны быть размещены 8 ферзей, то нет смысла генерировать все конфигурации с фиксированными позициями этих ферзей, так как доска уже заполнена. Вместо этого конфигурация должна быть отпечатана, поскольку мы нашли элемент множества B, который также является элементом множества A. Мы можем отобразить самый внутренний цикл и семь охватывающих его циклов друг на друга, заменив строку "ГЕНЕРИРОВАТЬ" на строку

if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ

else ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ, РАСШИРЯЮЩИЕ ИМЕЮЩУЮСЯ

Теперь единственное различие между восемью циклами состоит в том, что каждый цикл имеет "свое собственное h". Когда мы достигли этого этапа, мы можем получить утвердительный ответ на второй вопрос. Последовательное прохождение через восемь вложенных циклов может выполняться с помощью рекурсивной процедуры, скажем, "генерировать", описывающей однократное выполнение цикла. При ее использовании вся программа сводится к виду

ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ;

генерировать

где процедура "генерировать" определяется рекурсивно следующим образом:

procedure генерировать;

begin integer h;

h:= 0;

repeat if КЛЕТКА H СВОБОДНА do

begin УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H;

if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ

else генерировать;

ПЕРЕМЕСТИТЬ ФЕРЗЯ

end

h:= h + 1

until h = 8

end

Каждая активизация "генерировать" вводит свою отдельную локальную переменную h, заменяя тем самым переменные H2, H3,..., которые потребовались бы нам при написании восьми циклов, вложенных друг в друга. КЛЕТКА H СВОБОДНА и УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H опять ссылаются на первую свободную горизонталь, операция ПЕРЕМЕСТИТЬ ФЕРЗЯ - на последнюю занятую горизонталь.

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

integer array x [0:7]

задающий по порядку номера вертикалей, занимаемых ферзями. Нам нужно отдельное соглашение о представлении номеров ферзей на доске. Давайте введем integer n, такое, что

N = число ферзей на доске

x[i] = при 0 < i n: номер вертикали, занимаемой ферзем из i-ой горизонтали

Сочетание массива x и скаляра n является достаточным для фиксации любой конфигурации из множества B, причем это будут только конфигурации с шахматной доски. Следовательно, у нас нет логической необходимости в дополнительных переменных, хотя мы и введем еще несколько, поскольку с практической точки зрения мы можем хорошо их использовать

Проблема состоит в том, что c с только вышеприведенным материалом анализ того, находится ли под угрозой данная клетка, оказывается дорогостоящим и требует значительных затрат времени. Здесь мы можем применить стандартный прием, именуемый "расплата объемом памяти за время вычислений". Образец этого приема следующий.

В его простейшей форм мы имеем дело с вычислением, которому регулярно требуется значение функции FUN(arg), где "FUN" - заданная вычислимая функция, определенная на текущих значениях одной или нескольких переменных, которые все вместе названы "arg". В версии программы 1 хранится только значение arg, и FUN(arg) вычисляется всякий раз, когда это нужно. В версии программы 2 вводится дополнительная переменная, скажем, "fun", которая служит для сохранения значения "FUN(arg)", связанного с текущим значением "arg".

В версии 1 будет

arg:=... (т.е., присваивание значения)

а в версии 2 (более эффективной)

arg:=...; fun:= FUN(arg),

таким образом поддерживается справедливость отношения

fun:= FUN(arg).

Введение этого избыточного дополнительного ингредиента является одним из самых мощных способов для программиста повышения эффективности программы. Конечно же, мы должны применять его творчески!

Очень часто ситуация не так проста, как это, и теперь мы приходим ко второй причине для введения такой переменной, как "fun". Часто бывает очень неудобно вычислять FUN(arg) "из ничего" для произвольных значений arg, тогда как гораздо легче вычислить, как изменится значение FUN(arg) при изменении значения arg. В таком случае модификация значения fun более связана с природой функциональной зависимости и историей переменной arg, что подразумевает

arg:=...; fun:= FUN(arg).

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

Как это сделать? Можно, скажем, представить себе булевский массив из 8 х 8 элементов, указывающих для каждой клетки, свободна ли она. Если мы делаем это для всей доски, то добавление ферзя может повлиять на 29 клеток; удаление ферзя, однако, является мучительным процессом, поскольку ниоткуда не следует, что клетки, которым не больше угрожает он, на самом деле свободны: они могут находиться под угрозой других ферзей. Против этого есть стандартное средство, а именно, связывание с каждой клеткой не булевской переменной, а целочисленного счетчика, подсчитывающего число ферзей, угрожающих этой клетке. Добавление ферзя означает увеличение на 1 значений до 29 счетчиков, удаление ферзя означает уменьшение на "1" значений до 29 счетчиков, и клетка является свободной, когда ее счетчик равен нулю. Мы можем действовать таким способом, но возникает вопрос, не переусердствуем ли мы: 29 модификаций - это довольно много.

Каждая клетка, состоянием (свободна/несвободна) которой мы интересуемся, держит под прицелом горизонталь (которая свободна по определению, так что нам не нужно об этом заботиться), одну из 8 вертикалей (которая вся должна быть пустой), одну из 15 восходящих диагоналей (которая вся должна быть пустой) и одна из 15 нисходящих диагоналей (которая вся должна быть пустой). Это предполагает, что нам нужно отслеживать:

1.свободные вертикали

2.свободные восходящие диагонали

3.свободные нисходящие диагонали.

Поскольку каждая вертикаль или диагональ попадает под прицел только один раз, нам не нужны счетчики для каждой, а достаточно и булевской переменной. Для вертикалей мы вводим

boolean array col [0:7]

где "col[i]" означает, что i-я вертикаль свободна.

Как мы идентифицируем диагонали? На самом деле по каждой восходящей диагонали разность между номером горизонтали и номером вертикали является постоянной; а по нисходящей диагонали остается постоянной их сумма. Как результат, разность и сумма соответственно являются простейшими индексами, при помощи которых можно различать диагонали, и поэтому, и мы, следовательно, вводим

boolean array up [-7:+7], down [0:14], чтобы отслеживать свободные диагонали.

Вопрос о том, является ли поле свободным, становится таким:

col[h] and up[n-h] and down [n+h]

а установка или удаление ферзя сводятся к модификации трех булевских элементов, по одному в каждом массиве.

Без дополнительных переменных ПЕРЕМЕСТИТЬ ФЕРЗЯ содержала бы только "n:= n - 1", теперь же мы захотим знать также и номер ее вертикали, т.е., мы заменяем ее на ПЕРЕМЕСТИТЬ ФЕРЗЯ ИЗ КЛЕТКИ H. В результирующей программе вводится переменная "k"для общих вычислительных надобностей, операторы и выражения снабжаются пояснительных меток.

Этим завершается рассмотрение нашей задачи; программа генерирует 92 конфигурации.

begin integer n, k; integer array x[0:7]; boolean array col[0:7], up[-7:+7], down[0:14];

procedure генерировать;

begin integer h; h:= 0;

repeat if КЛЕТКА H СВОБОДНА: (col[h] and up[n-h] and down[n+h]) do

begin УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H:

x[n]:= h; col[h]:= false; up[n-h]:= false; down[n+h]:= false; n:= n + l;

if ДОСКА ЗАПОЛНЕНА: (n = 8) then

begin ПЕЧАТАТЬ КОНФИГУРАЦИЮ:

k:= 0; repeat print(x[k]); k:= k + 1 until k = 8; newline

end

else генерировать;

ПЕРЕМЕСТИТЬ ФЕРЗЯ С ПОЛЯ H:

n:=n-1;

down[n+h]:= true; up[n-h]:= true; col[h]:= true

end;

h:= h + l

until h=8

end;

ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ:

n:= 0;

k:= 0; repeat col[k]:= true; k:= k + l until k = 8;

k:= 0; repeat up[k-7]:= true; down[k]:= true; k:= k + l until k = 15;

генерировать

end

3.2 Проблемы хранения результата

программа хранение шахматный алгоритм

Хотя выше мы разобрали алгоритм который решает нашу задачу, нам нужно как то сохранить все 92 решения. Для того чтобы потом можно было отобразить на выбор любое из решений, наверное целесообразней хранить координаты одного решения в одной переменной Fr. Итого мы получаем 92 переменных типа integer. Остается только создать оператор который будет заполнять нашу переменную Fr, используя для этого значения массива X[1..8]. У нас есть 8 элементов массива X и в каждом может быть значения от 1 до 8, и нам нужно эти 8 элементов представить в виде одной переменной. Поскольку у нас 8 элементов которые могут принимать значения от 1 до 8, попробуем взять восьмизначное десятичное число в котором порядковый номер цифр будет соответствовать номеру элементов массива X, а числа соответственно значениям элементов массива X. Пронумеруем цифры в нашем числе слева на право. Некоторые характеристики соответствующие переменной Fr приведены в таблице.

Значение числа	1..8	1..8	1..8	1..8	1..8	1..8	1..8	1..8
Порядковый Номер(разряд)	1	2	3	4	5	6	7	8
Элем. массива	Х[1]	X[2]	X[3]	X[4]	X[5]	X[6]	X[7]	X[8]
Весовой коэффициент элемента	10^8	10^7	10^6	10^5	10^4	10^3	10^2	10^1



Из этого вытекает что наша переменная Fr может равняться числам от 11 111 111 до 88 888 888. В которых порядковый номер цифры отвечает за номер горизонтали, а сама цифра за позицию по вертикали. Определившись с методом, можно приступить к программной реализации.

Одним из возможных решений является алгоритм представленный ниже.

Таким образом для того чтобы получить значение i-того разряда искомого числа необходимо значение Х [i] * на его весовой коэффициент.

Нам потребуется 1 служебная переменная z которая будет отвечать за вес нашего числа. Изначально её приравняем к 100 000 000, создадим цикл в котором будем её делить на 10, уменьшая тем самым вес числа. Поскольку мы будем использовать номер элемента массива x в качестве номера весового коэффициента числа, то мы будем последовательно к Fr прибавлять значение x умноженное на z. В итоге за шаг нашего цикла z уменьшится на 1 порядок, и поменяется номер элемента x, значение которого умноженное на z прибавится к Fr,которое в начале равно 0. При последнем выполнении цикла мы получим в Fr восьмизначное число, отвечающие нужным свойствам. Наш цикл будет примерно таким

Z=100 000 000

For I:=1 to 8 do

Z:= z/10

fr:= fr+x[I]*z;

Так мы решили задачу хранения результатов, но остается теперь решить как восьмизначное число преобразовать обратно в массив x[1..8]. Для этого нам потребуется один цикл и две служебных переменных, одна z равная 10 000 000 и z1 равная Fr. Z1 нам понадобится для хранения промежуточного результата. При проходе цикла элементу массива x будет приравниваться результат операции целочисленного деления z1 на z, затем из z1 вычитается произведение элемента массива x и z, тем самым уменьшая z1 на 1 порядок. И последней командой цикла является целочисленное деление z на 10, за счет этого z уменьшается на 1 порядок. В конце выполнения всех шагов цикла мы заполняем массив x [1..8] соответствующими значениями.

Z=10 000 000

Z1=Fr

For I:=1 to 8 do

x[i]:= z1 div z

z1:= z1- x[i]*z

z:=z div 10;

3.3 Графическое отображение

Разобрав выше почти все аспекты написания нашего проекта, остается только уделить внимание его графической части.Delphi изначально предлагает готовое «окно» и библиотеку компонентов, что позволяет программисту уделить основное время на написание кода программы, а не её графической части. Но от того как будет выглядеть графическая часть программы, зависит и отношение к ней, «по одежке встречают, а по уму провожают». Поэтому мы в этом проекте воспользовались стандартным окном и некоторыми компонентами, но не забыли добавить и не стандартных решений. На основном окне программы мы разместили стандартную кнопку и компонент ListBox позволяющий отображать список строк и выбирать из них нужную. А для графического отображения найденных расстановок, мы нарисовали шахматную доску. Кнопка в нашем окне служит для запуска расчетов, ListBox для вывода найденных координат и выбора какой-либо из них для графического отображения на доске. Доска состоит из 64 заполненных разными цветами квадратов, и 2 пустых квадратов, которые обрамляют наше шахматное поле. Как и в настоящих шахматах сбоку клеток выведены их координаты. Процедура рисования доски принимает две переменные xn,yn, координаты угла доски. Для отображения ферзей используются два массива в которых хранится координаты клеток. При нажатие на кнопку, listbox заполняется 92 комбинациями, при выборе которых на доске отображается расположение ферзей.



4. Практическая часть

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, jpeg, StdCtrls, Buttons;

type

TForm1 = class(TForm)

List: TListBox;

Label1: TLabel;

Button6: TButton;

Text2: TLabel;

procedure FormPaint(Sender: TObject);

procedure Button6Click(Sender: TObject);

procedure ListClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

n,i: integer; //для gen обозначение вертикали

xn: integer = 200; // координаты доски

yn: integer = 60;

x: array [0..8] of integer; //ферзи

col: array [0..7] of boolean; //горизонтали

up: array [-7..7] of boolean; //восходящие диагонали

down: array [0..14] of boolean; //нисходящие диагонали

fr:array [0..91] of integer;//для хранения координат ферзей

mas: array[1..8] of integer; // x массив клеток доски

mas1: array[1..8] of integer; // y массив клеток доски

xr: array [1..8] of integer; //координаты для рисования ферьзей

nfr: integer = 0; //для массива ферзей номер

implementation

{$R *.dfm}

procedure TForm1.FormPaint(Sender: TObject);

var x,y,i1,cc,z,z1:integer;//cc для смены цвета

c,c1:Tcolor; //для хранения цветов доски

//z z1 для расчетов

begin

//xn:=100; //начальные координаты доски

y:=yn;

cc:=0; //служебная для смены цвета

c:=clWhite;

c1:=clDkGray;

//c1:=clBlack; //цвета

Form1.Canvas.brush.Style:=bsClear;

Form1.Canvas.Rectangle(xn,y,xn+300,y+300); //рамка для букв

Form1.Canvas.Pen.Color:=c1; //цвет рамки

Form1.Canvas.Rectangle(xn+29,y+29,xn+271,y+271); //рамка доски

form1.Canvas.Font.Size:=14;

Form1.Canvas.TextOut(xn+15,y+30,'8');

Form1.Canvas.TextOut(xn+15,y+62,'7');

Form1.Canvas.TextOut(xn+15,y+93,'6');

Form1.Canvas.TextOut(xn+15,y+123,'5');

Form1.Canvas.TextOut(xn+15,y+155,'4');

Form1.Canvas.TextOut(xn+15,y+185,'3');

Form1.Canvas.TextOut(xn+15,y+215,'2');

Form1.Canvas.TextOut(xn+15,y+245,'1');

Form1.Canvas.TextOut(xn+35,y+271,'a');

Form1.Canvas.TextOut(xn+70,y+271,'b');

Form1.Canvas.TextOut(xn+100,y+271,'c');

Form1.Canvas.TextOut(xn+130,y+271,'d');

Form1.Canvas.TextOut(xn+160,y+271,'e');

Form1.Canvas.TextOut(xn+195,y+271,'f');

Form1.Canvas.TextOut(xn+220,y+271,'g');

Form1.Canvas.TextOut(xn+250,y+271,'h');

for i1:=1 to 8 do

begin

y:=y+30; //высота квадрата

x:=xn; //установка для нового ряда доски

for i:=1 to 8 do

begin

x:=x+30; //ширина квадрата

if (cc = 1) then

begin

Form1.Canvas.Brush.Color:=c1;

cc:=0;

end

else //смена цвета на противоположный

begin

Form1.Canvas.Brush.Color:=c;

cc:=1

end;

Form1.Canvas.FillRect(Rect(x,y,x+30,y+30)); //рисование квадрата

end;

if cc = 0 then cc:=1 //установка цвета для нового ряда

else cc:= 0;

end;

// рисование ферьзей

if list.ItemIndex >= 0 then //если сделан выбор растановки

begin

// расшифровка координат

z:=10000000;

z1:=fr[list.itemIndex];

for i:=1 to 8 do

begin

xr[i]:= z1 div z;

z1:=z1- xr[i]*z;

z:=z div 10;

end;

for i:=1 to 8 do

begin

x:=mas[xr[i]]+45;

y:=mas1[i]+33;

Form1.Canvas.Brush.Color:=clBlack; //рисование закрашенного ферзя

form1.Canvas.Polygon([Point(x-7,y+25),Point(x-17,y),

Point(x-7,y+10),Point(x,y),

Point(x+7,y+10),Point(x+17,y),Point(x+7,y+25)]);

end;

end;

end;

procedure gen;

var h,z:integer; // h координата по горизонтале //z для fr

begin

h:=0;

repeat

if (col[h] and up[n-h] and down[n+h]) then

begin

x[n]:=h;

col[h]:=false;

up[n-h]:=false;

down[n+h]:=false;

n:=n+1;

if (n = 8) then

begin

z:= 100000000;

for i:=0 to 7 do

begin

z:= z div 10;

fr[nfr]:= fr[nfr]+x[i]*z+z;

end;

nfr:= nfr+1;

end

else gen;

n:=n-1;

col[h]:= true;

up[n-h]:=true;

down[n+h]:=true;

end;

h:=h+1;

until h=8;

end;

procedure TForm1.Button6Click(Sender: TObject);

var z:integer; //z&c для расчетов служебные

begin

// расчет координат

n:= 0; //для gen обозначение вертикали

i:=0; // счетчик

repeat

col[i]:=true;

i:=i+1

until i =8; //цикл для обозначения свободных горизонталей

i:=0;

repeat

up[i-7]:=true;

down[i]:=true;

i:=i+1;

until i =15; //свободные диагонали

gen; //вызов процедуры

//заполнение листа координатами

for i:=0 to 91 do

form1.List.Items.Add(IntToStr(fr[i])); //заполнение лист бокса

list.ItemIndex:=0; //установка первой строки в листе

// заполнение массива клеток

mas[1]:=xn;

mas1[8]:=yn;

z:=30; //ширина клетки доски

for i:=2 to 8 do

mas[i]:=mas[i-1]+z; //массив горизонталей

for i:=7 downto 1 do

mas1[i]:=mas1[i+1]+z; //массив вертикалей

Button6.Enabled:=False;

Text2.visible:=true;

Form1.FormPaint(form1); // перерисовка окна

end;

procedure TForm1.ListClick(Sender: TObject);

begin

Form1.FormPaint(form1); // перерисовка окна

end;

end.



Заключение

Эта работа позволила автору познакомится и попробовать овладеть несколькими приемами в программировании.

Один из которых имеет устоявшиеся название «обратное отслеживание». Идею обратного отслеживания можно применить к большому числу разных на первый взгляд задач. Но суть даже не в «обратном отслеживании» а в тех рассуждениях с помощью которых, мы пришли к нему. При встрече с задачами которые решаются другими методами, они скорее всего могут найдены сходными методами. Другой же состоит в расплате памятью за скорость вычисления. Расплата памятью за скорость вычислений - это более, чем трюк, полезный в данной практической программе. Это один из примеров того множества выборов, которые должен делать программист.

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



Список используемой литературы

1.Роб Баас, Майк Фервай, Хайдемария Гюнтер «Delphi 5», издательство «Ирина»,DHV, 2000,Киев

2. А.Я. Архангельский «Программирование в Delphi 6», издательство «бином», 2001,Москва

3. Евгений Корнилов «Программирование шахмат и других логических игр», издательство «БХВ-Петербург»,2005, Санкт-Петербург

4. Александр Полянский «Среда программирования Delphi 5-6 Справочное пособие», издательство «Познавательная книга плюс»,2001, Москва

5. Эдсгер В. Дейкстра «Краткое введение в искусство программирования»

А.С.Деревянко, перевод, 2006 http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra /ewd316/index316.html

Размещено на Allbest.ru

...