Sudoku

Mai 2021

Alexandra Demski

Dépôt Github du projet

Généralités

L'objectif principal du projet est de programmer une application en Java permettant de résoudre et créer des grilles de sudoku. Une version automatique des deux fonctionnalités sera également être intégrée.

Le Projet

Les Fonctionnalités

L'application Sudoku comporte deux fonctionnalités majeures : la résolution de grilles et leur création.

La première fonctionnalité permet de charger des grilles et de les remplir. Lorsqu'un utilisateur pense avoir finit, l'application vérifie si celle-ci est correcte et affiche le message approprié. Il est possible de résoudre automatiquement une grille en choisissant l'option dédiée mais également de la recommencer depuis le début.

La seconde fonctionnalité permet à l'utilisateur de créer ses propres grilles sudoku, stockées sous forme de fichiers à l'extension fichier.gri. Il est possible de lancer la création automatique d'une grille ou de la rendre vierge. Une option supplémentaire permet de vérifier sa cohérence générale.

De part son aspect interactif, l'application s'insère dans une interface cohérente et agréable.

La Structure

Le projet comporte trois dossiers. Le dossier build contient les exécutables permettant de lancer l'application. Le dossier grilles stocke les différentes grilles créées lors de l'utilisation de l'application avec trois fichiers démo déjà présents. Le dernier dossier nommé src contient les fichiers sources du projet, organisés dans différents packages.

L'application implémente le motif d'architecture MVC (Modèle-Vue-Contrôleur) séparant ainsi les fichiers sources en plusieurs packages distincts : ctrl implémente tous les contrôleurs de l'applications, chargés de faire le lien entre les vues et les modèles, gui contient l'interface graphique de l'application dont les fenêtres, les boîtes de dialogues et objets personnalisés comme la grille ou les différentes cases et sudoku stocke les différents objets chargés de modifier les données brutes de l'application.

Pour exécuter le projet, il est possible de passer par le Makefile avec la commande make run cependant, les utilisateurs Windows doivent installer des outils complémentaires pour son utilisation. Le projet est également exécutable par le biais de la commande java -cp "./build" Start. Il est important à noter que dans les deux cas il faut avoir installer au préalable le Java Development Toolkit ou le Java Runtime Environment sans lesquelles les commandes javac et java ne seront reconnues.

Le Code

Sudoku

La classe mère Sudoku intègre les différents fonctions, utiles pour toutes les fonctionnalités liées aux grilles : la recherche de cases vides et la vérification d'une case. Cette dernière fonction vérifie si la valeur présente dans une case est unique dans la colonne, ligne et zone.

public boolean checkCell(int num, int[] positions){
    int i=0,j=0;
    for(i=0;i<=8;i++){//Vérifier la colonne
        if(this.board[positions[0]][i]==num & i!=positions[1]){
            return false;
        }
    }
    for(i=0;i<8;i++){//Vérifier la ligne
        if(this.board[i][positions[1]]==num & i!=positions[0]){
            return false;
        }
    }
    int x = positions[0]-positions[0]%3;
    int y = positions[1]-positions[1]%3;
    for(i=x;i<x+3;i++){//Vérifier le carré
        for(j=y;j<y+3;j++){
            if(this.board[i][j]==num & i!=positions[0] & j!=positions[1]){
                return false;
            }
        }
    }
    return true;
}

Résolution Automatique

La résolution automatique est implémentée dans le fichier SolveSudoku à l'aide de la fonction solve.

L'algorithme de résolution tourne tant que la grille ne possède plus de cases vides, signifiant qu'elle est résolue.

Lorsqu'une case vide est trouvée, on essaye de la remplir : on vérifie pour chaque valeur possible si la grille reste toujours cohérente. Lorsqu'on a trouvé une telle valeur, on rappelle la méthode pour remplir la case d'après. Lorsqu'on ne trouve pas de valeur, la grille n'est plus cohérente et une case précédente est fausse, ainsi on la remet à 0 pour reculer la complétion.

xxxxxxxxxx
public boolean solve(){
    int[] empty = new int[2];
    while(true){
        empty = findEmtpy();
        if(empty==null){//On a trouvé aucune case vide
            return true;
        }
        else{//On a trouvé des cases vides
            int row=empty[0];
            int col=empty[1];
            int value;
            boolean valid;
            for(value=1;value<=9;value++){//On teste les valeurs allant de 1 à 9
                valid=checkCell(value,empty);
                if(valid){
                    this.board[row][col]=value;
                    if(solve()){
                        return true;
                    }
                    //Si on ne peut plus résoudre le sudoku, on remet la dernière case à 0 et on recule.
                    this.board[row][col]=0;
                }
            }
            return false;
        }
    }
}

Création Automatique

La création de grille automatique, implémentée dans la classe CreateSudoku se base sur sa résolution : l'algorithme résout la grille et efface un certain nombre de cases pour la rendre jouable. Cependant, pour rendre les grilles de sudoku uniques, il est important de modifier l'ordre de vérification des valeurs, représentée par un Pattern, ainsi on augmente le nombre de grilles possibles.

​x
public void create(){
    solveRandom();//Résolution avec un pattern aléatoire
    int count;//Décompte des cases effacées
    int fill = (int)(Math.random()*6)+17; //valeur aléatoire entre 17 et 17+5 = 22 de cases à garder
    int empty=80-fill;//Nombre totales de cases à effacer
​
    //Tant qu'on a pas effacé assez de cases
    for(count=0;count<empty;count++){
        eraseCell();//On continue
    }
}

