Weblog de Joël Riou

« Grèves, Indian Summer, pots | Comment transformer Amazon en Père Noël »

Un solveur de grilles de Sudoku

2005-12-17 03:44+0100 (Grigny)

Ces derniers mois, difficile de passer à côté du phénomène 数独, il se manifeste jusqu'au quotidien de référence. Il s'agit d'un jeu « mathématique » consistant à compléter une grille 9×9 avec des chiffres compris entre 1 et 9 de sorte que chacun de ces chiffres apparaisse exactement une fois sur chaque colonne, sur chaque ligne et sur chacun des neuf carrés 3×3 qui forment une supdivision de la grille. Pour plus de détails sur ce jeu, voir la page Wikipédia.

En théorie, la résolution d'une grille n'est pas un problème difficile : un ordinateur obtient la solution en une fraction de seconde. Pour m'en assurer, je viens de passer quelques dizaines de minutes pour écrire un solveur, un résolveur, un solutionneur (choisissez le néologisme le plus à votre goût) en C (pour Unix, peut-être pour autre chose). Code source : sudoku-0.0.tar.gz. Il n'y a aucun début de commencement d'optimisation dans ce petit programme...

Voici une petite grille :

4 1     6
 9 8   5 
    5 9  
6  54 3  
  3  7   
   6  71 
91   85 3
3  2     
  8    6 

Il n'y a évidemment qu'une seule solution pour cette grille, et le nombre de chiffres donnés est minimal pour cette propriété au sens où si on enlève un des chiffres indiqués, n'importe lequel, alors il y a au moins deux solutions. Il est probable que cette grille soit vraiment très difficile à compléter par un être humain...

D'un point de vue mathématique, ce « jeu » n'apparaît pas comme très passionnant (je m'en suis lassé au bout d'une poignée de grilles). Un collègue se posait il y a quelques jours des questions à propos des matrices de sudoku (que peut-on dire des valeurs propres, du rang) dans l'idée d'en faire des exercices de licence... mais je ne crois pas qu'il y ait là matière à choses intéressantes. On peut se demander quel est le « groupe de symétries » de l'ensemble des grilles de sudoku, combien y a-t-il de grilles précisément. Ces questions ont été résolues, mais semble-t-il de manière loin de l'élégance et la simplicité de certaines solutions pour le Rubik's cube...

Lien permanent


Commentaires

1. 2005-12-17 13:29+0100 (Ruxor)

On doit pouvoir se poser des questions intéressantes de dénombrement, au moins (compter le nombre de grilles n²×n², ou de grilles modulo permutation des lignes/colonnes/étiquettes, trouver l'asymptotique, étudier l'algébricité ou l'holonomie de la série génératrice) ou de combinatoire (trouver le nombre minimal d'entrées garantissant l'unicité de la solution, ou le nombre maximal avec unicité mais tel qu'en en retirant une on perde l'unicité). On peut aussi jouer à chercher des généralisations diverses, ou des variantes bizarres. Tiens, le jeu du sudoku à deux, par exemple : on part d'une grille vide, et chaque joueur tour à tour doit ajouter un chiffre en respectant les contraintes, et le premier qui ne peut pas jouer a perdu — qui a une stratégie gagnante ?

2. 2005-12-17 14:12+0100 (Joël)

Ruxor> Tiens, le jeu du sudoku à deux, par exemple : on part d'une grille vide, et chaque joueur tour à tour doit ajouter un chiffre en respectant les contraintes, et le premier qui ne peut pas jouer a perdu — qui a une stratégie gagnante ?

Une variante de ton jeu à deux : les joueurs mettent des chiffres l'un après l'autre ; lorsque c'est son tour, au lieu d'inscrire un chiffre, un joueur pourrait dire « Tu bluffes ! », l'autre joueur aurait alors un temps limité pour compléter la grille ; en inscrivant son chiffre, le joueur pourrait aussi dire « J'ai gagné ! », il devrait alors apporter la démonstration (toujours en temps limité) qu'il existe une unique manière de compléter la grille.

3. 2006-03-01 12:16+0100 (gjg)

Bonjour,

Dans ton commentaire Grigny tu écris que le nombres de grille qu'il est possible de faire au jeu du Sudoku à déja été résolu.

Peux tu indiqué le site ou on peut avoir plus de renseignement concernant ce sujet.

Merci

4. 2006-03-01 13:20+0100 (Joël)

Google me renvoie à <URL: http://www.afjarvis.staff.shef.ac.uk/sudoku/ >.


Vous pouvez poster un commentaire grâce au formulaire ci-dessous.

Nom ou surnom (obligatoire) :
Adresse email (facultative, n'apparaîtra pas publiquement sur ce site) :
Site Web (facultatif) :
Faire conserver ces coordonnées par mon navigateur ?
Pour montrer que vous n'êtes pas un robot stupide, veuillez recopier les chiffres 99868, dans l'ordre inverse :
Le commentaire (de grâce, évitez le SMS-speak) :

Ne mettez que du texte dans les commentaires ; vous pouvez néanmoins insérer des liens en saisissant par exemple <URL: http://www.google.fr/ > (à savoir « <URL: », une espace, l'URL proprement dite, une espace, et enfin « > ».

Date de génération : 2023-07-27 14:18+0530 ― Mentions légales.