Ответ в теме: Раскраска плоской карты на Prolog

      Комментарии к записи Ответ в теме: Раскраска плоской карты на Prolog отключены
#2828

В качестве структуры данных можно использовать граф, т.к. с его помощью удобно задавать смежные области — если области a и b смежные — то существует дуга между ними.

При решении задачи на Visual Prolog нужно сначала объявить используемые типы данных (на SWI Prolog этот шаг можно пропустить, т.к. в нем используется динамическая типизация):

DOMAINS
color_d = red; green; blue; black
node_d = symbol
node_color_d = node_color(node_d, color_d)
edge_d = edge(node_d, node_d)
nodes_d = node_d*
coloring_d = node_color_d*

Тут объявлены:

  1. 4 цвета, которых будет достаточно для раскраски карты;
  2. тип узла, представляющегося символом;
  3. структура node_color_d, совмещающая узел и цвет;
  4. структура дуги, совмещающая два узла — начало и конец дуги;
  5. список вершин графа;
  6. список типа node_color_d, задающий раскраску графа

В базе данных могут лежать дуги — это будет удобно если мы захотим изменять карту во время выполнения программы:

DATABASE
edge(node_d, node_d)

Приведенный вами граф может быть задан следующим набором ребер:
  	edge(a, b).
edge(a, c).
edge(a, d).
edge(b, c).
edge(b, e).
edge(c, d).
edge(c, e).
edge(c, f).
edge(d, f).
edge(e, f).

Т.к. ребра являются ориентированными, а отношение смежности — симметричным, нам потребуется вспомогательный предикат, выполняющий проверку смежности:
exist_edge(From, To):-
edge(From, To), !; edge(To, From), !.

Он проверяет существование дуги из From в To, а при неудаче — поиск обратной дуги.

Программа будет перебирать все варианты окраски узлов графа, а затем проверять корректность выбранных цветов.
Предикат color должен выдавать нам все возможные цвета, это нужно для перебора вариантов:

	color(red). 
color(green).
color(blue).
color(black).

Предикат nondeterm generate_colors(nodes_d, coloring_d) принимает список вершин графа и возвращает вариант раскраски графа, при этом для каждой вершины он вызывает предикат color, а остальные вершины обрабатывает рекурсивно:
	generate_colors([], []).
generate_colors([HeadNode|TailNodes], [node_color(HeadNode, NodeColor)|TailNodeColors]):-
color(NodeColor), 
generate_colors(TailNodes, TailNodeColors).

Проверка раскраски карты может сводиться к поиску такой пары смежных областей, что их цвета совпадают:
check_coloring(Coloring):-
member(node_color(ANode, Color), Coloring),
member(node_color(BNode, Color), Coloring),
exist_edge(ANode, BNode), !, fail; !.

Тут с помощью встроенной функции member (реализация функции member для Visual/Turbo Prolog) выполняется поиск в списке (задающем раскраску) некоторого узла (ANode с цветом Color) — фактически, осуществляется перебор элементов. Вторым вызовом member выполняется поиск в списке узлов с таким же цветом (переменная Color к этому времени уже инициализирована). Затем, выполняется проверка существования дуги между этими вершинами (смежности областей) и если области смежны — применяется отсечение и fail. Отсечение запрещает перебор (поиск других вариантов решения для этих же входных данных), а fail — показывает, что решения нет. В противном случае (если перебраны все вершины и не было найдено ни одной пары смежных областей одного цвета) — управление передается коду, расположенному после точки с запятой (см. Принципы построения Prolog-программ), который всегда завершается успешно.

Остается вызывать все эти функции чтобы получить решение:

GOAL 
generate_colors([a, b, c, d, e, f], NodeColors),
check_coloring(NodeColors), !.

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

map_coloring_trace