Использование структур Григорьева И.В.. 2 Задача о восьми ферзях Вариант 1 Каждое поле доски будем описывать с помощью пары координат X/Y. Необходимо. - презентация

1 Использование структур Григорьева И.В.

2 2 Задача о восьми ферзях Вариант 1 Каждое поле доски будем описывать с помощью пары координат X/Y. Необходимо найти список [X1/Y1, X2/Y2, X3/Y3, X4/Y4, X5/Y5, X6/Y6, X7/Y7, X8/Y8] удовлетворяющий требованию отсутствия нападений. 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * Одно из решений задачи о восьми ферзях.

3 3 Процедура решение будет искать подходящую конкретизацию переменных X1, Y1, X2, Y2, …, X8, Y8. Зафиксируем X-координату так, чтобы список, изображающий решение, удовлетворял более конкретному шаблону [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]. Обобщим задачу в отношении количества ферзей, разрешив количеству ферзей принимать любые значения включая 0. Тогда решение можно сформулировать рассмотрев случаи: Случай 1 Список ферзей пуст, в этом случае нападений нет.

4 4 Случай 2 Список ферзей не пуст, тогда он имеет вид [X/Y | Остальные ], чтобы он был решение необходимо чтобы (1) Ферзи в списке Остальные не должны бить друг друга, т.е. список остальные сам должен быть решением. (2) X и Y должны быть целыми числами от 1 до 8. (3) Ферзь в поле X/Y не должен бить не одного ферзя в списке Остальные. решение( [X/Y | Остальные]):- Решение (Остальные), принадлежит(Y, [1, 2, 3, 4, 5, 6, 7, 8] ), небьет(X/Y, Остальные).

5 5 Определим отношение небьет( Ф, Фспис) (1) Если Фспис пуст, то отношение выполнено, т.к. нет ферзя на которого можно напасть. (2) Фспис - не пуст, то он имеет форму [Ф1 | Фспис1] и должны выполняться два условия: (a) ферзь на поле Ф не должен бить ферзя на поле Ф1 и (b) ферзь на поле Ф не должен бить ни одного ферзя из списка Фспис1.

6 6 Так как наш шаблон обеспечивает, что все ферзи находятся на разных вертикалях, то остается обеспечить чтобы: Y-координаты ферзей были различны и Ферзи не находились на одной диагонали, т.е. расстояние между полями по направлению X не должно равняться расстоянию между ними по направлению Y. небьет( _, [ ]). небьет( X/Y, [X1/Y1 | Остальные] ):- YY1, (Y1-Y)(X1-X), (Y1-Y)(X-X1), небьет (X/Y, Остальные).

7 7 Вариант 2 Заменим представление решения [1/Y1, 2/Y2, 3/Y3,…, 8/Y8] более экономным представлением, оставив в нем только Y-координаты ферзей: [Y1, Y2, Y3, …, Y8]. Чтобы не было нападений по горизонтали, никакие два ферзя не должны занимать одну и ту же горизонталь, т.е. решение представляет собой одну из перестановок списка: [1, 2, 3, 4, 5, 6, 7, 8]

8 8 Такая перестановка S является решением, если каждый ферзь в ней не находится под боем: решение( S):- перестановка ([1, 2, 3, 4, 5, 6, 7, 8], S), безопасный (S). Отношение безопасный можно разбить на два случая (1) S – пустой, тогда он безопасный; (2) S – непустой список вида [Ферзь| Остальные]. Он безопасный, если список Остальные безопасный и Ферзь не бьет не одного Ферзя из списка Остальные.

9 9 безопасный( [ ]). безопасный([Ферзь | Остальные]):- безопасный ( Остальные), небьет (Ферзь, Остальные, 1). Расположение ферзей определяется только их Y-координатами, X-координат в представлении в явном виде нет. Этой трудности можно избежать, введя обобщение отношения небьет

10 10 (a)(a) * * * * (b) * * * * (a)Расстояние по X между Ферзь и Остальные равно 1; (b)Расстояние по X между Ферзь и Остальные равно 2;

11 11 небьет ( _, [ ], _ ). небьет (Y, [ Y1 | CписY ], РасстX) :- Y1-Y РасстХ, Y-Y1РасстХ, Расст1 is РасстX+1, небьет (Y, СписY, Расст1).

12 12 Вариант 3 Система представления с четырьмя координатами: xвертикаль yгоризонталь uдиагонали, идущие снизу вверх vдиагонали, идущие снизу вверх Эти координаты не являются независимыми, при заданных x и y, u и v определяются однозначно. Например,u = x - y v = x + y

13 13

14 14 Области определения координат таковы Dx = [1, 2, 3, 4, 5, 6, 7, 8] Dy = [1, 2, 3, 4, 5, 6, 7, 8] Du = [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7] Dv = [2,3,4,5,6,7,8, 9, 10, 11, 12, 13, 14, 15, 16] При заданных четырех областях изменения выбрать позицию для первого ферзя, вычеркнуть соответствующие позиции из областей изменения, а затем использовать оставшиеся элементы этих областей для размещения остальных ферзей.

