Discussion :

[vinche999]

Bonjour à tous,

Je cherche à faire un résolveur de sudoku mais j'ai beaucoup de mal.
J'ai créé une fonction mais elle foire.

Est-ce que quelqu'un pourrait m'aider ?

Merci d'avance.

[Eusebius]

Est-ce que quelqu'un pourrait m'aider ?

C'est un forum d'entraide, donc dans l'absolu, sans doute.
Ya plus qu'à poser ta question (sans doute assortie d'un bout de code bien choisi).

[vinche999]

Voilà la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
function resolution($i=0) {
 
   global $grille,$chiffres,$fin;
   for($ligne=0; $ligne<9; $ligne++) {
 
      for($colonne=0; $colonne<9; $colonne++) {
 
         if($grille[$ligne][$colonne]) continue;
 
         shuffle($chiffres); 
         for($k=0; $k<sizeof($chiffres); $k++) { $nombre = $chiffres[$k];
 
            if(in_array($nombre,$grille[$ligne])) continue;
 
            if(in_array($nombre,colonne($colonne))) continue;
 
            if(in_array($nombre,region($grille,$ligne,$colonne))) continue;
 
            $nombre_chiffre=$grille[$ligne][$colonne];
            $grille[$ligne][$colonne]=$nombre;
 
            if(($ligne==9-1)&&($colonne==9-1)) $fin=true;
            if($fin) return;
            // Non alors essaye de continuer
            resolution($ligne);
            // Sinon essaye avec le chiffre suivant
            if(!$fin) $grille[$ligne][$colonne]=$nombre_chiffre;
         }
         return;
      }
   }
}

Voilà la fonction de résolution.

Veux-tu que je donne tout le code ,

[Eusebius]

Veux-tu que je donne tout le code ,

Non, je voudrais que tu arrives à formuler une question.

[vinche999]

Voici la ligne de code où apparement le code à des soucis :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
shuffle($chiffres); 
for($k=0; $k<sizeof($chiffres); $k++) { $nombre = $chiffres[$k];

Certains sudoku sont résolus, d'autres pas.
Dans certains cas, il n'y a même pas de résolution, le temps est beaucoup trop long. Je ne vois pas où est le problème dans le code.

Quand j'ai une grille vide, aucun problème.
La fonction me genère toutes des grilles correctes.

[Fladnag]

ton algorithme est trop *simple*, il ne permet pas de gerer tout les cas.

Tu remplis simplement toutes les cases pour ne pas faire d'incoherences, mais une case que tu as remplis 2 lignes au dessus s'avere fausse pour la résolution d'une colonne, tu n'a prévu AUCUN moyen de revenir sur ton choix. C'est pourquoi tu ne résouds pas tout.

Il faut donc que tu fasse un algo qui te permet de REVENIR en arriere sur tes précédents choix pour les changer jusqu'a trouver le bon chiffre.

(en imaginant un algo PAS DU TOUT optimisé, tu pourrais revenir sur le précédent choix de la colonne et incrémenter le chiffre, puis invalider tout le reste de la ligne. Mais il faut autoriser la possibilité de passer de 9 a 1 ce que tu algo ne fait pas en ce moment)

[vinche999]

Ce qui est marrant, c'est que je sais pas à pas ce qu'il faut faire et je sais l'expliquer avec la parole mais je n'arrive pas à le retranscrire dans le code . Donc, en résumé, je dois utiliser le backtracking ainsi qu'une fonction récursive.

Mais, comment réaliser un backtracking ?

Je suppose que je dois réaliser un boucle du style for($l=9; $l>0; $i--);

C'est le flou ...

[Fladnag]

hum...
bon...

en reflechissant 20mn, et en imaginant un algo PAS DU TOUT optimisé (j'insiste bien hein ;o)

je gererais ca comme ca :

* Une matrice (tableau de tableau) pour gerer les cases
* Chaque case est un objet (ou un tableau) ayant les attributs suivantes :
- Liste des nombres possibles
- Etat : Valide/Invalide/Fixe
- Nombre actuel

Apres, il te faut :
* Une methode qui va te retourner la liste des cases d'une ligne (getLigne)
* Une methode qui va te retourner la liste des cases d'une colonne (getColonne)
* Une methode qui va te retourner la liste des cases d'une région (carré 3x3 pour les sudoku "normaux") (getRegion)

* Une methode qui met a jour la liste des nombres possibles DE TOUTES LES CASES INVALIDES en fonction des cases a l'état Fixe et Valide (majListePossibles) en tenant compte des nombres définis dans la ligne la colonne et la région.
Elle doit :
- lorsque la liste est réduite a 1 element, on affecte la valeur a la case, on la passe a VALIDE et on relance la methode sur toutes les cases ! (parce qu'on a ajouté une condition).
- lorsque une case a une liste est réduite a 0 element, on est bloqué, on renverra TRUE (sinon on renverra FALSE)

Ensuite, tu pourrais faire qqchose comme ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
majListePossibles();
// toutes les cases a l'etat VALIDE peuvent etre passées a FIXED car elles sont déduites directement par la logique a cette etape.
 
pour toutes les cases INVALIDES
  Choisir le prochain nombre possible dans la liste de cette case et l'affecter a la valeur de la case
  Bloqué = majListePossibles();
  si Bloqué alors
    Creer une liste des cases pouvant bloquer (ie : cases a l'etat VALIDE de la meme ligne, colonne et region)
    Faire un appel a une methode récursive (avec duplication des données) en passant cette liste :
      * majListePossible()
      * si bloqué => 
          * Si la liste n'est pas vide : 
              pour toutes les valeurs possible du premier element de la liste
                on utilise la valeur courante pour le 1er element
                on fait appel récursif avec la liste sans le 1er element
                si retour de l'appel = TRUE => on sort de la methode récursive avec TRUE
              fin pour
          * Sinon renvoyer FALSE 
      * si pas bloqué => renvoyer TRUE
incrémentant de 1
  fin si
fin pour

Note : Dans la mesure ou tu as duplication de données liées a la récursivités (pour gerer les différentes étapes en fait), toutes les methodes devraient prendre en parametre le tableau ou l'objet représentant la grille de sudoku.

Il est possible que mon algo soit encore un peu faux ou qu'il manque des choses, mais c'est l'idée (deja pas si simple ;o))

A noter qu'un algo extremement rapide (quelques millisecondes en C) existe pour résoudre n'importe quelle grille de sudoku... je n'en ai pas connaissance, je sais juste qu'il utilise des listes doublement chainées. Peut etre la page (tres complete) de Wikipedia sur le sudoku pourra t'elle t'aiguiller plus