Créer un générateur de grilles de Sudoku en JavaScript

Introduction



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).


Code de base



Nous allons partir sur un code de base tout simple :
<select id="niveau" name="type" onchange="AjoutOptionAuSelect(this);">
	<option value="20">Facile (20 cases vides)</option>
	<option value="30" selected>Normal (30 cases vides)</option>
	<option value="40">Expert (40 cases vides)</option>
	<option value="autre">Personnalisé</option>
</select>

<a href="javascript:generateSudoku(); return false;">Générer</a>

<div id="erreur" style="display: none"></div>
<div id="resultat">
	<h2>Base</h2>
	<div id="grille_a_faire"></div>

	<h2>Solution</h2>
	<div id="grille_solution"></div>
</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.

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 :
<script type="text/javascript">
	function generateSudoku ()
	{
		// Á compléter

	};

	function AjoutOptionAuSelect(this_select)
	{
		if (this_select.value == "autre")
		{
			var saisie;
			var pass = false;
			do
			{
				if (pass) alert("La valeur est incorrecte. Elle ne doit comporter que des chiffres.");
				saisie = prompt("Nombre de cases vides :");
				if (saisie == null) return false;
				pass = true;
			}
			while (saisie.match(/[^0-9]/i) && saisie != "")

			this_select.options[this_select.length] = new Option(saisie + ' case' + (saisie > 1 ? 's' : '') + ' vide' + (saisie > 1 ? 's' : ''), saisie, true, true);

			for (var i=0; i < this_select.options.length; i++)
			{
				if (this_select.options[i].value == saisie)
				{
					this_select.options[i].selected = true;
				}
			}
		}
	};
</script>


La deuxième fonction permet l'option "Personnalisé" du select. Pour plus d'informations, voir cet article.

Nous allons dès maintenant ajouter deux nouvelles variables dans notre fonction, pour la configuration :
var nb_case_vide = document.getElementById("niveau").value;
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'essai à faire.


Initialisation



Première chose importante à faire, c'est de déclarer nos variables.
var grille = new Array();
var lignes = new Array();
var colonnes = new Array();
var carres = new Array();
var i_while = 0;
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.
outerwhile: // Point de référence

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

{
	i_while++; // On ajoute 1 à la boucle


	// ...

};

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 :
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.
for (var i = 1; i <= 9; i++)
{
	grille[i] = new Array(); // On crée chaque ligne de la grille

	lignes[i] = new Array(); // On crée un array pour les lignes

	colonnes[i] = new Array(); // On crée un array pour les colonnes


	for (var j = 1; j <= 9; j++)
	{
		grille[i][j] = 0; // On passe toutes les cases à 0

		lignes[i][j] = j; // On complète toutes les possibilités de la ligne

		colonnes[i][j] = j; // On complète toutes les possibilités de la colonne

	};
};
for (var i = 1; i <= 3; i++)
{
	carres[i] = new Array(); // On crée les trois lignes de carrés


	for (var j = 1; j <= 3; j++)
	{
		carres[i][j] = new Array(); // On crée les trois colonnes de carrés dans chaque ligne de carré

		for (var k = 1; k <= 9; k++)
		{
			carres[i][j][k] = k; // Et on complète toutes les possibilités du carré

		};
	};
};

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.


Calculs



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) :
for (var y = 1; y <= 9; y++)
{
	for (var x = 1; x <= 9; x++)
	{
		// ...

	};
};


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.
var possibilites = new Array();
var index = 0;

for (var k = 1; k <= 9; k++)
{
	if (!lignes[y][k]) continue;
	if (!colonnes[x][k]) continue;
	if (!carres[Math.ceil(y/3)][Math.ceil(x/3)][k]) continue;

	possibilites[index] = k;
	index++;
};

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).

Á 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.
if (possibilites.length == 0) continue outerwhile;

var nb = possibilites[Math.floor((Math.random() * possibilites.length))];
grille[y][x] = nb;
lignes[y][nb] = undefined;
colonnes[x][nb] = undefined;
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 :
grille_complete = true;

Et le while ne recommencera plus.


