4.5.1. Программа 1

4.5.1. Программа 1

Вначале нужно выбрать способ представления позиции на доске. Один из наиболее естественных способов — представить позицию в виде списка из восьми элементов, каждый из которых соответствует одному из ферзей. Каждый такой элемент будет описывать то поле доски, на которой стоит соответствующий ферзь. Далее, каждое поле доски можно описать с помощью пары координат (X и Y), где каждая координата - целое число от 1 до 8. В программе мы будем записывать такую пару в виде

X / Y

где оператор "/" обозначает, конечно, не деление, а служит лишь для объединения координат поля в один элемент списка. На рис. 4.6 показано одно из решений задачи о восьми ферзях и его запись в виде списка.

После того, как мы выбрали такое представление, задача свелась к нахождению списка вида:

[X1/Y1, X2/Y2, X3/Y3, X4/Y4, X5/Y5, X6/Y6, X7/Y7, X8/Y8]

удовлетворяющего требованию отсутствия нападений. Наша процедура решение должна будет найти подходящую конкретизацию переменных X1, Y1, Х2, Y2, , Х8, Y8. Поскольку мы знаем, что все ферзи должны находиться на разных вертикалях во избежание нападений по вертикальным линиям, мы можем сразу же ограничить перебор, чтобы облегчать поиск решения. Можно поэтому сразу зафиксировать X-координаты так, чтобы список, изображающий решение, удовлетворял следующему, более конкретному шаблону:

[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]

Рис. 4.6. Решение задачи о восьми ферзях. Эта позиция может быть представлена в виде списка [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1].

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

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

Случай 1. Список ферзей пуст. Пустой список без сомнения является решением, поскольку нападений в этом случае нет.

Случай 2. Список ферзей не пуст. Тогда он выглядит так:

[ X/Y | Остальные ]

В случае 2 первый ферзь находится на поле X / Y, а остальные — на полях, указанных в списке Остальные. Если мы хотим, чтобы это было решением, то должны выполняться следующие условия:

(1) Ферзи, перечисленные в списке Остальные, не должны бить друг друга; т.е. список Остальные сам должен быть решением.

(2) X и Y должны быть целыми числами от 1 до 8.

(3) Ферзь, стоящий на поле X / Y, не должен бить ни одного ферзя из списка Остальные.

Чтобы запрограммировать первое условие, можно воспользоваться самим отношением решение. Второе условие можно сформулировать так: Y должен принадлежать списку целых чисел от 1 до 8. т.е. [1, 2, 3, 4, 5, 6, 7, 8]. С другой стороны, о координате X можно не беспокоиться, поскольку список-решение должен соответствовать шаблону, у которого X-координаты уже определены. Поэтому X гарантированно получит правильное значение от 1 до 8. Третье условие можно обеспечить с помощью нового отношения небьет. Все это можно записать на Прологе так:

решение( [X/Y | Остальные] ) :-

 решение( Остальные),

 принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),

 небьет( X/Y, Остальные).

Осталось определить отношение небьет:

небьет( Ф, Фспис)

И снова его описание можно разбить на два случая:

(1) Если список Фспис пуст, то отношение, конечно, выполнено, потому что некого бить (нет ферзя, на которого можно было бы напасть).

(2) Если Фспис не пуст, то он имеет форму

[Ф1 | Фспис1]

и должны выполняться два условия:

 (а) ферзь на поле Ф не должен бить ферзя на поле Ф1 и

 (b) ферзь на поле Ф не должен бить ни одного ферзя из списка Фспис1.

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

• Y-координаты ферзей были различны и

• ферзи не находились на одной диагонали, т.е. расстояние между полями по направлению X не должно равняться расстоянию между ними по Y.

На рис. 4.7 приведен полный текст программы. Чтобы облегчить ее использование, необходимо добавить список-шаблон. Это можно сделать в запросе на генерацию решений. Итак:

?-  шаблон( S), решение( S).

решение( [] ).

решение( [X/Y | Остальные ] ) :-

  % Первый ферзь на поле X/Y,

  % остальные ферзи на полях из списка Остальные

 решение( Остальные),

 принадлежит Y, [1, 2, 3, 4, 5, 6, 7, 8] ),

 небьет( X/Y | Остальные).

  % Первый ферзь не бьет остальных

небьет( _, [ ]). % Некого бить

небьет( X/Y, [X1/Y1 | Остальные] ) :-

 Y == Y1,       % Разные Y-координаты

 Y1-Y == X1-X   % Разные диагонали

 Y1-Y == X-X1,

 небьет( X/Y, Остальные).

принадлежит( X, [X | L] ).

принадлежит( X, [Y | L] ) :-

 принадлежит( X, L).

% Шаблон решения

шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

Рис. 4.7.  Программа 1 для задачи о восьми ферзях.

Система будет генерировать решения в таком виде:

S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1];

S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1];

S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1].

...

Упражнение

