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
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
:- 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
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
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.
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
Kind regards,
Jos