Limitation : Le programme suppose que le problème à résoudre n'a qu'une seule et unique solution car dans le cas contraire, il est incapable de résoudre le problème.

1. Initialisation

L'initialisation joue un rôle très important car la difficulté du problème réside principalement dans la mise en place d'un systèmes de structures de données permettant ainsi au programme de traiter les données d'entrées. Le systèmes de structures de données comprend :

Un tableau de 80 structure s_Case_jeu

1.1 Initialisation du tableau de structures s_Case_jeu

Définition de la structure s_Case_jeu :

La première étape est de lire le fichier d'entré afin de déterminer le type de chaque case et d'assigner l'information pertinente selon le type de la case dans l'une des deux structures de l'union. De plus, lors de cette opération, la position des cases contenant des sommes est sauvegardée dans la liste de pointeur utilisée à cet effet (l_liste_sommes). Cette étape est effectuée dans la fonction f_init().

La deuxième étape consiste à créer les liens entre les sommes et les cases blanches. Alors pour chaque structure de somme, une liste de pointeurs contenant la position des cases blanches associées à cette somme est créée et pour chaque case blanche les pointeurs des deux sommes associées à cette case sont sauvegardés dans la structure de la case blanche. Cette étape est effectuée dans par la fonction f_init_cases() .

Ensuite, le programme examine la liste des sommes afin de détecter des sommes identiques (même valeur et même nombre de cases blanches). Si des sommes identiques sont détectées alors des liens entres elles seront créés afin de vérifier certaines conditions dans la partie d'élimination des valeurs possibles. Cette étape est effectuée par les fonctions f_init_pareil() et f_set_pareil().

Pour terminer l'initialisation, un ensemble des valeurs possibles pour une somme donnée ainsi qu'une liste d'ensembles discriminatoires sont assignés à chaque somme. Un ensemble discriminatoire est constitué des valeurs qui caractérisent une combinaison de valeurs possibles pour la somme. Ces ensembles sont utilisés dans la deuxième partie du programme. Cette étape est effectuée par les fonctions f_set_discrimset() et la fonction récursive f_set_set().

2. Élimination des valeurs possibles.

L'élimination des valeurs se fait à l'intérieur d'une boucle et le programme en ressort lorsque la valeur de chaque case blanche a été trouvée. La boucle se trouve dans la fonction f_calcul(). Dans cette boucle, le programme calcule l'ensemble des valeurs possibles pour chaque case blanche en trouvant les valeurs communes des ensembles de valeurs possibles des sommes associées à la case blanche en question.

Une fois le calcul de l'ensemble des valeurs possibles calculé, le programme vérifie si la valeur recherchée est trouvée. Si elle l'est, il recalcule les valeurs possibles des sommes en ayant préalablement décrémenté le nombre de cases vides associées aux deux sommes et soustrait la valeur trouvée à la somme recherchée. De plus, une nouvelle liste d'ensembles discriminatoires est créée pour les sommes ayant plus de trois cases. Le besoin de cette nouvelle liste s'explique par le fait que les différentes combinaisons pour une somme de plus de trois cases ne possède pas tous une valeur qui n'apparaît pas dans une autre combinaison. Cette étape s'effectue dans la fonction f_recalcule().

Ensuite, le programme compare l'ensemble des valeurs de la case avec les ensembles discriminants. Si l'ensemble de la case est un sous-ensemble d'un des ensembles discriminants alors cet ensemble est soustrait de l'ensemble des sommes identiques à celle qui est présentement traitée puisque les règles du jeu interdisent l'utilisation de la même combinaison plus d'une fois pour des sommes identiques. Le reste des ensembles discriminants est soustrait à l'ensemble de la somme traitée car la combinaison recherchée est maintenant trouvée. Notez bien que la liste d'ensembles discriminants créée dans l'étape précédente pour les sommes ayant plus de trois case ne peut être utilisée pour éliminer des valeurs dans l'ensemble des sommes identiques car elle n'est valide que pour la somme avec laquelle elle est associée.

Par la suite, chaque valeur de l'ensemble des valeurs possibles d'une case blanche est testée en vérifiant qu'il est possible de parvenir à la valeur de la somme en utilisant cette valeur et les valeurs contenues dans les ensembles des autres cases blanches de cette somme. Si le test est négatif alors cette valeur est éliminée. Les deux dernières étapes sont exécutées dans la fonction f_elimine().

Le programme se termine en écrivant, dans le fichier de sortie, la solution au problème.