4.6. При поиске решения программа, приведенная на рис. 4.7, проверяет различные значения Y-координат ферзей. В каком месте программы задается порядок перебора альтернативных вариантов? Как можно без труда модифицировать программу, чтобы этот порядок изменился? Поэкспериментируйте с разными порядками, имея в виду выяснить, как порядок перебора альтернатив влияет на эффективность программы.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Программа

Из книги автора

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


4.7.1. Программа tar

Из книги автора

4.7.1. Программа tar У читателя, привыкшего к архиваторам типа arj, которые собирают файлы в единый архив и сразу "сжимают" их, может возникнуть вопрос "А зачем использовать две программы?” Все дело в том, что tar расшифровывается как Tape ARchiver, он не сжимает данные, а лишь объединяет


10.2. Программа rpm

Из книги автора

10.2. Программа rpm Название этой программы (или команды) является аббревиатурой от Redhat Package Manager. Такая расшифровка дается в большинстве книг и руководств по Linux и кажется мне более правильной и логичной, хотя в главе 6 "The Official Red Hat Linux Reference Guide" говорится: "The RPM Package Manager (RPM), is an open


12.2.3 Программа gv

Из книги автора

12.2.3 Программа gv Программа gv (или ghostview) разработана Иоганнесом Плассом (Johannes Plass) и предназначена для просмотра файлов формата PostScript и PDF (рис. 12.2).После ее запуска без указания имени файла основное окно программы будет пустым. Чтобы открыть какой-то файл, надо щелкнуть по


13.3.2 Программа ftp

Из книги автора

13.3.2 Программа ftp Программа ftp - это пользовательский интерфейс к стандартному протоколу передачи файлов по Интернету - File Transfer Protocol. Программа позволяет передавать файлы на удаленный компьютер и получать файлы с удаленного компьютера. Однако, введя команду ftp, вы


2.6.2. Программа RPM

Из книги автора

2.6.2. Программа RPM Установка программного обеспечения в дистрибутивах Red Hat и Mandrake производится с помощью программы rpm. RPM (red hat package manager) — это менеджер пакетов Red Hat. Несмотря на то, что в названии присутствует «Red Hat», он полностью предназначен работать как открытая пакетная


П1.1. Программа AVZ

Из книги автора

П1.1. Программа AVZ Программа AVZ (Антивирус Зайцева) – очень полезная утилита, и не раз меня выручала еще со времен Windows XP. Тогда я использовал антивирус Касперского, который не умел работать в безопасном режиме. Получалось так – все, что пропустил основной антивирус, в


6. Программа обучения

Из книги автора

6. Программа обучения Расскажите, что находится внутри продукта, как построено обучение, и покажите блоки тем, списки – пункты программы. «Вы узнаете три способа, как сделать то, семь секретов, как сделать это». Причем вы не только рассказываете, что внутри, но и то, что это


Программа Istanbul

Из книги автора

Программа Istanbul Istanbul (http://live.gnome.org/Istanbul) – это очень удобный и простой в работе инструмент, написанный с использованием библиотек GTK+. Результат работы сохраняется в видеофайл, кодированный свободным кодеком Ogg Theora. Как вариант, можно передать созданный поток серверу Icecast


Программа Wink

Из книги автора

Программа Wink Wink (http://www.debugmode.com/wink/) – это мощная и простая в работе программа, написанная с использованием библиотек wxWidgets. Wink не распространяется с открытым исходным кодом, но является свободной для персонального и делового использования. С ее помощью можно делать снимки


Программа

Из книги автора

Программа      Ниже приводится короткая программа, позволяющая узнавать номер кода символа даже в том случае, если на вашей машине не используется код ASCII. main( )   /* определяет номер кода символа */{   char ch;   printf(" Введите, пожалуйста, символ . ");   scanf(" %c", &ch);   /* ввод


9.3. Программа apt-get

Из книги автора

9.3. Программа apt-get Предположим, у вас есть пакет package.deb. При его установке обнаружилось, что он требует наличия пакета lib.deb, который у вас не установлен. Что ж, вы находите в Интернете отсутствующий пакет, устанавливаете его способом, описанным в разд. 9.2 (то есть применяя


20.3. Программа bum

Из книги автора

20.3. Программа bum Ранее в Ubuntu имелась программа Службы (в программной группе Система | Администрирование), позволяющая включать/отключать системные сервисы. В современных версиях Ubuntu такой программы нет. Зато можно установить программу Boot-Up Manager, которая даже лучше, чем


4.5.1. Программа 1

Из книги автора

4.5.1. Программа 1 Вначале нужно выбрать способ представления позиции на доске. Один из наиболее естественных способов — представить позицию в виде списка из восьми элементов, каждый из которых соответствует одному из ферзей. Каждый такой элемент будет описывать то поле


4.5.2. Программа 2

Из книги автора

4.5.2. Программа 2 В соответствии с принятым в программе 1 представлением доски каждое решение имело вид[1/Y1, 2/Y2, 3/Y3, ..., 8/Y8]так как ферзи расставлялись попросту в последовательных вертикалях. Никакая информация не была бы потеряна, если бы X-координаты были пропущены. Поэтому


4.5.3. Программа 3

Из книги автора

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