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)