Cours CNAM par J. Laforgue

Exercice08_Sudoku

Retour

Télécharger

Exercice sur la resolution d'un sudoku

EnonceExercice08.pdf

Exercice08.java

// Exercice sur la resolution d'un sudoku
//

// Definition de la case de la grille de Sudoku
// ===================================================
class Case
{
    int val;       // Valeur entre 0 et 9 (si 0 alors case vide)
    boolean fixe;  // La valeur est fixe (grille de départ)
}

// Definition de la grille de Sudoku
// ===================================================
class Grille
{
    Case[][] grille;  // La grille (tableau a 2 dimension de Case)

// Constructeur
    public Grille()
    {
        // Creation de la grille
        grille = new Case[9][9];
    }

// Affiche la grille a l'ecran
    public void afficher()
    {
        for(int l=0;l<9;l++){
            for(int c=0;c<9;c++)
                System.out.print(grille[l][c].val+" ");
                System.out.println();
        }
        System.out.println("-------------------------------");
    }

// Algorithme de resolution d'une grille de Sudoku
    // L'algorithme s'arrete a la 1ere solution trouvee
    //
    public void resoudre()
    {
        boolean fini = false;
        int p=0;  // Parcours de la 1ere case (en haut a gauche) jusqu'a la
        // derniere case (en bas a droite) avec un parcours de gauche a droite
        // et de haut en bas 
        // 
        while(!fini){
            // Si la case courante est fixe alors passer a la suivante
            if (fixe(p)) 
                {
                    if (p==80) fini=true; // On est sur la derniere case
                    // on arrete
                    else p++; // case suivante
                }
            else {
                // Si la case contient la valeur 9, il faut revenir en arriere
                if (val(p)==9){
                    val(p,0);
                    if (p==0) fini=true;
                    else
                        {
                            p--;
                            while ( (p>=0) && (fixe(p))) p--;
                            if (p<0) fini=true;
                        }
                }
                // sinon on incremente la valeur de la case, et si elle est
                //  valide on passe a la suivante sinon rien
                else{
                    val(p,val(p)+1);
                    if (valide(p)){
                        if (p==80) fini=true;
                        else p++;
                    }
                }
            }
        }
    }

// Dans les methodes qui suivent, la position p est un entier de 0 à 80
    // qui est le rang de la case dans la grille suivant un parcours de 
    // gauche a droite et de haut en bas

// Retourne la valeur de la case se trouvant a la position p
    private int val(int p){
        return grille[p/9][p%9].val;
    }
    // Change la valeur de la case se trouvant a la position p
    private void val(int p,int v){
        grille[p/9][p%9].val=v;
    }
    // Retourne si fixe ou non de la case se trouvant a la position p
    private boolean fixe(int p){
        return grille[p/9][p%9].fixe;
    }

// Teste si la valeur de la case se trouvant a la position p est valide
    // C est a dire s'il n'existe pas une meme valeur dans la ligne, ou la
    // colonne, ou le bloc 3x3
    //
    private boolean valide(int p)
    {
        // Conversion de la position en coordonnees dans la grille
        int l = p/9; 
        int c = p%9;

// La valeur a tester
        int v=grille[l][c].val;
        
        // Teste sur la ligne
        for(int i=0;i<9;i++)
            if ( (i!=c)&&(grille[l][i].val==v) ) return false;

// Teste sur la colonne
        for(int i=0;i<9;i++)
            if ( (i!=l)&&(grille[i][c].val==v) ) return false;

// Teste dans le bloc 3x3
        for(int i=(l/3)*3;i<(l/3)*3+3;i++)
            for(int j=(c/3)*3;j<(c/3)*3+3;j++)
                if ( ( (i!=l) || (j!=c) ) && (grille[i][j].val==v) ) return false;
        
        // Pour tracer le deroulement de la resolution
        // afficher();
        // Pour debuguer pas a pas
        //Terminal.lireString();

return true;
    }
    
}

