Modélisons pas à pas ce problème sous forme d’un CSP
Variables (X) :
Chaque région sur la carte est représentée par une variable Xi, où i est le numéro de la région à colorier. Dans ce cas, nous avons 14 régions, donc X = {X1, X2, ..., X14}.
Domaines (D(Xi)) :
Chaque variable Xi peut prendre l'une des 4 couleurs suivantes : bleu, rouge, vert, ou jaune. Ainsi, D(Xi) = {bleu, rouge, vert, jaune} pour toutes les variables Xi.
Contraintes (C) :
Les contraintes représentent les conditions à respecter pour que le coloriage soit valide. Dans ce cas, la contrainte principale est que deux régions voisines (ayant une frontière en commun) ne peuvent pas avoir la même couleur. Nous exprimons cette contrainte en utilisant le prédicat "voisines(Xi, Xj)", qui est vrai si Xi et Xj sont voisines.
Pour formaliser cette contrainte, nous définissons un ensemble C de contraintes :
C = {Xi ≠ Xj | Xi et Xj sont 2 variables différentes de X et voisines(Xi, Xj) = vrai}
Cela signifie que pour chaque paire de variables Xi et Xj qui sont voisines, nous ajoutons une contrainte indiquant que Xi ne peut pas avoir la même couleur que Xj.
Définition du prédicat "voisines(Xi, Xj)" :
Nous pouvons définir le prédicat "voisines(Xi, Xj)" en listant explicitement toutes les paires de régions voisines. Par exemple, si nous avons la paire (1, 7), cela signifie que la région 1 est voisine de la région 7.
Ainsi, l'ensemble des paires de régions voisines est :
{(1,7), (1,9), (1,10), (1,11), (1,12), (1,13), (2,8), (2,12), (2,14), (3,7), (3,10), (3,14), (4,9), (4,11), (4,14), (5,8), (5,11), (5,12), (6,7), (6,13), (6,14), (7,1), (7,3), (7,6), (7,10), (7,13), (7,14), (8,2), (8,5), (8,12), (9,1), (9,4), (9,10), (9,11), (10,1), (10,3), (10,7), (10,9), (10,14), (11,1), (11,4), (11,5), (11,9), (11,12), (12,1), (12,2), (12,5), (12,8), (12,11), (12,13), (12,14), (13,1), (13,6), (13,7), (13,12), (13,14), (14,2), (14,3), (14,4), (14,6), (14,7), (14,10), (14,12), (14,13)}
Ainsi, pour chaque paire (Xi, Xj) dans cette liste, nous ajoutons la contrainte Xi ≠ Xj à C.
Cette modélisation permet de résoudre le problème de coloriage de la carte en utilisant un CSP, en veillant à ce que les régions voisines soient coloriées avec des couleurs différentes. De plus Ce problème de coloriage d'une carte est un cas particulier du problème du coloriage des sommets d'un graphe (deux sommets adjacents du graphe doivent toujours être de couleurs différentes).