Gestion de Fichier

La gestion des fichiers est définie dans la classe SudokuManager qui contient deux méthodes : save et read. Les deux fonctions ouvrent un DataStream en entrée ou en sortie puis convertissent ou traduisent chaque ligne de la grille en valeur numérique. Il est important d'indiquer les différentes erreurs possibles lors de ma lecture ou écriture d'un fichier, ainsi, selon le résultat final, les fonctions retournent une valeur numérique différente.

xxxxxxxxxx
public int read(int[][] b, String n){
    this.board = b;
    this.fileName = n;
    try{
        //Ouverture d'un fichier
        DataInputStream inputStream = new DataInputStream(new FileInputStream("./grilles/" + this.fileName));
        for(int i=0;i<=8;i++){
            int rowNumbers = inputStream.readInt();//Récupération de la ième ligne dans un Integer
            String row = Integer.toString(rowNumbers);//Conversion de la ligne en String
            int length = row.length()-1;
            for(int j=8;j>=0;j--){
                if(length<0){
                    this.board[i][j]=0;
                }
                else{
                    this.board[i][j]=Character.getNumericValue(row.charAt(length));
                    length--;
                }
            }
        }
        inputStream.close();//Fermeture du fichier
        return 1;
    } catch(FileNotFoundException ex) {
        return -1;//Si le fichier n'existe pas     
    } catch(IOException ex) {
        return -2;//Si la lecture échoue              
    }

xxxxxxxxxx
public int save(int[][] b, String n){
    this.board = b;
    this.fileName = n;
    try{
        //Ouverture/Création d'un fichier .gri
        DataOutputStream outputStream = new DataOutputStream(new FileOutputStream("./grilles/" + this.fileName + ".gri"));
        for(int i=0;i<=8;i++){
            String row = new String();
            for(int j=0;j<=8;j++){
                row=row+this.board[i][j];
            }
            int rowNumbers = Integer.parseInt(row,10);//Conversion du String vers un Integer
            outputStream.writeInt(rowNumbers);//Ecriture dans le fichier
        }
        outputStream.close();//Fermeture du fichier et indication de la réussite
        return 1;
    } catch(IOException ex) {
        return -1;//Si l'écriture échoue
    } catch(NumberFormatException ex) {
        return -2;//Si la conversion échoue
    }

Interface Graphique

Les fenêtres

L'interface graphique comprend trois fenêtres distinctes : StartFrame, CreateFrame et SolveFrame. Chacune implémente les objets nécessaires et les répartie grâce à la mise en page GridBagLayout proposant une personnalisation efficace.

Les fonctionnalités

Chaque bouton, relié à une fonctionnalité, comporte un ActionListener dédié. Ils font partis du package ctrl :

xxxxxxxxxx
package ctrl;
import object; //Import de différents packages
​
public class Controller implements ActionListener{
​
    private type attribut; //Potentiel attribut
    public Controller(type attribut, JButton btn){
        //Initialisation
        btn.addActionListener(this);//Ajout du listener
    }
    @Override
    public void actionPerformed(ActionEvent e){
        //Action
    }
}

Lorsqu'une fonctionnalité est jugée critique, elle est confirmée à l'aide d'une boîte de dialogue JOptionPane.showConfirmDialog().

La sauvegarde de grille passe par un JOptionPane.showInputDialog() afin d'obtenir le nom du fichier.

Le choix de fichier à importer se fait par le biais de la classe ChooseDialog qui hérite d'un JFileChooser.

La grille

Une grille de sudoku est représentée à l'aide d'un JPanel utilisant un GridLayout. Cette représentation est implémentée dans la classe Grille.

En se basant sur le modèle de la grille, un tableau d'entier à deux dimensions, la classe Grille crée deux sortes de boutons : des NumberCell lorsque la case possède déjà une valeur, qui sont des boutons non-cliquables, et des EmptyCell qui, par défaut, seront vides mais modifiables.

Pendant la résolution ou la création d'une grille, le joueur doit sélectionner un chiffre qui sera enregistré dans le singleton NumberMemo. Son unique but est de garder en mémoire le dernier chiffre sélectionné et de retourner la même instance. Lorsqu'un chiffre et une case modifiable sont sélectionnés, la case changera de valeur.

La création et résolution automatique de la grille nécessite une fonction à part qui va mettre à jour toutes les cases vides :

xxxxxxxxxx
public void updateGrille(){
    for (Iterator<EmptyCell> i = this.vides.iterator(); i.hasNext();){//Itération d'une liste de cases vides
        EmptyCell e = i.next();
        int x = e.getCoordsX();//Récupération coordonnées
        int y = e.getCoordsY();
        e.setValeur(this.grille[x][y]);//Mise à jour selon le modèle
    }
}

La remise à neuf d'une grille passe également par une méthode à part :

xxxxxxxxxx
public void restartGrille(){
    for (Iterator<EmptyCell> i = this.vides.iterator(); i.hasNext();){//Itération d'une liste de cases vides
        EmptyCell e = i.next();
        e.setValeur(0);//Remise à 0 de la vue
        int x = e.getCoordsX();//Récupération des coordonnées
        int y = e.getCoordsY();
        this.grille[x][y] = 0;//Remise à 0 du modèle
    }
}