Задача о ферзях

При этом в начале вычислений и при переходах к любому последующему рекурсивному вызову параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера клетки, допустимой для установки фигуры. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера поля, доступного для установки ферзя. Если в обрабатываемом столбце ферзь установить невозможно, то создавшуюся ситуацию (позицию) назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему столбцу и продолжению работы с ним. Других случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии мы должны считать совокупность всех тупиков. Заметим, что в данном случае элементы базы до начала вычислений неизвестны. Приступим к написанию программного кода: Место, куда вставляем очередного ферзя, определяется в процедуре addFerz;Если значения, соответствующие заданной клетке, равны FALSE, то будем считать, что поле бито, если же TRUE — тогда данную клетку можно занять. Попробуем написать предварительный код для реализации схемы 2.

2.ProcedureaddFerz (i: integer);BeginИнициализируем выбор положения для i-ого ферзяForj:=1 to 8Ifбезопасно thenпоставить ферзя;If (i<8) THEN addFerz (i+1)$IFнеудачноTHENубрать ферзя;End;Чтобы двигаться дальше, необходимо остановиться на каком-либо представлении для данных. Следуя правилам игры в шахматы, мы знаем что ферзь бьет все фигуры, находящиеся на одной с ним вертикали, горизонтали или диагонали, мы приходим к выводу что на каждой вертикали, горизонтали или диагонали не должно располагаться более одной фигуры, отсюда следует при поиске места для 1-го ферзя можно рассматривать лишь первую вертикаль, аналогично для каждого следующего. Таким образом, параметр 1 становится индексом вертикали, а в процессе выбора рассматриваются лишь 8 возможных позиций, то есть 8 допустимых значения индекса горизонталиj. Остается определить как представлять на доске эти восемь ферзей? Очевидно, доску вновь можно было бы представить в виде двумерного массива, но после небольших рассуждений мы приходим к выводу, что это значительно усложнило бы проверку безопасности поля. Конечно, подобное решение нежелательно, потому что такая операция выполняется очень часто. Поэтому хотелось бы остановиться на таком представлении данных, которое по возможности упростило бы проверку. В данной ситуации наиболее разумно делать непосредственно доступной именно ту информацию, которая действительно имеет значение и чаще всего используется. В нашем случае это не поля, занятые ферзями, а информация о том, находится ли уже ферзь на данной горизонтали или диагонали. (Мы уже знаем, что на каждой k-й вертикали (1 <=кБ= 1) стоит ровно один ферзь.) Эти соображения приводят к таким описаниям переменных: vert:array[1.8] ofboolean; // проверкавертикалейhor: array[2.16] of boolean; {суммакоординатклетки 1+1=2 8+8=16,проверка горизонталей и диагоналей, доступна или нет}diag:array[-7.7] ofboolean; // в сумме с b дает проверку диагоналей. Формирование возможных кандидатов происходит регулярным образом, гарантирующим, что ни один кандидат не встретится более чем один раз.

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

2.4. Вывод данных.

Для вывода данных воспользуемся процедурой, которой присвоим имя Print. Для наибольшей эффективности процедуру вывода данных будем вызывать из процедуры addFerze (). Предварительно необходимо вывести на экран номер комбинации, это необходимо для проверки условия, что всего задача имеет 92 решения. Воспользуемся переменной-счетчиком, которую будем наращивать перед каждым последующим выводомs:=s+1;writeln ('Решение номер ', s:2,': ');Для наглядности, чтобы понимать, какая клетка является пустой, а какая ферзем, в пустой клетке будем выводить символ ‘*', а в клетке с ферзем символ ‘#'. Для заполнения заведем массив: vyvod: array[1.8,1.8]ofchar;Предварительно всем клеткам присвоим символ ‘*'fori:=1 to 8 dofor j:=1 to 8 dovyvod[i, j]: ='*'; В зависимости от позиций расставленных ферзей, позициям с ферзями присвоим символ ‘#'for k:=1 to 8 dovyvod[ ]: ='#';И приступим непосредственно к выводу данных: fori:=1 to 8 dobeginfor j:=1 to 8 dowrite (vyvod[i, j],' ');writeln;end;И после вывода для расчета следующей комбинации попросим пользователя продолжить выполнение вычислений: write ('Press <Enter>');readln;Полный исходный код программы можно увидеть в приложении, А к курсовой работе. Примеры работы программы изображены на рисунке 2.1:Рисунок 2.

1.

Заключение

.

