Ответ в теме: Логическая задача: автомобильные гонки

#3558

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

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

Как показано на рисунке поставим символ минус в клетки, которые соответствуют условиям:

Геометрически задача соответствия означает, что на каждой горизонтали и вертикали может стоять только один +. Из этого вытекает два правила экстраполяции, позволяющие автоматически завершить решение задачи:

  1. Если на горизонтали (вертикали) все знаки кроме одного – то свободная позиция фиксируется значением +.
  2. Если на горизонтали (вертикали) имеется +, то все остальные значения
    заполняются знаком .

В нашем случае, во второй строке имеется одна свободная позиция, мы ставим в ней знак +. Далее в первом столбце имеем знак +, значит остальные значения столбца . В третьей строке имеется свободная позиция ставим в ней +. Во второй строке в свободную позицию ставим знак +.

На языке Пролог структура программы будет иметь вид:

predicates
  имя(symbol) - nondeterm (o) nondeterm (i)
  место(symbol) - nondeterm (o)nondeterm (i)
  соответствие(symbol,symbol) - nondeterm (i,i) nondeterm (i,o)
  решение(symbol,symbol,symbol,symbol,symbol,symbol) - nondeterm nondeterm (o,o,o,o,o,o)
clauses
  % база данных имен
  имя(ваня).
  имя(петя).
  имя(коля).
  % база данных мест
  место(первое).
  место(второе).
  место(третье).
  % определим однозначное соответствие И – имя, М - место
  соответствие(И,М):-
    имя(И), И=петя, место(М),
    not(М=второе), not(М=третье).
  соответствие(И,М):-
    имя(И), И=коля, место(М),
    not(М=третье).
  соответствие(И,М):-
    имя(И), И=ваня, место(М).

  решение(И1,М1,И2,М2,И3,М3):-
    И1=петя,соответствие(И1,М1),
    И2=коля,соответствие(И2,М2),
    И3=ваня,соответствие(И3,М3),
    М1<>М2,М1<>М3,М2<>М3.
goal
  решение(Имя1,Место1,Имя2,Место2,Имя3,Место3).