Программирование на языке Пролог | страница 74

Теперь мы можем рассмотреть последнюю основную область применения отсечения в программах на Прологе – завершение последовательности порождения и проверки вариантов. Очень часто программа состоит из частей, соответствующих следующей общей модели. Имеется последовательность целей, которые могут быть согласованы множеством различных способов и которые порождают много возможных решений при возврате. Кроме того, имеются цели, проверяющие приемлемость порожденных решений для последующего использования. Если поиск сопоставлений для этих целевых утверждений закончится неудачей, то возврат приведет к тому, что будет предложено новое решение. Новое решение будет подвергнуто проверке на пригодность и так далее. Процесс завершится, либо когда будет порождено приемлемое решение (успех), либо когда нельзя больше найти решений (неудача). Мы можем назвать «генератором» целевые утверждения, которые порождают все возможные альтернативы, а целевые утверждения, которые проверяют пригодность решения, - «контролером». Давайте рассмотрим пример такой программы. Приводимый ниже фрагмент мог бы быть частью программы, играющей в крестики-нолики. Эта программа использует встроенные предикаты var и arg, которые подробно рассмотрены в гл. 6.

вынужденный ход(Доска,K):- линия(Клетки), угроза(Клетки,Доска,K),!.

линия([1,2,3]).

линия([4,5,6]).

линия([7,8,9]).

линия([1,4,7]).

линия([2,5,81).

линия([3,6,9]).

линия ([1,5,9]).

линия([3,5,7]).

угроза([X,Y,Z],B,X):- пусто(Х,В), крестик (Х,В), крестик(Z,B).

угроза([X,Y,Z],B,Y):- пусто(Y,B), крестик (Х,В), крестик(Z,B). 

угроза([X,Y,Z],B,Z):- пусто(Z,B), крестик(Х,В), крестик(Y,B).

пусто(К,Доска):- arg(K,Дocкa,C), var(C).

крестик(К,Доска):- arg(K,Дocкa,C), nonvar(C), C=X.

нолик(К,Доска):- arg(К,Доска,С), nonvar(C), С=0.

Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок — символ X. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:

Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат