Задача раскраски карты состоит в приписывании каждой стране на заданной карте одного из четырех заданных цветов с таким расчетом, чтобы ни одна пара соседних стран не была окрашена в одинаковый цвет. Существует теорема, которая гарантирует, что это всегда возможно.
Пусть карта задана отношением соседства
соседи( Страна, Соседи)
где Соседи - список стран, граничащих со страной Страна. При помощи этого отношения карта Европы с 20-ю странами будет представлена (в алфавитном порядке) так:
соседи( австрия, [венгрия, запгермания, италия,
лихтенштейн, чехословакия,
швейцария, югославия]),
соседи( албания, [греция, югославия]).
соседи( андорра, [испания, франция]).
. . .
Решение представим в виде списка пар вида
Страна / Цвет
которые устанавливают цвет для каждой страны на данной карте. Для каждой карты названия стран всегда известны заранее, так что задача состоит в нахождении цветов. Таким образом, для Европы задача сводится к отысканию подходящей конкретизации переменных C1, C2, СЗ и т.д. в списке
[австрия/C1, албания/С2, андорра/С3, . . .]
Теперь определим предикат
цвета( СписЦветСтран)
который истинен, если СписЦветСтран
удовлетворяет тем ограничениям, которые наложены на раскраску отношением соседи.