// Programme principal
public class Exercice08
{
    /** méthode principale de l'exercice */
    public static void main(String... args)
    {
        // Creation de la grille de sudoku
        Grille sudo = new Grille();

if (args.length ==1)
            {
                // Initialisation de la grille avec celle en entree
                // La valeur en entree est 1 chaine de caractere dont chaque
                // caractere est la valeur d'une case
                //
                int l=0;
                int c=0;
                for(int k=0;k<81;k++)
                    {
                        sudo.grille[l][c] = new Case();
                        sudo.grille[l][c].val=Integer.parseInt(args[0].charAt(k)+"");
                        if (sudo.grille[l][c].val!=0) sudo.grille[l][c].fixe=true;
                        
                        if ((c!=0)&&(c%8==0)){l++;c=0;}
                        else c++;
                    }
            }
        else
            {
                int l=0;
                int c=0;
                for(int k=0;k<81;k++)
                    {
                        sudo.grille[l][c] = new Case();
                        sudo.grille[l][c].val=0;
                        sudo.grille[l][c].fixe=false;
                        
                        if ((c!=0)&&(c%8==0)){l++;c=0;}
                        else c++;
                    }
            }

// Si pas de parametre alors la grille initiale est vide.

// Affichage de la grille d'entree
        sudo.afficher();

// Resolution de la grille
        sudo.resoudre();

// Affichage de la solution
        sudo.afficher();
    }
}

Terminal.java

import java.io.*;

public class Terminal{    
    static BufferedReader in =
        new BufferedReader(new InputStreamReader(System.in));

public static String lireString() // Lire un String
    {
        String tmp="";
        char C='\0';
        try {
            tmp = in.readLine();
        }
        catch (IOException e)
            {
                exceptionHandler(e);
            }
        return tmp;
    } // fin de lireString()
    public static int lireInt()  // Lire un entier
    {
        int x=0;
        try {
            x=Integer.parseInt(lireString());
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return x ;
    }
    public static boolean lireBoolean()  // Lire un entier
    {
        boolean b = true;
        try {
            b = Boolean.valueOf(lireString()).booleanValue();
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return b;
    }
    public  static double lireDouble()  // Lire un double
    {
        double x=0.0;
        try {
            x=Double.valueOf(lireString()).doubleValue();
        }
        catch (NumberFormatException e) {
            exceptionHandler(e);
        }    
        return x ;
    }
    public  static char lireChar()  // Lire un caractere
    {
        String tmp=lireString();
        if (tmp.length()==0)
            return '\n';
        else 
            {
                return tmp.charAt(0);
            }
    }
    public static void ecrireString(String s){ // Afficher un String
        try{
            System.out.print(s);
        } catch (Exception ex){
            exceptionHandler(ex);
        }
    }
    public static void ecrireStringln(String s) // Afficher un String
    {
        ecrireString(s);
        sautDeLigne();
    } // fin de ecrireStringln()
    public static void ecrireInt(int i)  // Afficher un entier
    {
        ecrireString(""+i);
    }
    public static void ecrireIntln(int i)  // Afficher un entier
    {
        ecrireString(""+i);
        sautDeLigne();
    }
    public static void ecrireBoolean(boolean b){
        ecrireString(""+b);
    }
    public static void ecrireBooleanln(boolean b){
        ecrireString(""+b);
        sautDeLigne();
    }
    public  static void ecrireDouble(double d)  // Afficher un double
    {
        ecrireString(""+d);
    }
    public  static void ecrireDoubleln(double d)  // Afficher un double
    {
        ecrireDouble(d);
        sautDeLigne();
    }
    public  static void ecrireChar(char c)  // Afficher un caractere
    {
        ecrireString(""+c);
    }  
    public  static void ecrireCharln(char c)  // Afficher un caractere
    {
        ecrireChar(c);
        sautDeLigne();
    }
    public static void sautDeLigne(){
        try{
            System.out.println();
        }catch(Exception ex){
            exceptionHandler(ex);
        }
    }
    protected static void exceptionHandler(Exception ex){
        TerminalException err = new TerminalException(ex);
        throw err;
    }
    public static void ecrireException(Throwable ex){
        ecrireString(ex.toString());
        ex.printStackTrace(System.err);
    }
}  
class TerminalException extends RuntimeException{
    Exception ex;
    TerminalException(Exception e){
        ex = e;
    }
}

      compil.bat
      run1.bat
      run2.bat
      runVide.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Télécharger

Cours d'Informatique
par Jacques LAFORGUE