Prolog图着色（4色图）代码解释

Question

the map I am using

（对不起，我的英语不好）我从老师那里得到了 Prolog 代码，但我是这门语言的新手，所以我不明白什么是冲突//没有冲突//找到着色的真正作用以及他为什么使用节点和列表，我搜索了一个解释，但我找不到类似的代码。这是代码 >>>

adjacent( 1, 2 ).
adjacent( 1, 3 ).
adjacent( 1, 4 ).
adjacent( 1, 5 ).
adjacent( 2, 3 ).
adjacent( 2, 4 ).
adjacent( 3, 4 ).
adjacent( 4, 5 ).

color( red ).
color( yellow ).
color( pink ).
color( purple ).

conflict( color( Node1, Color ), color( Node2, Color )) :-
       adjacent( Node1, Node2 ).

noconflict( _, [] ).
noconflict( Coloring1, [Coloring2 | Colorings] ) :-
    not( conflict( Coloring1, Coloring2 )),
        noconflict( Coloring1, Colorings ).

findcoloring( [], [] ).
findcoloring( [Node | Nodes], [Coloring | Colorings] ) :-
    findcoloring( Nodes, Colorings ),
    Coloring = color( Node, Color ),
    color( Color ),
    noconflict( Coloring, Colorings ).

Answer 1

如果您是该语言的新手，可能无法在简短而有用的答案中解释所有这些代码。

why he is using nodes and lists

地图可以看作是连接图，“节点”和“边”是这些图的常用术语。节点表示地图的区域，并且它们在图片中相邻使得边缘连接如下：

列表是在 Prolog 中保存多个内容的便捷方式。

问题的设置是这些事实，例如节点 1 和 3 在地图中相邻，1 和 4 也是相邻的，并且 red 是颜色，[=19= 也是]:

adjacent( 1, 3 ).
adjacent( 1, 4 ).
adjacent( 1, 5 ).
adjacent( 2, 3 ).
adjacent( 2, 4 ).
adjacent( 3, 4 ).
adjacent( 4, 5 ).

color( red ).
color( yellow ).
color( pink ).
color( purple ).

这条规则规定两个相连的地图区域不能是相同的颜色。它向我们展示了 Prolog 术语 color(N, C) 是编写代码以连接地图区域（节点）及其指定颜色的方式。它对 Node1 和 Node2 使用相同的变量 Color，不需要像其他语言可能使用的 if (Color1 == Color2)。如果两个节点相邻并且被赋予了相同的颜色，那就是冲突：

conflict( color( Node1, Color ), color( Node2, Color )) :-
       adjacent( Node1, Node2 ).

构建解决方案的是以下代码，它检查 color(N, C) 分配列表以查找任何冲突。它检查第一个与第二个，然后 recursively 检查第一个与所有剩余的。如果没有发现冲突，则 noconflicts 为真：

noconflict( _, [] ).
noconflict( Coloring1, [Coloring2 | Colorings] ) :-
    not( conflict( Coloring1, Coloring2 )),
        noconflict( Coloring1, Colorings ).

以下代码为节点着色，它以节点列表作为第一个参数 findcoloring([1,2,3,4,5], Answer) 并转到列表的末尾，然后返回并从末尾分配颜色 [5] 获取一种颜色，检查无冲突，然后 [4,5] 获取颜色并检查冲突，然后 [3,4,5] 获取颜色，等等。这也是递归的：

findcoloring( [], [] ).
findcoloring( [Node | Nodes], [Coloring | Colorings] ) :-
    findcoloring( Nodes, Colorings ),
    Coloring = color( Node, Color ),
    color( Color ),
    noconflict( Coloring, Colorings ).

Prolog 工作方式的本质，如果存在冲突，则 noconflict() 测试失败，Prolog 将回溯并撤消分配的颜色，并在搜索解决方案时尝试不同的颜色。这就是为什么没有循环，没有变量赋值，没有if/else，只是声明当每个节点都有颜色并且它们之间没有冲突时地图是彩色的。

Prolog图着色（4色图）代码解释

Prolog map coloring (4 colors map) code explanation

prolog