Prolog map coloring (4 colors map) code explanation

the map I am using

(sorry for my bad English) I got Prolog code from a teacher but I am new to the language so I couldn't understand what conflict//no conflict//find coloring really does and why he is using nodes and lists, I searched for an explanation but I couldn't find similar code. This is the code >>>

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 ).

Solution 1:

If you are new to the language it may be impossible to explain all of that code in a short and useful answer.

why he is using nodes and lists

The map can be seen as a graph of connections and "nodes" and "edges" are common terms for these graphs. Nodes meaning areas of the map, and them being adjacent in the picture makes for edge connections like this:

Lists are a convenient way to hold multiple things in Prolog.

The setup for the problem is these lines of facts which say e.g. that node 1 and 3 are adjacent in the map, so are 1 and 4, and that red is a color, so is 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 ).

and this rule which says that two connected map areas cannot be the same color. It shows us that the Prolog term color(N, C) is the way the code has been written to connect map areas (nodes) with their assigned colors. It uses the same variable Color with both Node1 and Node2, there is no need for if (Color1 == Color2) like other languages might use. If two nodes are adjacent and have been given the same color, that's a conflict:

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

Building up to the solution is the following code which checks a list of color(N, C) assignments looking for any conflicts. It checks the first one against the second one, then recursively checks the first one against all the remaining ones. If there are no conflicts found, noconflicts is true:

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

The following code colors the nodes, it takes a list of nodes as the first parameter findcoloring([1,2,3,4,5], Answer) and goes to the end of the list, then comes back up and assigns colors from the end [5] gets a color which is checked for no conflicts, then [4,5] both get colorings and are checked for conflicts, then [3,4,5] get colorings, etc. This is also recursive:

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

The nature of how Prolog works, if there is a conflict then the noconflict() test fails, and Prolog will backtrack and undo the assigned color and try a different one as it searches for a solution. This is why there's no loop, no variable assignment, no if/else, just a declaration that the map is colored when each node has a color and there are no conflicts between any of them.