1

LE SUDOKU PROJET PARCOURS GSI

BLANC Nicolas – BRABANT Benjamin – PLANTE Timothée

2 Objectifs et Organisation

3

Objectifs

Réalisation d’une interface graphique permettant de jouer au Sudoku

Mise en place des algorithmes de génération et de résolution d’une grille

Ajout d’options en ligne de commandes pour générer et résoudre des fichiers de grilles

Pérennité des données sous forme de fichiers textes formatés

4

Organisation

Jour 1 Analyse du problème, mise en place du modèle de

données et première ébauche d’interface graphique Jour 2

Finalisation de l’interface graphique, début de réflexion sur un algorithme de génération par famille

Jour 3 Mise en place des options en ligne de commandes et

implémentation de la première IA de résolution Jour 4

Finalisation de l’interface, implémentation d’un solveur optimisé et mise en place de divers tests

5 Architecture

6

Organisation des fichiers

|-- build : généré à la compilation -- classes : contient le bytecode java

|-- build.xml : fichier de génération ant |-- README.txt : fichier d’instructions |-- release : dossier des éléments de distribution

|-- jar : contient les archives jar |-- ressources : dossier des ressources externes

|-- files : dossier des fichiers de chargement Sudoku |-- images : images du projet

7

Structure du modèle

Architecture MVC (Modèle Vue Contrôleur) et pattern Observer pour la relation Modèle-Vue

Classe centrale Sudoku contenant une instance de MoteurJeu contenant la grille de jeu accessible partout

Classe ModeleGrille subdivisée en ModeleZone et en ModeleCase

Classes SolveurClassique, SolveurOptimise et Generateur permettant une génération et résolution externe à ModeleGrille

8

Diagramme de classe

9IA - Génération et Résolution

10

Solveur Classique (obsolète)

Construire la liste des valeurs possibles pour les cases vides (en ligne, colonne, zone)

FAIRE Choisir une case dont la cardinalité des valeurs possibles est

minimale Choisir/affecter une valeur parmi les valeurs possibles pour

la case Mettre à jour les valeurs possibles des autres cases vides,

enlever la valeur de cette case SI une intersection modifiée est devenue vide ALORS

Erreur -> retour au point de choix FIN SI

TANT QUE il reste encore une case vide

11

Solveur Optimisé

Algorithme première partie : Restriction des valeurs possibles par lignes

colonnes et zones, Pour chaque case vide, s’il n’y a qu’une seule

valeur possible, on lui affecte cette valeur, Première vérification: pour chaque cases, si la

case est vide n’a pas de valeur possible, ou si la case n’est pas vide et sa valeur n’est pas parmi les valeurs possibles, la grille actuelle n’est pas possible

12

Solveur Optimisé

Algorithme deuxième partie :

Pour chaque case vide, si une des possibilités de la case est unique sur la ligne, la colonne et la zone, on affecte cette valeur à la case.

13

Solveur Optimisé

Algorithme troisième partie : Si la grille est bloquée, on prend une case qui

possède le moins de valeurs possibles, on choisit une valeur et on essaie de finir la grille avec cette valeur. Si on arrive à une contradiction on revient en arrière et on prend une autre valeur possible.

On répète ces opérations jusqu’à la résolution de la grille, ou de son impossibilité

14

Solveur Optimisé

En résumé : Utilise la notion d’arbre, Rapidité due à l’utilisation d’un tableau

statique à deux dimensions de vecteurs d’entiers

Permet d’accéder à tout moment aux valeurs possibles pour une case donnée de la grille.

15

Génération par famille (obsolète)

Sélection Pivot

Famille valide

Ajout Compatible

Détection de boucle infinie

16

Génération

Génération Aléatoire

Gestion de ModeleGrille résolue

Suppression de valeurs

17

Performances finales

Résolution : 250 ms Résolution + Création : 360 ms Programme : 740 ms Résolution sûre

AI Escargot : 55 ms

Blanc Nicolas – Brabant Benjamin – Planté Timothée

18 Pérennité et Ligne de Commandes

Blanc Nicolas – Brabant Benjamin – Planté Timothée

19

Pérennité des données

Stockage des grilles sous forme de fichiers texte contenant une succession de ligne de la forme :

<d> <d> <d> <d> <d> <d> <d> <d> <d> Avec <d> un entier entre 0 et 9

Possibilité de lecture d’un fichier contenant une succession de grilles et détection des grilles erronées

Assouplissement des contraintes au niveau des espacements des caractères et des caractères de fin de ligne

Gestion des erreurs liées à la lecture et l’écriture de données sur disque.

20

Ligne de commande

Gestion d’options par ligne de commande Aucune option saisie : lancement interface graphique -rc <fichier_entree> : résolution classique des grilles

valides de fichier_entree et affichage console -ro <fichier_entree> : résolution optimisée des grilles

valides de fichier_entree et affichage console -g : génération d’une grille et affichage console -g <nb> : génération de nb grilles et affichage

console Possibilité de rediriger la sortie console vers un

fichier texte contenant les grilles générées ou résolues : -f <fichier_sortie> : écriture des résultats dans

fichier_sortie et désactivation de l’affichage console

21

« C’est un jeu. Ce fût des larmes, de la sueur et du développement ! »

Aperçu du programme

22 Interface graphique

23

Menu Principal

Au lancement de l’application (sans saisie d’options) , affichage du menu principal laissant les choix : Nouvelle partie Charger partie Quitter

24

Nouvelle Partie – Charger Partie

25

Valeurs Identiques

En cliquant une valeur initiale (et non modifiable) de la grille, affichage en surbrillance verte de toutes les valeurs identiques de la grille

26

Famille de valeurs

En cliquant une valeur modifiable de la grille, en plus, affichage en surbrillance rouge de toutes les valeurs non nulles de la ligne, colonne et zone de la case sélectionnée

27

Résolution

Le clic sur le bouton résoudre remplace les valeurs modifiables de la grille quelquesoit celles saisies par l’utilisateur.

L’icône « validée » permet de bien constater que la grille est juste

28 Commandes Shell

29

Résolution classique

30

Résolution optimisée

31

Génération

32 Conclusion

Une architecture MVC respectée au maximum Une génération et résolution par lecture de fichier en ligne de commande robuste Une IA optimale résolvant tout type de grille en un temps inférieur à la seconde Un modèle complet mais peu optimisé pour les calculs

33

LE SUDOKU PROJET PARCOURS GSI

Blanc Nicolas – Brabant Benjamin – Planté Timothée

Questions ?