Yes Man a dit le 23 décembre 2009
Le début est en effet simple, et c’est justement maintenant pour aller plus loin que l’on a besoin de toi. Pourquoi ne pas continuer l’article ? La réponse est dans mon pseudo.
Créer une grille de Sudoku
Vous êtes ici : Accueil / Articles / Formations en Algorithmique
Introduction
Qu’est-ce qu’un sudoku ?
Un sudoku est un jeu populaire dont le but est de remplir une grille de 9x9 divisée en carrés de 3x3 avec des chiffres selon des contraintes très restrictives.
Voici un exemple de grille :
Chaque ligne, chaque colonne et chaque carré de 3x3 ne doit contenir qu’une occurrence de chaque nombre entre 1 et 9. Ainsi, dans la première ligne, il est impossible de placer un 6 dans une des cases vides car la ligne en possède déjà 1.
Les grilles de sudoku sont réparties en plusieurs niveaux, allant de débutant à diabolique, selon des critères très subjectifs et dont la difficulté de niveau peut varier fortement suivant le fournisseur de grille.
La création des sudoku
Avec la popularisation du jeu, il est devenu très rapidement nécessaire de trouver des algorithmes pour créer automatiquement des grilles afin de répondre à la demande toujours croissante. Voici une méthode assez générale, à partir de laquelle il est bien entendu possible d’ajouter ses propres subtilités pour rendre le jeu plus attractif.
Notre programme est scindé en 2 étapes : la génération de la grille complète, puis le retrait des chiffres. Cet ordre de création a été choisi pour plusieurs raisons : il est nécessaire de disposer de la grille de solution afin de satisfaire la curiosité d’éventuels joueurs qui n’arriveraient pas à la compléter. De plus, il n’est pas possible d’ôter aléatoirement des valeurs de la grille, sous risque de créer une grille possédant plusieurs solutions. La solution unique est une règle d’or de la création de sudoku, bien que parfois non respectée.
Afin d’éviter ce problème, nous allons baser nos algorithmes de retrait sur le principe fondamental suivant : « Ne retirer que les pièces qu’il est possible de retrouver de manière certaine par une réflexion implémentée sous forme algorithmique ».
Le niveau de difficulté est donc tout simplement géré par la complexité de l’algorithme qui doit vérifier qu’une pièce est retrouvable.
Le présent dossier n’a pas pour vocation de créer une application de sudoku mais uniquement d’orienter le lecteur vers une méthode algorithmique qu’il pourra affiner à sa guise. Ainsi, l’affichage de la grille n’est pas gérée, de même pour l’interaction avec le joueur. Les codes sources proposés sont programmés en PHP avec une syntaxe procédurale en prenant soin d’utiliser des fonctions simples afin de faciliter sa transcription dans d’autres langages.
Génération de la grille
Notre première étape consiste donc à générer la grille résultat. Comment trouver une grille respectant les contraintes du jeu, de manière certaine ? Eh bien il n’existe aucun algorithme ne permettant de la générer de manière directe. La solution employée par tous est donc l’utilisation d’un algorithme de backtracking.
Introduction au backtracking
Le bactracking ( retour sur trace en Français ), est un algorithme récursif optimisé pour la recherche de solutions avec contraintes, ce qui est précisément le cas de la génération d’une grille de sudoku. Voici un pseudo code général le représentant :
<?php
function backtracking( variables ) {
if( toutes les variables sont assignées ) {
return variables ;
}
foreach( valeur ) {
if( solution partielle respecte contraintes ) {
solution = backtracking( variables + valeur ) ;
if( solution ) {
return solution;
}
}
}
// Si aucune valeur ne respecte les contraintes
return false ;
}
?>
La grande différence entre une recherche de toutes les solutions et la recherche par analyse combinatoire est que celle-ci coupe les branches dès qu’une solution partielle ne vérifie pas les contraintes imposées, et évite ainsi quantité de tests inutiles.
Application au cas du Sudoku
Dans notre cas, nous nous placer successivement à chaque case du jeu, et essayer de placer un numéro entre 1 à 9, différent des numéros qui sont dans la même ligne, dans la même colonne ou dans le même carré que la case. S’il ne reste aucun chiffre possible, alors il faut revenir en arrière ( d’où le nom retour sur trace ) et essayer d’autres numéros dans les cases précédentes.
Notre fonction va donc prendre en paramètre un une matrice 9x9 implémentée sous forme de tableau. Ce dernier sera vide lors du premier appel à la fonction, puis se remplira petit à petit à chaque appel de récurrence. La fonction retournera soit la matrice contenant la grille générée, soit false.
Le choix du numéro à placer doit être fait de manière aléatoire sans quoi toutes les grilles seraient similaires.
Voici un exemple d’algorithme de génération de grille :
<?php
function creer_grille( $grille = array(), $position = 0 ) {
// Si nous sommes arrivés à la fin, la grille est trouvée
if( $position == 81 ) {
return $grille;
}
// Calculer la ligne et la colonne
$i = floor( $position / 9 );
$j = $position % 9;
// Créer une liste des nombres de 1 à 9
$valeurs = range( 1, 9 );
// Retirer les valeurs déjà utilisées
for( $k=0; $k<9; $k++ ) {
// Oter de la liste les nombres de la ligne
if( $v = $grille[ $i ][ $k ] ) {
unset( $valeurs[ $v-1 ] );
}
// Oter de la liste les nombres de la colonne
if( $v = $grille[ $k ][ $j ] ) {
unset( $valeurs[ $v-1 ] );
}
// Oter de la liste les nombres du carré
if( $v = $grille[ $i + floor($k/3) ][ $j + ($k%3) ] ) {
unset( $valeurs[ $v-1 ] );
}
}
// Melanger le tableau
shuffle( $valeurs );
// Essayer les valeurs restantes jusqu'à trouver la solution
foreach( $valeurs as $v ) {
$grille[$i][$j] = $v;
$resultat = creer_grille( $grille, $position + 1 );
// Si on trouve la solution, on la retourne
if( $resultat ) {
return $resultat;
}
unset( $grille[$i][$j] );
}
// Si nous arrivons à la fin de la boucle, aucune grille n'existe
// avec les valeurs précédentes
return false;
}
?>
Nous disposons désormais d’une fonction retournant une matrice 9x9 contenant les valeurs de la grille. Il reste désormais à retirer des valeurs avec des algorithmes que nous allons détailler à la prochaine étape.
Retrait des valeurs
Dans cette partie, nous allons développer la fonction qui, à une grille donnée, va choisir des positions aléatoirement et regarder s’il est possible de les replacer sans ambigüité. Les fonctions de test seront explicitées dans la partie suivante.
Nous allons tester dans un ordre aléatoire successivement toutes les positions pour voir s’il est possible de les retirer. Il est évident que plus les valeurs sont retirées, plus il est difficile de retirer des valeurs car pour les retrouver, il faut faire appel à des réflexions plus complexes.
Le nombre de valeurs restantes sera donc fonction de la puissance de l’algorithme de retrait utilisé.
Cette fonction va contenir une petite subtilité : lorsqu’une position est testée, nous allons tester son image par la symétrie centrale de centre celui du carré 9x9, afin de garder une grille équilibrée au niveau du retrait des valeurs.
Voici donc une fonction qui va prendre en premier paramètre la grille complète de sudoku, puis en second paramètre un tableau de fonctions de retrait de valeurs, que nous décrirons ensuite.
<?php
function retirer_valeurs( $grille, $tests = array() ) {
// Créer une liste de toutes les positions
$positions = range( 0, 80 );
// Tant que la liste des valeurs à tester n'est pas vide
while( $positions ) {
// Prendre une position au hasard
$position = array_rand( $positions );
unset( $positions[ $position ] );
// Calculer la ligne et la colonne
$i = floor( $position / 9 );
$j = $position % 9;
// Pour chaque test de retrait
foreach( $tests as $test ) {
// S'il est possible de retirer la position
if( $test( $grille, $i, $j ) ) {
// Supprimer la valeur de la grille
unset( $grille[ $i ][ $j ] );
break;
}
}
// Calculer la ligne et la colonne opposées
$position = 80 - $position;
$i = floor( $position / 9 );
$j = $position % 9;
unset( $positions[ $position - 1 ] );
// Pour chaque test de retrait
foreach( $tests as $test ) {
// S'il est possible de retirer la position
if( $test( $grille, $i, $j ) ) {
// Supprimer la valeur de la grille
unset( $grille[ $i ][ $j ] );
break;
}
}
}
return $grille;
}
?>
Algorithmes de retrait
Nous entrons dans le cœur de la création des sudoku. Les algorithmes utilisés dans cette partie dépendent en grande partie des créateurs de sudoku, chacun gardant jalousement ses secrets de fabrication. Afin de créer les algorithmes de retraits, il est nécessaire de se pencher sur les raisonnements que font un joueur afin de lui-même compléter la grille.
Beaucoup de raisonnements sont redondants, et il est donc important de différencier les techniques utilisées. Il est facile de voir si 2 raisonnements sont similaires aux taux de retrait de nombres de la grille finale.
Tous les algorithmes de retrait devront respecter la pseudo-signature suivante :
Premier raisonnement : les contraintes de placement
Principe
Le raisonnement au plus bas niveau que va effectuer le joueur va être de regarder s’il n’est pas possible de placer des valeurs en se contentant d’appliquer les règles du jeu : le nombre ne doit pas déjà être présent dans la ligne, dans la colonne et dans le carré de 3x3. L’ensemble des valeurs possibles restantes est égale à 1, alors il peut placer la valeur.
Dans l’exemple précédent, nous voyons qu’il ne reste plus qu’un 2 possible à l’emplacement coloré en jaune. Il n’y a donc pas d’ambigüité.
Implémentation
L’implémentation de ce raisonnement est extrêmement simple. Elle est d’ailleurs entièrement contenue dans la fonction de génération de la grille.
<?php
function est_retirable_1( $grille, $i, $j ) {
unset( $grille[$i][$j] );
// Créer une liste des nombres de 1 à 9
$valeurs = range( 1, 9 );
// Retirer les valeurs déjà utilisées
for( $k=0; $k<9; $k++ ) {
// Oter de la liste les nombres de la ligne
if( $v = $grille[ $i ][ $k ] ) {
unset( $valeurs[ $v-1 ] );
}
// Oter de la liste les nombres de la colonne
if( $v = $grille[ $k ][ $j ] ) {
unset( $valeurs[ $v-1 ] );
}
// Oter de la liste les nombres du carré
if( $v = $grille[ $i + floor($k/3) ][ $j + ($k%3) ] ) {
unset( $valeurs[ $v-1 ] );
}
}
// Retourne true s?il ne reste plus qu?une valeur
return count($valeurs) == 1;
}
?>
Second raisonnement : les contraintes distantes
Principe
Le premier raisonnement trouve rapidement ses limites. Il ne faut pas pour autant considérer que la valeur ne peut pas être retrouvée facilement. Prenons le cas suivant :
Etant donné un carré de 3x3 et une valeur, si toutes les cases vides du carré sauf une contiennent la valeur dans la même ligne ou la même colonne, alors cette valeur se situe forcément dans la dernière case vide.
Nous voyons que ce raisonnement n’est pas équivalent au précédent car le précédent ne permettait pas de trouver la valeur. En effet, il y restait 1,3,5,6.
Implémentation
L’implémentation du second raisonnement n’est pas non plus très compliquée. Connaissant les coordonnées de la valeur dont on veut tester la non-ambigüité, il suffit d’effectuer un test d’existence de la valeur dans la ligne et la colonne de toutes les autres cases vides du carré :
<?php
function est_retirable_2( $grille, $i, $j ) {
// Récupérer la valeur, puis la supprimer
$valeur = $grille[$i][$j];
unset( $grille[$i][$j] );
// Pour chaque position du carré 3x3
for( $k=0; $k<9; $k++ ) {
// Calculer les coordonnées courrantes
$ligne = floor( $i/3 ) + floor( $k / 3 );
$colonne = floor( $j/3 ) + ( $k % 3 );
// Si nous sommes dans une case vide différente de la case étudiée
if( $ligne != $i && $colonne != $j && !$grille[$ligne][$colonne] ) {
// A chaque case de sa ligne ou de sa colonne
for( $l=0; $l<9; $l++ ) {
// Si nous trouvons la valeur
if( $grille[$ligne][$k] == $valeur
|| $grille[$k][$colonne] == $valeur ) {
// Sortir de la boucle
break;
}
}
// Si la boucle est terminée, alors une autre case vide
// est ambigüe, donc la pièce n'est pas retirable
return false;
}
}
// Si toutes les cases vides ont été testées sans retourner false
// alors aucune n'est ambigüe
return true;
}
?>
Exemple d’utilisation
Après avoir vu quelques exemples d’algorithmes de retraits, voici un code permettant de les appeler :
<?php
// Créer une nouvelle grille
$grille_complete = creer_grille();
// Lui retirer des valeurs
$grille = retirer_valeurs( $grille_complete, array( 'est_retirable_1', ?est_retirable_2? ) );
// L'afficher
echo '<table>';
for( $i=0; $i<9; $i++ ) {
echo '<tr>';
for( $j=0; $j<9; $j++ ) {
echo '<td>' . $grille[$i][$j] . '</td>';
}
echo '</tr>';
}
echo '</table>';
?>
Pour aller plus loin
La grille affichée comportera encore beaucoup trop de valeurs, rendant la grille trop facile. Il est donc nécessaire de trouver d’autres raisonnements et les implémenter en PHP. Nous n’étudierons pas plus de raisonnements car ils deviennent de plus en plus lourds à formaliser, et d’autant plus à implémenter.
Voici cependant un principe qui fera faire un grand pas dans la complexité de la grille : Il suffit de créer un arbre des dépendances des valeurs retirées et dire « si toutes les valeurs de l’arbre de dépendance sont non-ambigües, alors considérer la valeur racine comme non-ambigüe ». A partir de ce principe, les algorithmes vont évoluer des tests de valeurs existantes à des tests de valeurs non-ambigües, ce qui va grandement augmenter le taux d’acceptation de retrait.
Commentaires
Ludovic PATEY a dit le 23 décembre 2009
A vrai dire, je n’ai plus trop le temps d’écrire des articles.
Si tu veux faire des grilles de sudoku très difficiles, il y a un moyen très simple : la force brute. En gros, comme algorithme de retrait, tu retires la pièce, puis fais du backtracking pour essayer de trouver toutes les solutions compatibles avec la grille. S’il n’y en a qu’une seule, c’est qu’il n’y a pas d’ambiguïté et donc tu peux la retirer. Les ordinateurs sont bien assez puissants pour cela.
moTx a dit le 5 janvier 2010
Bonjour,
Votre algo de génération de grille est intéressant, mais me pose problème avec de la programmation typée, en effet on ne peut avoir deux types de retour (un tableau à deux dimensions, et un booléen), ce qui me pose un gros problème pour la conversion en VB.
Avez une idée à comment solutionner le problème ?
(j’ai posté un thread ici : http://www.developpez.net/forums/d858385/dotnet/visual-basic-net/windows-forms/fonction-recursive-types-retour/#post4896607 )