/* Faerben von Landkarten */

/* Hauptpraedikat: faerbe(Landkarte,Farben,Farbzuordnung) */
/* Format fuer Landkarte: Liste von Regionen der Form */
/*                        region(Name,Farbe,ListeVonNachbarn) */
/* Als Nachbarbezeichnung dienen nicht die Namen sondern die Farbvariablen. */


faerbe([Region|Restkarte],Farben,[Paar|L]) 
          :- faerbe_region(Region,Farben,Paar), faerbe(Restkarte,Farben,L). 
faerbe([], _Farben,[]).

/* Faerbung einer Region plus Faerbung von Nachbarn mit Restfarben */

faerbe_region(region(Name,Farbe,Nachbarn), Farben,(Name,Farbe))
       :-  select(Farbe,Farben,Restfarben), sublist(Nachbarn,Restfarben).


/* Hilfspraedikate */

select(X,[X|Ys],Ys). 
select(X,[Y|Ys],[Y|Zs]) :-  select(X,Ys,Zs). 

sublist([X|Xs],Ys)  :-  member(X,Ys), sublist(Xs,Ys). 
sublist([],_Ys). 

%member(X,[X|_Xs]).
%member(X,[_Y|Ys]) :- member(X,Ys).

/* Testaufrufe fuer 3 und 4 Farben und die Laenderkarte von Deutschland*/

test3(L) :- 
    faerbe([region(schleswig-holstein,   SH,  [HH,N,MP]), 
            region(hamburg,              HH,  [SH,N]), 
            region(niedersachsen,        N,   [SH,HH,SA,TH,H,NRW,HB]), 
            region(bremen,               HB,  [N]), 
            region(nordrhein-westfalen,  NRW, [N,H,RP]),
            region(hessen,               H,   [NRW,RP,BW,BY,TH]),
            region(rheinland-pfalz,      RP,  [NRW,H,BW,SL]),
            region(saarland,             SL,  [RP]), 
            region(baden-wuerttemberg,   BW,  [RP,H,BY]), 
            region(bayern,               BY,  [H,BW,TH,S]), 
            region(thueringen,           TH,  [H,BY,N,S,SA]), 
            region(sachsen,              S,   [BY,TH,SA,BB]),  
            region(sachsen-anhalt,       SA,  [TH,N,MP,BB,S]), 
            region(brandenburg,          BB,   [B,MP,S,SA]), 
            region(berlin,               B,    [BB]), 
            region(mecklenburg-vorpommern,  MP,  [SH,N,SA,BB])
           ],
           [gruen,weiss,gelb],L).

test4(L) :- 
    faerbe([region(schleswig-holstein,   SH,  [HH,N,MP]), 
            region(hamburg,              HH,  [SH,N]), 
            region(niedersachsen,        N,   [SH,HH,SA,TH,H,NRW,HB]), 
            region(bremen,               HB,  [N]), 
            region(nordrhein-westfalen,  NRW, [N,H,RP]),
            region(hessen,               H,   [NRW,RP,BW,BY,TH]),
            region(rheinland-pfalz,      RP,  [NRW,H,BW,SL]),
            region(saarland,             SL,  [RP]), 
            region(baden-wuerttemberg,   BW,  [RP,H,BY]), 
            region(bayern,               BY,  [H,BW,TH,S]), 
            region(thueringen,           TH,  [H,BY,N,S,SA]), 
            region(sachsen,              S,   [BY,TH,SA,BB]),  
            region(sachsen-anhalt,       SA,  [TH,N,MP,BB,S]), 
            region(brandenburg,          BB,   [B,MP,S,SA]), 
            region(berlin,               B,    [BB]), 
            region(mecklenburg-vorpommern,  MP,  [SH,N,SA,BB])
           ],
           [gruen,weiss,gelb,rot],L).