color.trig

# ------------
# 4 Color test
# ------------
#
# See https://en.wikipedia.org/wiki/Four_color_theorem

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.
@prefix list: <http://www.w3.org/2000/10/swap/list#>.
@prefix log: <http://www.w3.org/2000/10/swap/log#>.
@prefix var: <http://www.w3.org/2000/10/swap/var#>.
@prefix : <http://example.org/#>.

# map of European Union
:Belgium :neighbours (:France :Netherlands :Luxemburg :Germany).
:Netherlands :neighbours (:Belgium :Germany).
:Luxemburg :neighbours (:Belgium :France :Germany).
:France :neighbours (:Spain :Belgium :Luxemburg :Germany :Italy).
:Germany :neighbours (:Netherlands :Belgium :Luxemburg :Denmark :France :Austria :Poland :Czech_Republic).
:Italy :neighbours (:France :Austria :Slovenia).
:Denmark :neighbours (:Germany).
:Ireland :neighbours ().
:Greece :neighbours (:Bulgaria).
:Spain :neighbours (:France :Portugal).
:Portugal :neighbours (:Spain).
:Austria :neighbours (:Czech_Republic :Germany :Hungary :Italy :Slovenia :Slovakia).
:Sweden :neighbours (:Finland).
:Finland :neighbours (:Sweden).
:Cyprus :neighbours ().
:Malta :neighbours ().
:Poland :neighbours (:Germany :Czech_Republic :Slovakia :Lithuania).
:Hungary :neighbours (:Austria :Slovakia :Romania :Croatia :Slovenia).
:Czech_Republic :neighbours (:Germany :Poland :Slovakia :Austria).
:Slovakia :neighbours (:Czech_Republic :Poland :Hungary :Austria).
:Slovenia :neighbours (:Austria :Italy :Hungary :Croatia).
:Estonia :neighbours (:Latvia).
:Latvia :neighbours (:Estonia :Lithuania).
:Lithuania :neighbours (:Latvia :Poland).
:Bulgaria :neighbours (:Romania :Greece).
:Romania :neighbours (:Hungary :Bulgaria).
:Croatia :neighbours (:Slovenia :Hungary).

# rules
_:bng_1 log:isImpliedBy _:bng_2.

_:bng_1 {
    var:MAP :color var:PLACES.
}

_:bng_2 {
    ((var:PLACE var:X) _:bng_3 var:PLACES) log:collectAllIn var:SCOPE.
    var:PLACES :places true.
    [] rdf:value true; log:callWithCut true.
}

_:bng_3 {
    var:PLACE :neighbours var:Y.
}

_:bng_4 log:isImpliedBy true.

_:bng_4 {
    () :places true.
}

_:bng_5 log:isImpliedBy _:bng_6.

_:bng_5 {
    var:PLACES :places true.
}

_:bng_6 {
    var:PLACES list:firstRest ((var:PLACE var:COLOR) var:TAIL).
    var:TAIL :places true.
    var:PLACE :neighbours var:NEIGHBOURS.
    (:red :green :blue :yellow) list:member var:COLOR.
    (1 _:bng_7 ()) log:collectAllIn var:SCOPE.
}

_:bng_7 {
    var:TAIL list:member (var:NEIGHBOUR var:COLOR).
    var:NEIGHBOURS list:member var:NEIGHBOUR.
}

# query
_:bng_8 log:query _:bng_8.

_:bng_8 {
    :mapEU :color var:PLACES.
}