Pour modéliser ce problème sous la forme d'un CSP, il s'agit d'identifier les variables (les inconnues du problème), les domaines de valeur de ces variables, et les contraintes existant entre ces variables.
Ici, ce que l'on doit déterminer (nos inconnues), c'est la couleur de chaque région. On aura donc une variable pour chaque région, chacune de ces variables pouvant prendre comme valeur une des 4 couleurs.
Les contraintes spécifient que deux régions voisines ne doivent pas être de la même couleur.