Projet d'Intelligence Artificielle : le Sudoku

Résumé du document

Face au phénomène actuel de la mode du sudoku, nous avons souhaité nous intéresser ici à ce jeu d'un peu plus près, de comprendre son fonctionnement et d'implémenter un programme permettant d'y jouer. Nous allons donc tout d'abord étudier le fonctionnement du sudoku et voir quelles sont les contraintes de jeu et les différentes méthodes permettant de résoudre une grille. Nous verrons ensuite la méthode que nous avons choisi de programmer et pourquoi.

Le sudoku n'est pas un jeu purement mathématique. En effet, il n'existe aucune formule mathématique permettant de trouver la solution d'une grille de sudoku. Le cerveau humain procède par déductions et hypothèses. Programmer ce type de méthode relève donc du domaine de l'intelligence artificielle: domaine d'étude dans lequel s'inscrit ce projet.

La base du sudoku remonte à l'Antiquité, probablement vers 2000 av J-C nommé le « Carré latin ». Un carré latin est un carré n x n dont les cases sont remplies par les mêmes n lettres, en ligne et en colonne. Ce principe mathématique est présent dans la théorie des graphes et a été étudié au XVIIIe siècle par le mathématicien suisse Leonhardt Euler.

Le Sudoku classique est une juxtaposition de 9 carrés latins dont les lettres ont été remplacées par des chiffres. Une grille de sudoku se compose de neuf carrés de 3x3 cases. Au sudoku, ces carrés sont appelés "régions".

Le but du jeu est de compléter la grille afin que chaque ligne, chaque colonne et chaque région contiennent toutes les chiffres de 1 à 9 une fois et une seule.

Depuis un an le jeu connaît un énorme succès, notamment en Grande Bretagne. Les grands quotidiens nationaux comme The Guardian, The Times ou The Independent publient désormais leurs grilles. Les autres pays anglophones s'y sont également mis, le sudoku ayant investi les pages du Times of India, du Sydney Morning Herald ou du Toronto Star. Depuis le mois de juin 2005, le sudoku conquiert le reste de l'Europe.
En France, c'est dans un article paru dans Libération début juin 2005 qu'il fit sa première apparition.

Extraits

[...] La récurrence s'arrêtera lorsque la solution sera trouvée Méthode adoptée pour la génération de grille Afin de générer une grille de Sudoku pour qu'un utilisateur puisse jouer, il faut partir du principe que l'ordinateur doit être capable de résoudre ce qu'il propose. Voila pourquoi le module de résolution a été implémenté avant celui-ci. Pour générer une grille, l'ordinateur génère tout d'abord au hasard une solution complète d'une grille de Sudoku, cette grille sera par la suite appelée masque de résolution. Ensuite celui-ci va enlever des valeurs afin de laisser des cases vides. [...]

[...] Lorsque l'utilisateur rentre une valeur dans la grille de Sudoku et s'il se trompe il peut l'effacer. Par ailleurs le programme vérifie à tout instant que la valeur que l'utilisateur souhaite rentrer n'est pas incohérente ; dans le cas contraire cette valeur ne pourra pas être insérée dans la matrice. Analyse détaillée 1 Analyse des Variables et types 1. Justification de la classe Sudoku Suite à l'étude du problème, la classe la plus adéquate au problème posé est un tableau, regroupant les 81 cases d'une grille de Sudoku. [...]

[...] Si la valeur choisit ne permet pas la résolution de la grille alors on prend les autres possibilités qui s'offraient à nous jusqu'à résolution de la grille La génération d'une grille Caractéristiques : La fonction de génération d'une grille (void Generer_Grille(int niveau)) à pour particularité de générer une grille suivant le niveau de difficulté souhaité. Cette fonction fait appel à 2 sous fonctions : La fonction de résolution d'une grille. La fonction d'ajout d'une valeur dans la grille de jeu. Fonctionnement : Le système de résolution employé par la fonction de résolution permet de résoudre une grille vierge, et donc de générer une solution aléatoire. Une fois la solution aléatoire générée on applique un masque à cette grille de jeu. [...]

[...] Une grille de Sudoku se compose de neuf carrés de 3x3 cases. Au Sudoku, ces carrés sont appelés "régions". Le but du jeu est de compléter la grille afin que chaque ligne, chaque colonne et chaque région contiennent toutes les chiffres de 1 à 9 une fois et une seule. Exemple de grille : La mode du Sudoku Depuis un an le jeu connaît un énorme succès, notamment en Grande Bretagne. Les grands quotidiens nationaux comme The Guardian, The Times ou The Independent publient désormais leurs grilles. [...]

[...] Ces problèmes ont en commun de ne pas avoir de formule mathématique pour en venir à bout. Lorsque le cerveau humain travaille sur ce type de problème, il est amené à utiliser des déductions logiques et à tâtonner La difficulté de ce projet est donc d'implémenter ce type de raisonnement à l'ordinateur Méthode adoptée pour la résolution Première partie : Evolution des contraintes par case et ajout de valeur avec certitude Nous avons choisi dans ce projet d'associer à chaque case du Sudoku un ensemble de valeurs appelées contraintes C'est-à-dire, qu'à chaque case on associe les valeurs potentielles pour celle-ci. [...]