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

Question

（抱歉我的英语不好）我从老师那里得到了 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

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

为什么他使用节点和列表

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

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

问题的设置是这些事实，例如：节点

1

和

3

在地图中相邻，

1

和

4

也相邻，

red

是一种颜色，

yellow

也是一种颜色：

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)

是编写代码以连接地图区域（节点）及其指定颜色的方式。它使用与

Color

和

Node1

相同的变量

Node2

，不需要像其他语言可能使用的

if (Color1 == Color2)

。如果两个节点相邻并且被赋予相同的颜色，那就是冲突：

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

构建解决方案是以下代码，它检查

color(N, C)

分配列表以查找任何冲突。它对照第二个检查第一个，然后“递归地”对照所有剩余的检查第一个。如果没有发现冲突，则 noconflicts 为 true：

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，只是声明当每个节点都有颜色时地图是有颜色的，并且它们之间没有冲突。

Answer 2

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

不认为

adjacent( n1, n2 ).

事实是对称的。快速解决方法是：

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