В ходе работы над курсовой работой была достигнута цель : — Разработка программы для решения задачи о 8 ферзях.

Для достижения поставленной цели были выполнены следующие задачи: — Изучены алгоритмы решения задачи о восьми ферзях;

— Спроектировано реализуемое приложение;

— Создан программный код согласно проекту в среде программирования PascalABC. Полученная программа соответствует всем требованиям, установленным при написании курсовой работы. Учитываю трудоемкость вычислений, приходим к выводу что реализация решения задачи для досок огромного размера Nна N, в действительности электронно-вычислительной машине придется производить число вычислений, стремящееся к бесконечности, а при нынешних ограничениях в ресурсах ЭВМ, решение текущей задачи не из легких. При выполнении задания, следует отметить, что наиболее информативным оказалось учебное пособие Никлауса Вирта «алгоритмы и структуры данных». Напрашивается вывод, что данная книга отлично подходит для изучения основных алгоритмов, использующихся в программировании.

Список использованных источников

1 автор

Корнилов Е. Н. Программирование шахмат и других логических игр: учеб.

пособие / Е. Н. Корнилов. — издательство «БХВ-Петербург», 2005 — 292с. Вирт Никлаус. Алгоритмы и структуры данных: учеб.

пособие / Никлаус Вирт — издательство «Мир», 1992 — 360 с. Семашко, Г. Л. Программирование на языке паскаль / Г. Л. Семашко, А. И. Салтыков. — Главная редакция физико-математической литературы издательства «Наука», 2015. — 128 c. Еремин О. Ф. Методическое пособие по программированию на языке PascalABC" / О. Ф. Еремин, Моздок, 2009 — 49 с. 2 автора.

О.Ю.Агарева, Ю. В. Селиванов — Математическая логика и теория алгоритмов: учеб.

пособие — Издательско-типографский центр МАТИ, 2011 — 80 с. Электронные ресурсы.

Электронная библиотека Rulit[Электронный ресурс] // Описание языка PascalABC.NET — режим доступа:

http://www.rulit.me/books/opisanie-yazyka-pascalabc-net-download-free-412 001.htmlЭлектронные СМИ www. mir24.ru [Электронный ресурс] // Средства массовой информации — режим доступа:

https://mir24.tv/news/16 265 582/reshenie-zadachi-o-vosmi-ferzyah-ocenili-v-million-dollarovПриложение АЛистинг программыprogramferzi;usescrt;vars, i: integer;vert:array[1.8] of boolean; // проверкавертикалейhor: array[2.16] of boolean; {суммакоординатклетки 1+1=2 8+8=16,проверка горизонталей и диагоналей, доступна или нет}diag:array[-7.7] ofboolean; // в сумме с b дает проверку диагоналейrasst: array[1.8]ofinteger; // номера горизонталей ферзей, собственно расстановкаvyvod: array[1.8,1.8]ofchar; //матрица — вывод расположения ферзейprocedureprint; // вывод результатов на экранvari, j, k:integer;begins:=s+1;writeln ('Решениеномер ', s:2,': ');fori:=1 to 8 doforj:=1 to 8 dovyvod[i, j]: ='*'; //заполним матрицу нолямиfork:=1 to8 dovyvod[8-rasst[k]+1,k]: ='#'; //клетки с ферзями, номер по вертикали, номер по горизонталиfori:=1 to 8 dobeginforj:=1 to 8 dowrite (vyvod[i, j],' ');writeln;end;write ('Press <Enter>');readln;end;procedureaddFerz (i:integer); //рекурсивнаяпроцедурарасстановкиферзейvarj:integer;beginforj:=1 to 8 doif (vert[j] = TRUE) and (hor[i+j] = TRUE) and (diag[i-j] = TRUE) then //еслиполенебъетсяbeginrasst[i]: =j; //займемегоvert[j]: =false; hor[i+j]: =false; diag[i-j]: =false; //делаембитымifi<8 thenaddFerz (i+1) elseprint; //если не последняя вертикаль, то проверяем следующую, иначе выводvert[j]: =true; hor[i+j]: =true; diag[i-j]: =true;{если не получилось до конца, освобождаем полевозвращаемся назад, проверяем следующий вариант}end;end;beginclrscr;fori:=1 to 8 do vert[i]: =true; //всеполясвободныfori:=2 to16 dohor[i]: =true; //нет угроз ни по горизонталям, ни по вертикалямfori:=-7 to 7 do diag[i]: =true; //нетугрозподиагоналямs:=0;addFerz (1); //начинаем с первой вертикалиreadlnend.