Generateur de grilles de sudoku resolues

Soyez le premier à donner votre avis sur cette source.

Vue 9 331 fois - Téléchargée 748 fois

Télécharger le projet
Commenter

Description

Voici ma première source en C#, un simple générateur de grilles de sudoku résolues.
Ce programme peut être une base de commencement pour certains qui voudraient créer leur propre jeu de sudoku.
L'algorithme utilisé est celui du backtracking (possibilité de revenir en arrière si il y a blocage à un certain moment dans l'algorithme).
Algorithme :
On pointe sur une case de la grille.
S'il y a des solutions possibles pour la case, on en choisit une.
Si il n'y a plus de solutions possibles pour la case, on backtrack (on pointe sur la case précédente pour en modifier la valeur).
Après avoir choisit la valeur pour la case, on rappel la fonction de backtracking en pointant sur la case suivante.

Source / Exemple : 


//classe Grille
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    class Grille
    {
    	//attributs
        private Case[,] grille;
		//constructeur
        public Grille(){
            //on initialise la grille avec un tableau 2 dimensions 9 par 9 avec des objets Case
            initGrille();
            //on remplit la grille initialisée
            remplirBacktrack(0, 'n');
         }
		//methode pour initialiser la grille
        private void initGrille(){
            //on initialise la grille avec un tableau(9,9) d'objet Case
            grille = new Case[9,9];
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    grille[i, j] = new Case();
                }
            }
        }

        //fonction RECURSIVE pour remplir la grille en utilisant l'algorithme de backtrack
        private void remplirBacktrack(int position, char param){
            //on verifie si on n'est pas au bout de la grille :
            if (position >= 81) return;
            int ligne, col, nb;
            bool checkCol, checkRow, checkSquare, checkTab, tabFull;
            bool p = false;
            bool[] tabValeurCase = new bool[9];
            Random rnd = new Random();
            //on recupere le numero de ligne et de colonne
            //en fonction de la position :
            ligne = position / 9;
            col = position % 9;

            nb = 0;
            //on recupere le tableau des chiffres pour la case courante :
            grille[col, ligne].getTabValeurs(tabValeurCase);

            if (param == 'b')
            //backtrack
            {
            	//on recupere la valeur de la case pointee
                nb = grille[col, ligne].getValeur();
                //on rend cette valeur interdite dans le tableau de valeurs de la case
                grille[col, ligne].setVrai(nb);
                //on met a jour le tableau de la case dans cette fonction
                grille[col, ligne].getTabValeurs(tabValeurCase);
            }
            //boucle tant que l'on n'a pas trouvé un chiffre convenable pour la case
            while (p == false)
            {
                tabFull = true;
                //On verifie s'il reste des solutions possibles pour la case, dans son tableau :
                
                for (int i = 0; i < 9; i++)
                {
                    if (tabValeurCase[i] == false) tabFull = false;
                }
                //si le tableau de valeurs utilisees de la case n'est pas plein :
                if (!tabFull)
                {
                    checkTab = false;
                    // on choisit un chiffre disponible dans la liste de valeurs de la case :
                    while (!(checkTab))
                    {
                        nb = rnd.Next(1, 10);
                        if (tabValeurCase[nb - 1] == true) checkTab = false;
                        else checkTab = true;
                    }
                    //on verifie si le nombre choisit n'est pas dans la colonne, dans la ligne ou dans le carre
                    checkRow = notInRow(nb, ligne, col);
                    checkCol = notInColumn(nb, ligne, col);
                    checkSquare = notInSquare(nb, ligne, col);
                    p = checkTab && checkRow && checkCol && checkSquare;
                    if (!p)
                    //si le nombre est deja dans la ligne/carre/colonne, 
                    //on le met a "true" dans le tableau de valeurs de la case
                    {
                        grille[col, ligne].setVrai(nb);
                        grille[col, ligne].getTabValeurs(tabValeurCase);
                    }
                    else 
                    //si le chiffre choisit convient,
                    //on set la valeur de la case avec ce chiffre
                    { 
                        grille[col, ligne].setValeur(nb); 
                    }
                }
                //s'il est plein, backtrack (recul d'une case) :
                else
                {	
                	//on reinitialise le tableau de valeurs de la case
                    grille[col, ligne].resetTab();
                    //on met la valeur de la case a 0
                    grille[col, ligne].setValeur(0);
                    //on appel la fonction en reculant de 1 case
                    remplirBacktrack(position - 1, 'b');
                    return;
                }
            }
            //cas ou la progression est normale
            //on appel la fonction en avancant d'une case :
            remplirBacktrack(position + 1, 'n');
            return;
        }

		//fonction pour verifier si 'value' n'est pas deja present dans la ligne
        private bool notInRow(int value, int indR, int indC)
        {
            bool p=true;
            for(int i=0;i<9;i++){
                if(grille[i,indR].getValeur()==value) p=false;
               }
            return p;
        }
        
        //fonction pour verifier si 'value' n'est pas deja present dans la colonne
        private bool notInColumn(int value, int indR, int indC){
            bool p=true;
            for(int i=0;i<9;i++){
                if (grille[indC, i].getValeur() == value) p = false;
               }
            return p;
        }
		
		////fonction pour verifier si 'value' n'est pas deja present dans le carré
        private bool notInSquare(int value, int indR, int indC){
               int divC,divR;
               bool p = true;
               divC = indC/3;
               divR = indR/3;
               for(int i = divC*3;i<divC*3+3;i++){
                   for(int j = divR*3;j<divR*3+3;j++){
                       if (grille[i, j].getValeur() == value) p = false;
                   }
               }
               return p;
        }

        public int getValCase(int ligne, int col)
        {
            return grille[col, ligne].getValeur();
        }
    }
}

