Pour réaliser cette application web, nous utiliserons du JavaScript (et du HTML pour l'affichage).
Pour commencer, petit rappel sur les règles de ce jeu. En partant des chiffres déjà inscrits sur la grille, nous devons compléter les cases vides afin que chaque ligne, chaque colonne et chaque carré (3x3 cases) contiennent seulement une seule fois les chiffres de 1 à 9.
Pour réaliser ce programme, nous ferons remplir l'intégralité de la grille, puis nous enlèverons X cases en fonction du niveau demandé. On parcourt chaque ligne de la grille, puis chaque case de cette ligne, on tire un nombre au hasard sur la liste des nombres qui ne sont encore pas tombés sur cette ligne et on vérifie qu'il fonctionne. S'il ne fonctionne pas, on prend un autre nombre qui n'est pas encore présent sur la ligne. Si aucun des nombres restant ne fonctionne, alors on recommence la grille à zéro. Il faudra faire faire à notre programme beaucoup de sudoku pour obtenir une grille correcte. On partira sur 1000 (remarque : pour notre ordinateur, tester 1000 grilles sera très très rapide, n'ayez pas peur).
Update : Cette solution n'est pas la méthode idéale, même si elle fonctionne. J'ai créé cet article il y a des années, où je n'étais pas encore à l'aise avec la récursivité. Il est préférable d'utiliser du backtracking, c'est à dire qu'au lieu de recommencer la grille du début si elle ne fonctionne pas, il serait préférable de rechoisir un nombre pour la case précédente, puis la case encore d'avant si ça ne fonctionne toujours pas, ...
Nous allons partir sur un code de base tout simple :
1 <select id="niveau" name="type" onchange="AjoutOptionAuSelect(this);"> 2 <option value="20">Facile (20 cases vides)</option> 3 <option value="30" selected>Normal (30 cases vides)</option> 4 <option value="40">Expert (40 cases vides)</option> 5 <option value="autre">Personnalisé</option> 6 </select> 7 8 <a href="javascript:generateSudoku(); return false;">Générer</a> 9 10 <div id="erreur" style="display: none"></div> 11 <div id="resultat"> 12 <h2>Base</h2> 13 <div id="grille_a_faire"></div> 14 15 <h2>Solution</h2> 16 <div id="grille_solution"></div> 17 </div>
Premièrement, un select permettant de choisir le niveau, avec par défaut, le niveau normal.
Vous remarquerez qu'il y a aussi une option Personnalisé. Si vous souhaitez pouvoir faire choisir au visiteur le nombre de cases à retirer, regarder cet article : Ajouter une option à un select en JavaScript.
Ensuite, un lien pour générer le sudoku, appelant une fonction JavaScript que nous ferons ensuite.
La div erreur permettra d'afficher une éventuelle erreur, sinon, on affichera la base (la grille avec des cases à compléter), suivie de la solution (ou plutôt, une solution possible).
Et le code de base pour notre JavaScript :
1 function generateSudoku() 2 { 3 // @TODO 4 }; 5 6 function AjoutOptionAuSelect(this_select) 7 { 8 if (this_select.value == "autre") 9 { 10 var saisie; 11 var pass = false; 12 do 13 { 14 if (pass) alert("La valeur est incorrecte. Elle ne doit comporter que des chiffres."); 15 saisie = prompt("Nombre de cases vides :"); 16 if (saisie == null) return false; 17 pass = true; 18 } 19 while (saisie.match(/[^0-9]/i) && saisie != "") 20 21 this_select.options[this_select.length] = new Option(saisie + ' case' + (saisie > 1 ? 's' : '') + ' vide' + (saisie > 1 ? 's' : ''), saisie, true, true); 22 23 for (var i=0; i < this_select.options.length; i++) 24 { 25 if (this_select.options*.value == saisie) 26 { 27 this_select.options*.selected = true; 28 } 29 } 30 } 31 };
La deuxième fonction permet l'option Personnalisé du select. Pour plus d'informations, voir l'article que j'ai cité précédemment.
Nous allons dès maintenant ajouter deux nouvelles variables dans notre fonction, pour la configuration :
1 var nb_case_vide = document.getElementById("niveau").value; 2 var nb_max_loop = 1000;
La première afin de récupérer le nombre de cases à cacher en fonction du niveau, la deuxième pour le nombre maximal d'essais à faire.
Première chose importante à faire, c'est de déclarer nos variables.
1 var grille = new Array(); 2 var lignes = new Array(); 3 var colonnes = new Array(); 4 var carres = new Array(); 5 var i_while = 0; 6 var grille_complete = false;
Le tableau grille devra contenir 9 tableaux (9 lignes) avec 9 tableaux chacun (9 colonnes).
Le tableau lignes devra contenir quant à lui toutes les possibilités de chaque ligne. Pour vérifier plus tard si par exemple, le 3 est déjà sorti à la ligne 7, on vérifiera si lignes[7][3] existe.
Même principe pour colonnes.
Pour carres, c'est encore le même procédé, à part qu'il y a 3x3 carrés et non 9x9 cases.
Et enfin, on initialise les variables i_while et grille_complete, respectivement pour le nombre de boucle déjà effectué, et si la grille est complétée ou non (par défaut à non).
Avant d'initialiser nos variables maintenant, nous allons créer le while afin que les cases soient vidées à chaque boucle.
1 outerwhile: // Point de référence 2 while ((i_while < nb_max_loop) && !grille_complete) // Boucle tant que la grille n'est pas complète et que l'on n'a pas dépassé le maximum de boucle 3 { 4 i_while++; // On ajoute 1 à la boucle 5 6 // ... 7 };
Vous pouvez voir que j'ai ajouté juste avant la boucle outerwhile. Je vais vous expliquer à quoi cela sert. En fait, donc notre boucle, nous allons tout d'abord initialiser nos cases, puis nous allons essayer de les remplir.
Si nous sommes contraints d'annuler notre grille, nous devrons recommencer. Et c'est justement à cela que sert notre outerwhile. Lorsque que nous voudrons redémarrer le while, il nous suffira de faire :
1 continue outerwhile;
Passons maintenant à l'initialisation de nos tableaux.
Rien de bien compliqué si vous avez compris mes explications sur l'intérêt de chaque variable lors de leurs déclarations.
1 for (var i = 1; i <= 9; i++) 2 { 3 grille[i] = new Array(); // On crée chaque ligne de la grille 4 lignes[i] = new Array(); // On crée un array pour les lignes 5 colonnes[i] = new Array(); // On crée un array pour les colonnes 6 7 for (var j = 1; j <= 9; j++) 8 { 9 grille[i][j] = 0; // On passe toutes les cases à 0 10 lignes[i][j] = j; // On complète toutes les possibilités de la ligne 11 colonnes[i][j] = j; // On complète toutes les possibilités de la colonne 12 }; 13 }; 14 for (var i = 1; i <= 3; i++) 15 { 16 carres[i] = new Array(); // On crée les trois lignes de carrés 17 18 for (var j = 1; j <= 3; j++) 19 { 20 carres[i][j] = new Array(); // On crée les trois colonnes de carrés dans chaque ligne de carré 21 for (var k = 1; k <= 9; k++) 22 { 23 carres[i][j][k] = k; // Et on associe à chaque carré toutes les possibilités de lignes et de colonnes 24 }; 25 }; 26 };
Par la suite, quand nous voudrons vérifier si l'on peut mettre le chiffre 7 à la ligne 3 colonne 5 (et donc le carré de la deuxième ligne, colonne 1), il suffira de vérifier si lignes[3][7], colonnes[5][7] et carres[2][1][7] existent.
Si toutes existent, alors on ajoute le nombre à grille[3][5] et on supprime chacune des variables.
Nous allons donc faire nos calculs cases par cases. Il suffit de faire donc une boucle pour les lignes (y), suivie d'une boucle pour les colonnes (x) :
1 for (var y = 1; y <= 9; y++) 2 { 3 for (var x = 1; x <= 9; x++) 4 { 5 // ... 6 }; 7 };
Ensuite, nous allons tout d'abord créé un tableau avec toutes les possibilités.
On recrée une boucle sur chacun des chiffres de 1 à 9 et on vérifie s'il n'est pas déjà présent dans cette ligne, pas déjà présent dans cette colonne et pas déjà présent dans le carré actuel. Si c'est ok, alors on l'ajoute à un tableau possibilites.
1 var possibilites = new Array(); 2 var index = 0; 3 4 for (var k = 1; k <= 9; k++) 5 { 6 if (!lignes[y][k]) continue; 7 if (!colonnes[x][k]) continue; 8 if (!carres[Math.ceil(y/3)][Math.ceil(x/3)][k]) continue; 9 10 possibilites[index] = k; 11 index++; 12 };
Ce n'est pas bien compliqué.
Juste une précision pour trouver le numéro du carré actuel. Pour trouver sa ligne, Math.ceil(y/3), on divise le numéro de la ligne par 3, et on prend l'entier supérieur ou égal grâce à la fonction Math.ceil. Ainsi, si nous sommes à la ligne 8 : 8/3=2.6666 ; la valeur renvoyée sera donc 3, nous serons à la 3ème ligne.
Exactement le même principe pour Math.ceil(x/3).
A partir de là, nous avons deux possibilités.
Soit le tableau possibilites est vide. Nous devons donc recommencer notre boucle. Nous utiliserons continue outerwhile; comme je vous l'ai dit un peu plus haut.
S'il n'est pas vide, alors on tire au hasard une des possibilités, on l'ajoute à notre grille et on la supprime des tableaux des lignes, des colonnes et des carrés.
1 if (possibilites.length == 0) continue outerwhile; 2 3 var nb = possibilites[Math.floor((Math.random() * possibilites.length))]; 4 grille[y][x] = nb; 5 lignes[y][nb] = undefined; 6 colonnes[x][nb] = undefined; 7 carres[Math.ceil(y/3)][Math.ceil(x/3)][nb] = undefined;
Si après avoir parcouru les deux boucles le programme tourne toujours, c'est qu'il a réussi à compléter la grille. Donc juste avant la fermeture du while :
1 grille_complete = true;
Et le while ne recommencera plus.
A ce moment-là, deux possibilités toujours. Soit la grille est complétée, soit elle ne l'est pas. Si elle ne l'est pas, alors on affiche la div erreur, on cache la div resultat et on affiche un message d'erreur.
1 if (grille_complete) 2 { 3 // @TODO 4 } 5 else 6 { 7 var today = new Date; 8 9 document.getElementById("resultat").style.display = 'none'; 10 document.getElementById("erreur").style.display = 'block'; 11 document.getElementById("erreur").innerHTML = today.getHours() + ":" + today.getMinutes() + ":" + today.getSeconds() + " : Echec après " + nb_max_loop + " tentatives."; 12 }
Si la grille est complétée, alors il va falloir cacher X cases (en fonction du niveau).
Pour cacher ses cases, afin qu'elles soient mélangées proprement, nous allons créer un tableau à 81 entrées (9x9), avec comme valeur par défaut false. On passera la valeur à true pour X cases (nombre de cases devant être cachées).
Ensuite on devra mélanger le tableau. En PHP, il existe la fonction shuffle. Mais celle-ci n'existe pas par défaut en JavaScript. Nous utiliserons une fonction déjà créée par un autre développeur :
1 //+ Jonas Raoni Soares Silva 2 //@ http://jsfromhell.com/array/shuffle [rev. #1] 3 function shuffle(array) 4 { 5 for(var j, x, i = array.length; i; j = parseInt(Math.random() * i), x = array[--i], array* = array[j], array[j] = x); 6 return array; 7 };
On obtient donc :
1 var cases_a_vider = new Array(); 2 3 for (var i = 1; i <= 81; i++) 4 { 5 if (i <= nb_case_vide) cases_a_vider* = true; 6 else cases_a_vider* = false; 7 } 8 9 cases_a_vider = shuffle(cases_a_vider);
Reste maintenant à afficher le résultat sous forme de tableaux (1 pour l'énoncé, 1 pour la solution).
Rien de bien compliqué, on fait une boucle de chaque ligne de la grille et en fonction du numéro de la case, on l'affiche ou non dans le tableau énoncé.
On n'oublit pas à la fin de cacher la div erreur et d'afficher la div resultat dans le cas où il y aurait eu une erreur juste avant.
1 var html = "<table cellpadding='0'><tbody>"; 2 var html_enonce = "<table cellpadding='0'><tbody>"; 3 var count = 0; 4 5 for (var y = 1; y <= 9; y++) 6 { 7 html += "<tr>"; 8 html_enonce += "<tr>"; 9 10 for (var x = 1; x <= 9; x++) 11 { 12 count++; 13 14 html += "<td>" + ((cases_a_vider[count]) ? '<span class="red">' + grille[y][x] + '</span>' : grille[y][x]) + "</td>"; 15 html_enonce += "<td" + ((cases_a_vider[count]) ? ' class="vide"> ' : '>' + grille[y][x]) + "</td>"; 16 }; 17 18 html += "</tr>"; 19 html_enonce += "</tr>"; 20 }; 21 22 html += "</tbody></table>"; 23 html_enonce += "</tbody></table>"; 24 25 document.getElementById("grille_a_faire").innerHTML = html_enonce; 26 document.getElementById("grille_solution").innerHTML = html; 27 document.getElementById("resultat").style.display = 'block'; 28 document.getElementById("erreur").style.display = 'none';
Le générateur de sudoku est maintenant prêt.
Pour être sûr, vous pouvez augmenter le nombre de tentatives, ça ne risque pas grand-chose ; voir le résultat.