15 15 Ключевым в этой программе является отношение реш (СписY, Dx, Dy, Du, Dv), которое конкретизирует Y-координаты ( в CписY) ферзей, считая, что они размещены в последовательных вертикалях, взятых из Dx. Решение (CписY) :- реш ( СписY, [1, 2, 3, 4, 5, 6, 7, 8], [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16].

16 16 реш( [ ], [ ], Dy, Du, Dv). реш([Y | СписY], [X | Dx1], Dy, Du, Dv ) :- удалить (Y, Dy, Dy1), U is X-Y, удалить (U, Du, Du1), V is X+Y, удалить (V, Dv, Dv1), реш(CписY, Dx1, Dy1, Du1, Dv1).

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

18 18 Решение числового ребуса Известным примером числового ребуса является DONALD + GERALD ROBERT Задача состоит в том, чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры.

19 19 Определим отношение сумма( N1, N2, N) где N1, N2 и N представляют три числа данного ребуса. Цель cyммa(N1, N2, N) достигается, если существует такая замена букв цифрами, что N1+N2 = N. Первым шагом к решению будет выбор представления чисел N1, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр.

20 20 Например, число 255 будет тогда представляться списком [2,2,5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так: [ D,O,N,A,L,D ] + [ G,E,R,A,L,D ] = [ R,O,B,E,R,T ]

21 21 Теперь задача состоит в том; чтобы найти такую конкретизацию переменных D, О, N и т.д., для которой сумма верна. После того, как отношение сумма будет запрограммировано, задание для пролог- системы на решение ребуса будет иметь вид ?- сумма([ D,O,N,A,L,D ], [ G,E,R,A,L,D ], [ R,O,B,E,R,T ]).

22 22 Суммирование производится цифра за цифрой, начиная с младших цифр в сторону старших, всякий раз учитывая цифру переноса справа. Необходимо также сохранять множество допустимых цифр, т.е. цифр, которые еще не были использованы для конкретизации уже встретившихся переменных. Поэтому, вообще говоря, кроме трех чисел N1, N2 и N в рассмотрении должна участвовать некоторая дополнительная информация:

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

24 24 сумма1( N1, N2, N, C1, С, Цифры1, Цифры) Здесь N1, N2 и N - наши три числа, как и в отношении сумма, С1 - перенос справа (до сложения N1 и N2), а С - перенос влево (после сложения). Пример: ?- сумма1 ( [H,E], [6,E], [U,S], 1, 1, [1,3,4,7,8,9],Цифры). Н = 8 Е = 3 S = 7 U = 4 Цифры = [1,9]

25 25 Если N1 и N2 удовлетворяют отношению сумма, то С1 и С должны быть равны 0. Цифры1 - список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении сумма любых цифр, ее определение в терминах отношения сумма1 выглядит так: сумма( N1, N2, N) :- сумма1(N1,N2,N,0,0,[0,1,2,3,4,5,6,7,8,9],_).

26 26 Это отношение является уже достаточно общим, чтобы можно было определить его рекурсивно. Без ограничения общности мы предположим, что все три списка, представляющие три числа, имеют одинаковую длину. Наш пример, конечно, удовлетворяет этому условию, но если это не так, то всегда можно приписать слева нужное количество нулей к более «короткому» числу.

27 27 Определение отношения сумма1 можно разбить на два случая: Все три числа представляются пустыми списками. Тогда сумма([], [], [], 0, 0, Циф, Циф). Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид: [D1| N1],[D2| N2],[D| N]

28 28 В этом случае должны выполняться два условия: Оставшиеся цифры, рассматриваемые как три числа N1, N2 и N, сами должны удовлетворять отношению сумма1, выдавая влево некоторый перенос С2 и оставляя некоторое подмножество неиспользованных цифр Циф2.

29 29 Крайние левые цифры D1, D2 и D, а также перенос С2 должны удовлетворять отношению: С2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр. cумма1([D1|N1],[D2,|N2],[D|N], С2,С,Циф2,Циф) :- сумма1( N1, N2, N, С1, С2, Циф1, Циф2), суммацифр( D1, D2, С2, D, С, Циф2, Циф).

30 30 Осталось только описать на Прологе отношение суммацифр. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка Циф2. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр «потрачена» не будет.

31 31 В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - непеременная, ничего не вычеркивается (конкретизации не было). Вот эта программа: удалить( Элемент, Список, Список) :- bound( Элемент), !. удалить( Элемент, [Элемент | Список], Список). удалить(Элемент, [А | Список], [А | Список1]) :- удалить( Элемент, Список, Список1).

32 32 В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'а и ROBERT'а с использованием этой программы выглядит так: ?- ребус1( N1, N2, N), сумма( N1, N2, N). сумма( N1, N2, N) :- сумма1( N1, N2, N, 0, 0, [0,1,2,3,4,5,6,7,8,9], _). сумма1( [], [], [], 0, 0, Цифры, Цифры). …

33 33 суммацифр( D1, D2, C1, D, С, Циф1, Циф) :- удалить( D1, Циф1, Циф2), % Выбор доступной цифры для D1 удалить( D2, Циф2, ЦифЗ), % Выбор доступной цифры для D2 удалить( D, ЦифЗ, Циф), % Выбор доступной цифры для D S is D1 + D2 + C1, D is S mod 10, С is S div 10.

34 34 % Примеры ребусов ребус1( [D,O,N,A,L,D], [G,E,R,A,L,D], [R,O,B,E,R,T]). ребус2( [0,S,E,N,D], [0,M,O,R,E], [M,O,N,E,Y]).