//classe Case
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WindowsFormsApplication1
{
	
    class Case
    {
    	//attributs
        private bool[] tabValeurs;
        private int valeur;
		
		//constructeur
        public Case(){
            initCase();
        }
		
		//methode pour initialiser le tableau de valeurs de la case (a false)
		//et sa valeur a 0
        private void initCase()
        {
            tabValeurs = new bool[9];
            for (int i = 0; i < 9; i++)
            {
                tabValeurs[i] = false;
            }
            valeur = 0;
        }
		
		//methode pour reinitialiser le tableau de valeurs de la case
        public void resetTab()
        {
            for (int i = 0; i < 9; i++)
            {
                tabValeurs[i] = false;
            }
        }
		
		//methode pour enlever un chiffre des valeurs possibles de la case
        public void setVrai(int indice)
        {
            tabValeurs[indice - 1] = true;
        }
		
		//methode pour modifier la valeur de la case
        public void setValeur(int value)
        {
            valeur = value;
        }
		
		//methode pour obtenir la valeur de la case
        public int getValeur()
        {
            return valeur;
        }
		
		//methode pour recopier (passage par reference) le tableau de valeur de la case
		//dans un tableau passé en argument
        public void getTabValeurs(bool[] tabValCase)
        {
            for (int i = 0; i < 9; i++)
            {
                tabValCase[i] = tabValeurs[i];
            }
            
        }
    }
}

Conclusion :


Ce programme n'est bien sur pas une fin en soit, juste une simple illustration de l'algorithme de backtracking pour la generation de grilles de sudoku.
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
Eneur
Messages postés
3
Date d'inscription
mardi 26 octobre 2010
Statut
Membre
Dernière intervention
8 décembre 2011
 -
Salut,
j'ai parcouru ton code avec attention mais les subtilités du C sharp, je crois que c'est comme ça qu'on dit, me sont un peu étrangères. Je suis plus familier du C++.
En fait ton programme construit une grille résolue, en utilisant le retour sur traces lorsqu'il y a blocage, mais la finalité c'est quoi pour un joueur de sudoku si la grille est résolue? quelque chose doit m'échapper sans doute.
ENEUR
Signaler
cs_robx2309
Messages postés
5
Date d'inscription
mardi 2 mars 2010
Statut
Membre
Dernière intervention
9 décembre 2011
 -
C'est vrai qu'en soit le programme n'a pas de grande utilité, mais comme je l'ai deja dit ce n'est pas une fin, mais plutot une "base" de depart pour ceux qui voudraient faire leur propre jeux de sudoku, c'est pour cela que j'ai essayé de faire un algorithme "propre", et de bien structurer mon code. Si je trouve le temps je ferai un vrai jeu de sudoku (bien que je crois qu'il y en ait deja un de posté sur le site)
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.