« Grèves, Indian Summer, pots | Comment transformer Amazon en Père Noël »
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 | 5 | 4 | 3 | |||||
| 3 | 7 | |||||||
| 6 | 7 | 1 | ||||||
| 9 | 1 | 8 | 5 | 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...
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 ?
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.
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
Google me renvoie à <URL: http://www.afjarvis.staff.shef.ac.uk/sudoku/ >.
Vous pouvez poster un commentaire grâce au formulaire ci-dessous.
Date de génération : 2023-07-27 14:18+0530 ― Mentions légales.