Création de la grille



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.
if (grille_complete)
{
	// Á faire

}
else
{
	var today = new Date;

	document.getElementById("resultat").style.display = 'none';
	document.getElementById("erreur").style.display = 'block';
	document.getElementById("erreur").innerHTML = today.getHours() + ":" + today.getMinutes() + ":" + today.getSeconds() + " : Echec apr&egrave;s " + nb_max_loop + " tentatives.";
}



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 :
//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/array/shuffle [rev. #1]
function shuffle(array)
{
	for(var j, x, i = array.length; i; j = parseInt(Math.random() * i), x = array[--i], array[i] = array[j], array[j] = x);
	return array;
};

Je ne vous expliquerai pas comment fonctionne cette fonction, elle est bien trop compliquée.

On obtient donc :
var cases_a_vider = new Array();

for (var i = 1; i <= 81; i++)
{
	if (i <= nb_case_vide) cases_a_vider[i] = true;
	else cases_a_vider[i] = false;
}

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'oubli 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.
var html = "<table cellpadding='0'><tbody>";
var html_enonce = "<table cellpadding='0'><tbody>";
var count = 0;

for (var y = 1; y <= 9; y++)
{
	html += "<tr>";
	html_enonce += "<tr>";

	for (var x = 1; x <= 9; x++)
	{
		count++;

		html += "<td>" + ((cases_a_vider[count]) ? '<span class="red">' + grille[y][x] + '</span>' : grille[y][x]) + "</td>";
		html_enonce += "<td" + ((cases_a_vider[count]) ? ' class="vide">&nbsp;' : '>' + grille[y][x]) + "</td>";
	};

	html += "</tr>";
	html_enonce += "</tr>";
};

html += "</tbody></table>";
html_enonce += "</tbody></table>";

document.getElementById("grille_a_faire").innerHTML = html_enonce;
document.getElementById("grille_solution").innerHTML = html;
document.getElementById("resultat").style.display = 'block';
document.getElementById("erreur").style.display = 'none';



Résultats



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.

Tags :
Article écrit le samedi 8 septembre 2012 à 16:51:32 - 3807 vues
http://www.dewep.net/Blog/Article-11/Creer-un-generateur-de-grilles-de-Sudoku-en-JavaScript




3 commentaires

Avatar

Le sudoku que je viens de télécharger sur cette page à l'air super sympa!!!
Je vous le recommande, chers internautes.

il y a 1 an
Avatar loic

loic

Serait il possible de remplacer les chiffres par des images (gif, png.... avec le chiffre en surimpression ?
Merci
Travail très intéressant....

il y a 10 mois et demi
Avatar Aurélien Maigret

Aurélien Maigret

Bonjour,

Pour afficher des images au lieu des numéros, tu passes le grille[y][x] de la fin en paramètre à une nouvelle fonction, qui, au lieu de retourner un nombre, retourne une balise img :

<img src="1.jpg" alt="1"/><


Remarque : J'ai fais cet article il y a maintenant plus de 8 mois ; je n'étais pas encore en école d'informatique. La technique utilisée ici n'est vraiment pas propre : au lieu de recommencer un sudoku à zéro quand il y a une erreur, il faudrait juste reculer d'une case, ce serait bien plus rapide.

Aurélien.

il y a 10 mois et demi




Laisser un commentaire

Qu'est-ce que Gravatar ?

Gravatar vous permet de créer un compte basé sur votre adresse E-Mail, pour ensuite y ajouter un avatar. Lorsque vous postez un commentaire sur un blog supportant ce service, il vous suffit alors de renseigner votre E-Mail pour que votre avatar soit automatiquement ajouté. D'autres informations (votre nom, votre site, ...) peuvent aussi être récupérées sur votre profil Gravatar.
Sur ce blog, votre nom, votre avatar et votre site sont récupérés. Le champ "pseudo/nom" n'est d'aucune utilité si votre adresse E-Mail est associé à un compte Gravatar.

CC BY-NC-SA 3.0 L'ensemble des articles est soumis à la licence CC BY-NC-SA 3.0 (Code Juridique).
Vous êtes donc libre de remixer et partager l'oeuvre aux conditions de l'attribuer (lien vers la page de l'article), de ne pas l'utiliser à des fins commerciales et de la partager avec une licence identique ou similaire.

Aurélien Maigret

Retrouvez-moi sur les principaux réseaux sociaux ! Si vous souhaitez être tenu informé de la publication de mes prochains articles, abonnez-vous au flux RSS, ou suivez-moi sur Twitter/Facebook.

Derniers tweets