Tabling in four_color example

Hi,

Am trying to change the example at


to make use of tabling in swipl version 8.1.10-56-g1631e38f2

The current attempt is at


but the test run doesn’t produce the expected results as in

Thanks for any help and kind regards,
Jos

1 Like
:- table four_color/2.

four_color(Place, Color) :-
    neighbours(Place, Neighbours),
    member(Color, [red, green, blue, yellow]),
    \+ four_color(Place, _),
    \+ (member(Neighbour, Neighbours), four_color(Neighbour, Color)).

This is not going to work. I think the misconception is that you seem to believe that \+ four_color(Place, _) checks that no color has yet been assigned (added to the tables). Right? This is not what happens.

As is, \+ is not tabling aware and thus we get some odd results where cuts over tables lead to incomplete results. You can use tnot/1 instead. Then, disregarding most, we read four_color(Place, Colour) :- tnot(four_colour(Place, _). and that returns

104 ?- run.
four_color(malta, green).
four_color(malta, red).
four_color(malta, blue).
four_color(malta, yellow).

Think about it, only malta has no neighbours :slight_smile:

I’m not much of a tabling expert yet, so it was a challenge to understand this better. My start was like this:

:- table four_color/2, neighbour_colour/2.

four_color(Place, Place-Color) :-
    neighbours(Place, _Neighbours),
    member(Color, [red, green, blue, yellow]),
    tnot(neighbour_colour(Place, Color)).

neighbour_colour(Place, Color) :-
    neighbours(Place, Neighbours),
    member(Neighbour, Neighbours),
    four_color(Neighbour, Color).

Now we have a nice logical definition. If you run it, you’ll find all places can have all colors. This is true: for each place we can give it some colour and colour the others such that this color is valid.

We need to define a relation that captures an enitre mapping. I need to think about that more. Note that normally you’d end up with a program that will produce all possible colorings. Possiby you can avoid that using answer subsumption.

Nice example to see where the limits of tabling are. I hope a tabling expert steps in :slight_smile:

1 Like

Thanks very much for the feedback from both of you and there is indeed a need
to take the whole map into account. This is another attempt in plain swipl
https://github.com/josd/see/blob/487c745d594b0505913c5ef56e37a2b846cbb9e2/four_color/four_color.pl and it also works with the reordered map of JanB.

The one time I actually needed coloring I used clp(fd): create a variable for each place color, label the colors 1…4, use in/2 to define the domain of each variable and add the clpfd inequality constraints from the neigbours. Finally label the variables. I didn’t do any timing to see whether that scales better than plain Prolog.

1 Like

There is indeed a huge difference i.e. the latter version (with the reverse)
takes only 1,904 inferences compared to 2,607,835 inferences for the former
which is indeed backtracking 18134 times.

$ swipl -f four_color.pl -g run | grep backtracking | wc -l
% 2,607,835 inferences, 0.312 CPU in 0.312 seconds (100% CPU, 8368596 Lips)
18134

Very nice and for the moment I am very happy with plain Prolog.
Thanks Jan.

The original example is reverted to plain N3 and available at https://github.com/josd/eye/tree/master/reasoning/4color
It runs fine on top of swipl :slight_smile:

Kind regards,
Jos