
/*
 Description du problème

Il faut de colorier les 14 régions de la carte ci-dessous, de sorte que deux régions ayant une frontière en commun soient coloriées avec des couleurs différentes. On dispose pour cela des 4 couleurs suivantes : bleu, rouge, jaune et vert.   

 Formalisation du problème sous la forme : CSP (X,D,C) 

X = {X1, X2, ..., X14} 
(On associe une variable Xi différente par région i à colorier.) 
pour tout Xi élément de X, D(Xi) = { bleu, rouge, vert, jaune } -> {1,2.3.4}
(Chaque région peut être coloriée avec une des 4 couleurs.)
C = { Xi \= Xj / Xi et Xj sont 2 variables différentes de X et voisines(Xi,Xj) = vrai }
où voisines/2 est un prédicat tel que voisines(X,Y) est vrai si X et Y sont deux régions voisines. 

Appel :
carte(?variable, +liste_d_options)
Description :
carte(L,O) réussit si
L s'unifie avec la liste des couleurs pour chacune des 14 régions,
La liste des options pour le prédicat fd_labeling/2 (voir le point 3 de la session 5 ou le manuel Gnu-Prolog). Ces options vous permettront de spécifier l'ordre d'affectation des variables.
Exemple d'exécution de carte/2 : Pour chercher une solution au problème, sans heuristique particulière, on exécutera
| ?- carte(A,[backtracks(B)]).
A = [1,1,1,1,1,1,2,3,2,3,3,2,3,4]
B = 4 ?
yes
La liste A indique qu'il faut colorier les régions 1 à 6 avec la couleur 1, les régions 7, 9 et 12 avec la couleur 2, les régions 8, 10, 11 et 13 avec la couleur 3 et la région 14 avec la couleur 4. Pour trouver cette première solution, Prolog a effectué 4 retours-arrières.
Pour chercher une solution au problème en utilisant l'heuristique "échec d'abord", on exécutera

| ?- carte(A,[variable_method(first_fail),backtracks(B)]).
A = [1,1,1,1,1,1,2,3,2,3,3,2,3,4]
B = 0 ?
yes
Prolog trouve la même solution... mais sans effectuer un seul retour-arrière.
Pour chercher toutes les solutions au problème (sans les afficher), et compter le nombre total de retour-arrières effectués, on exécutera


| ?- findall(B,carte(A,[variable_method(first_fail),backtracks(B)]),L), length(L,Nb_solutions), sum_list(L,Nb_backtracks).
L = [0,1,1,1,...]
Nb_solutions = 1968
Nb_backtracks = 1967
(10 ms) yes
Dans ce cas, Prolog effectue 1967 retour-arrières pour calculer les 1968 solutions...
*/
voisins(1,7).
voisins(1,10).
voisins(1,9).
voisins(1,11).
voisins(1,12).
voisins(1,13).
voisins(2,8).
voisins(2,12).
voisins(2,14).
voisins(3,14).
voisins(3,7).
voisins(3,10).
voisins(4,14).
voisins(4,9).
voisins(4,11).
voisins(5,11).
voisins(5,12).
voisins(5,8).
voisins(6,7).
voisins(6,14).
voisins(6,13).
voisins(7,13).
voisins(7,10).
voisins(7,14).
voisins(8,12).
voisins(9,10).
voisins(9,11).
voisins(10,14).
voisins(11,12).
voisins(12,13).
voisins(12,14).
voisins(13,14).

carte(L,Options) :-
        length(L,14),
        fd_domain(L,1,4),
        poseContraintes(1,L),
        fd_labeling(L,Options).

poseContraintes(_,[]).
poseContraintes(I,[XI|L]) :-
        findall(J,voisins(I,J),Lvoisins),
        poseContraintes(I,XI,Lvoisins,L),
        Iplus1 is I+1,
        poseContraintes(Iplus1,L).

poseContraintes(_,_,[],_).
poseContraintes(I,XI,[J|Lvoisins],L) :-
        JmoinsI is J-I,
        nth(JmoinsI,L,XJ),
        XI #\= XJ,
        poseContraintes(I,XI,Lvoisins,L).
