Résolution d'un Kakuro
La modélisation CSP en intelligence artificielle
Le Kakuro
Le Kakuro est un jeu logique que l'on perçoit souvent comme une adaptation numérique des mots croisés. L'objectif du jeu est de remplir les cases vides (blanches) avec des chiffres entre 1 et 9 de sorte que la somme de tous les chiffres d'un nombre soit égale au nombre inscrit dans la case remplie (noire) définissant le nombre, et qu'un nombre ne puisse pas contenir deux fois le même chiffre. Cette dernière règle est celle qui rend possible la création de grilles à solution unique.
Dans le cadre de la spécialité "Intelligence Artificielle", en licence 3 Informatique à la faculté, il nous a été demandé de modéliser, sous la forme d'un CSP, une grille de Kakuro, dans le but d'en trouver les contraintes afin de créer un algorithme de résolution du jeu.
CSP : Problèmes de satisfactions de contraintes
Un CSP (Constraint Satisfaction Problem) est un problème mathématique où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. En utilisant ce principe sur le Kakuro, on a un moyen adapté pour déterminer et gérer toutes les contraintes que peut poser une grille de Kakuro. On pourra ainsi la modéliser et la résoudre correctement en ayant pris en compte toutes les contraintes nécessaires.
- Une liste de variables (les éléments qui composent le problème)
- Un domaine d'association pour chaque variable (ici les chiffres de 0 à 9)
- Une liste de contraintes (qui sont les contraintes du problème)
- Un ensemble de relations de compatibilité
Les contraintes du Kakuro
Il y a deux principales contraintes qui se dégagent d'une grille de Kakuro : la somme des chiffres, qui doit avoir pour résultat le nombre inscrit dans la case initiale de la colonne ou de la ligne; et le fait qu'une somme ne doit pas contenir deux fois le même chiffre (exemple : si le résultat vaut 12 et que l'on a 4 cases alors "3 + 2 + 3 + 4" n'est pas correct car 3 apparaît deux fois).
Le projet
Inachevé par manque de temps, le projet consistait à implémenter deux algorithmes de résolution en C pour résoudre une grille de Kakuro. Il s'agissait d'un algorithme de backtracking et de l'algorithme Forward-Checking. Seul l'algorithme de backtracking a été réalisé. Il est implémenté itérativement et fonctionne avec un système de pile pour exploiter la liste de variables du CSP.
Voici le code :
/***********************************************************
Algorithme backtrack.
Retourne 1 si une solution a été trouvée, 0 sinon.
************************************************************/
int backtrack(GrilleDeJeu jeu, CSP* csp) {
// Compteur de boucle.
int i;
// Pour la prochaine variable à tester.
variable var;
// Vaut 1 si une valeur est consistante.
int consistant = 0;
// Pour la valeur du domaine.
int valeur;
// Tant que la liste des variables du CSP n'est pas vide.
while(csp->V != NULL) {
// Prochaine variable à tester.
var = depiler_var(&(csp->V));
consistant = 0;
// Tant qu'il y a des valeurs dans le domaine de la variable à tester.
while((valeur = domaineVide(var.domaine)) != -1) {
var.domaine[valeur - 1] = 0;
consistant = 0;
// Si la valeur est consistante.
if ((consistant = valeur_consistante(jeu, var, valeur)) == 1) {
// On affecte la valeur consistante à la case correpsondante.
jeu.cases_blanches[var.case_blanche->id].valeur = valeur;
// On met à jour les valeurs des cases associées aux contraintes de somme.
mettreAJourContraintesSomme(var, valeur, &jeu);
// On empile cette affectation dans la liste des affectations.
empiler_debut(&(csp->A), var);
break;
}
}
// Si aucune valeur n'a été consistante.
if (consistant == 0) {
// On remet la valeur de la case à 0
var.case_blanche->valeur = 0;
// Si aucune affectation n'a pu être possible.
if (csp->A == NULL) {
return 0;
}
// Réinitialisation du domaine.
for(i = 0; i < 9; i++) {
var.domaine[i] = 1;
}
// On remet la variable au sommet de la liste.
empiler_debut(&(csp->V), var);
// On remet la variable parcourue au sommet de la liste.
empiler_debut(&(csp->V), csp->A->var);
// On enlève l'affectation actuelle de la liste.
depiler_var(&(csp->A));
}
}
return 1;
}
Le rapport du projet est disponible ci-dessous.