<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Coloriage Objectif : colorier une carte de la Suisse et des pays limitrophes. Démarche : * générer tous les coloriages possibles * établir un réseau de contraintes "dif" * appliquer à la carte de la suisse </div> <div class="nb-cell program" data-background="true" data-singleline="true" name="p1"> :- use_module(library(dif)). % Sound inequality %:- use_module(library(clpfd)). % Finite domain constraints %:- use_module(library(clpb)). % Boolean constraints %:- use_module(library(chr)). % Constraint Handling Rules %:- use_module(library(when)). % Coroutining %:- use_module(library(clpq)). % Constraints over rational numbers </div> <div class="nb-cell markdown" name="md2"> ## Générer tous les coloriages On se fixe les 7 couleurs de l'arc-en-ciel pour faire le coloriage (rouge, orange, jaune, vert, bleu, indigo et violet). On prend un liste de pays quelconque, [A, B, C] pour 3 pays, par exemple. On veut trouver tous les coloriages possibles (7*7*7 possibilités, avec par exemple [rouge,rouge,rouge] en premier). </div> <div class="nb-cell program" data-background="true" name="p2"> couleur(rouge). couleur(orange). couleur(jaune). couleur(vert). couleur(bleu). couleur(indigo). couleur(violet). </div> <div class="nb-cell query" name="q1"> couleur(A). </div> <div class="nb-cell program" data-background="true" name="p3"> coloriagePossible([]). coloriagePossible([E|L]):- couleur(E), coloriagePossible(L). </div> <div class="nb-cell query" name="q2"> coloriagePossible([A,B,C]). </div> <div class="nb-cell markdown" name="md3"> ## Réseau de contraintes tous différents Pour 3 variables A, B, C, il s'agit de mettre en place les contraintes A<>B, A<>C, B<>C (et éventuellement les symétriques), c'est à dire pour N pays, N*(N-1) (éventuellement /2) contraintes dif. </div> <div class="nb-cell program" data-background="true" name="p4"> differentDesAutres(_X,[]). differentDesAutres(X,[E|L]):- dif(X,E), differentDesAutres(X,L). </div> <div class="nb-cell query" name="q3"> differentDesAutres(X,[]). </div> <div class="nb-cell program" data-background="true" name="p6"> tousDifferents([]). tousDifferents([E|L]):- differentDesAutres(E,L), tousDifferents(L). </div> <div class="nb-cell query" name="q4"> tousDifferents([A,B,C,D]). </div> <div class="nb-cell markdown" name="md4"> ## Application à la carte de la Suisse et des pays limitrophes Pour différencier les pays limitrophes, il faut prendre des couleurs différentes, le plus simple serait de prendre autant de couleur que de pays, mais on peut faire mieux, par contre localement il faut des couleurs différentes à chaque fois que 2 pays ou plus se touchent. </div> <div class="nb-cell program" data-background="true" name="p5"> coloriage([S,F,Al,I,Au,L]):- tousDifferents([S,F,Al]), tousDifferents([S,Al,Au]), tousDifferents([S,Au,L]), tousDifferents([S,Au,I]), tousDifferents([S,I,F]), coloriagePossible([S,F,Al,I,Au,L]). </div> <div class="nb-cell query" name="q5"> coloriage([Suisse,France,Allemagne,Italie,Autriche,Liechtenstein]). </div> <div class="nb-cell markdown" name="md5"> conclusion : il suffit de trois couleurs (et avec 2, ce n'est pas possible) </div> </div>