Ответ в теме: Раскраска плоской карты на 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