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

Did you try this input, slight reordering:

% map of European Union
neighbours(germany, [netherlands, belgium, luxemburg, denmark, france, austria, poland, czech_republic]).
neighbours(poland, [germany, czech_republic, slovakia, lithuania]).
neighbours(cyprus, [greece]).
neighbours(czech_republic, [germany, poland, slovakia, austria]).
neighbours(denmark, [germany, sweden]).
neighbours(estonia, [finland, latvia, lithuania]).
neighbours(finland, [estonia, sweden]).
neighbours(france, [spain, belgium, luxemburg, germany, italy, united_kingdom]).
neighbours(ireland, [united_kingdom]).
neighbours(italy, [france, austria, slovenia]).
neighbours(latvia, [estonia, lithuania]).
neighbours(lithuania, [estonia, latvia, poland]).
neighbours(luxemburg, [belgium, france, germany]).
neighbours(greece, [bulgaria, cyprus]).
neighbours(hungary, [austria, slovakia, romania, croatia, slovenia]).
neighbours(malta, []).
neighbours(netherlands, [belgium, germany, united_kingdom]).
neighbours(portugal, [spain]).
neighbours(romania, [hungary, bulgaria]).
neighbours(slovakia, [czech_republic, poland, hungary, austria]).
neighbours(slovenia, [austria, italy, hungary, croatia]).
neighbours(austria, [czech_republic, germany, hungary, italy, slovenia, slovakia]).
neighbours(belgium, [france, netherlands, luxemburg, germany, united_kingdom]).
neighbours(bulgaria, [romania, greece]).
neighbours(croatia, [slovenia, hungary]).
neighbours(spain, [france, portugal]).
neighbours(sweden, [finland, denmark]).
neighbours(united_kingdom, [ireland, netherlands, belgium, france]).

It will not find a color for austria:

?- four_color(Country, Color), fail; true.
true.

?- neighbours(Place, _), \+ place(Place, _).
Place = austria
false.

So the greedy algorithm doesn’t work anyway.

:- 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

Since the greedy algorithm doesn’t work, you need somewhere a little backtracking. The backtracking would be needed then when a country cannot be placed.

I don’t know whether ordinary tabling can do that. Also I don’t know whether more advanced tabling, that maybe has negation through wellfound semantics available, could do the necessary backtracking.

Typically answer set programming (ASP) can do the necessary backtracking. Here is an ASP run, that will also place austria, using the same resorted neighbours/2 facts. The ASP program reads:

:- use_module(library(minimal/asp)).

choose([place(Place,red),
        place(Place,green),
        place(Place,blue),
        place(Place,yellow)]) <= neighbours(Place,_), posted(init).
        
fail <= posted(place(Place,Color)), posted(place(Neighbour,Color)),
        neighbours(Place, Neighbours), member(Neighbour, Neighbours).

The second rule might fail, and will cause ASP backtracking which also involves retracting tabled facts, facts that have been tabled in the choose operator, the non-deterministic tabling of ASP.

Here is an example run:

?- post(init), (place(Place,Color), write(Place-Color), nl, fail; true).
germany-red
poland-green
cyprus-red
czech_republic-blue
denmark-green
estonia-red
finland-green
france-green
ireland-red
italy-red
latvia-green
lithuania-blue
luxemburg-blue
greece-green
hungary-red
malta-red
netherlands-green
portugal-red
romania-green
slovakia-yellow
slovenia-blue
austria-green
belgium-yellow
bulgaria-red
croatia-green
spain-blue
sweden-red
united_kingdom-blue
Yes

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

If you use this code instrumentation, you will see
that it now uses backtracking, also with your
input neighbours/2 table.

places([]).
places([Place-Color|Tail]) :-
    places(Tail), 
    (true; write('places was backtracking'), nl, fail),
    neighbours(Place, Neighbours),
    member(Color, [red, green, blue, yellow]),
    \+ (member(Neighbour-Color, Tail), member(Neighbour, Neighbours)).

This is probably because now it starts with last
neighbour and not with the first neighbour as in
your original code. If you run it, you will see the
backtracking as follows:

?- four_color(Places).
places was backtracking
places was backtracking
places was backtracking
places was backtracking
...

If you use the same instrumented code, and if you
change the order, like for example using this
variant with a reverse/2:

four_color(Places) :-
    findall(Place-_, neighbours(Place, _), List),
    reverse(List, Places),
    places(Places).

I don’t see any backtracking anymore. So the
neighbour/2 table was indeed a lucky charm, an
input constelation that didn’t need any backtracking.
I directly get with reverse/1 in place, no indication
of any backtracking by the instrumentation:

?- four_color(Places).
Places = [united_kingdom-blue, sweden-blue, 
spain-blue, slovenia-yellow, slovakia-blue, 
romania-blue, portugal-red, poland-red, ... - ...|...] .

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.

What would be of interest, would be doing the CLP(FD) or the ASP solution in parallel. Both approaches have a generate and test component. The CLP(FD) does a generate and test during labeling. The ASP does a generate and test during choose.

The problem here is that in contrast to parallel streams we can not simply pass a few items through a pipline. So although balance/1 would help, there is the issue that for both CLP(FD) and ASP a model is manipulated. In CLP(FD) the model is usually called the constraint store, and in ASP its the progressing stable model or whatever.

I have a predicate setup_balance/1 which can help here. It simply does make initial copies of the model, and you need to have some generator that then takles subproblems on the initial model, which gets modified through each thread working on a replica of the initial model while trying to solve its subproblem.

This would be quite fun to experiment with. But currently I am busy with aggregates and tabling, to give it some transparent parallelization in the future, having balance/1 underneath. But could also try to make something for CLP(FD) and ASP with setup_balance/1 underneath.

It seems that others are also working on parallel ASP for example:

Parallel Answer Set Programming - Pontelli et al.
http://pcr17.inf.usi.ch/slides/Formisano_PCR17.pdf

Taking notes to myself: Actually in ASP the model intialization is rather a no op. The situation is a little better than in CLP(FD), in ASP the program its just a static disjunctive program with constraints. Not like in CLP(FD) where there is not really a program format.

So for ASP, calling post(init) from different threads will automatically create thread local progressive stable models or whatever.

Even for a parallel streams solution, currently
lack of idea how to define subproblems of
the four colour problem?

For the queens problem its not so difficult, you
can just take one or two queens, and
enumerate their positions,

and then let the threads pick such queen positions,
and let the threads try to complete the problem
with more queens.

1 Like