Partager l'article ! Défi : un sudoku diabolique: Suite à un commentaire de Bestiolle m'invitant à résoudre une grille particulièrement cors&e ...
Le tourtereau
Dans une allée à Chartres
Commentaires
- Défi : un sudoku diabolique
- Pour changer les serrures de votre voiture, votre concessionnaire vous fera une offre que vous ne pourrez que refuser
- Pour changer les serrures de votre voiture, votre concessionnaire vous fera une offre que vous ne pourrez que refuser
- Défi : un sudoku diabolique
- Création surréaliste
Mardi 20 décembre 2005
2
20
/12
/Déc
/2005
22:09
Suite à un commentaire de Bestiolle m'invitant à résoudre une grille particulièrement corsée, j'ai pû répondre à la question de la suffisance des règles que j'avais énoncées dans mon article sur les techniques de résolution d'un sudoku. La réponse est non, mes quatre règles ne sont pas suffisantes...
La grille me permettant de l'affirmer est la suivante :
Les petits chiffres indiquent les possibilités pour les cases indéterminées à ce stade de la résolution. En appliquant mes règles n° 2 et n° 3, on peut éliminer quelques possibilités (marquées d'une croix mauve) mais on ne peut faire mieux.
Le plus intéressant est qu'en cherchant sur Internet, j'ai trouvé quelques règles supplémentaires mais parmi ces dernières aucune de celles qui n'utilisent pas une forme ou une autre d'essai et d'erreur ne s'appliquent dans cette situation.
Le défi
Trouver une règle ne faisant pas appel au raisonnement hypothétique permettant de progresser dans la résolution de cette grille. Par raisonnement hypothétique, j'entends les raisonnements du type « Si je place/ne place pas tel chiffre dans cette case alors... ».
Manou, Fabrice, Elven ?
La grille me permettant de l'affirmer est la suivante :
Les petits chiffres indiquent les possibilités pour les cases indéterminées à ce stade de la résolution. En appliquant mes règles n° 2 et n° 3, on peut éliminer quelques possibilités (marquées d'une croix mauve) mais on ne peut faire mieux.
Le plus intéressant est qu'en cherchant sur Internet, j'ai trouvé quelques règles supplémentaires mais parmi ces dernières aucune de celles qui n'utilisent pas une forme ou une autre d'essai et d'erreur ne s'appliquent dans cette situation.
Le défi
Trouver une règle ne faisant pas appel au raisonnement hypothétique permettant de progresser dans la résolution de cette grille. Par raisonnement hypothétique, j'entends les raisonnements du type « Si je place/ne place pas tel chiffre dans cette case alors... ».
Manou, Fabrice, Elven ?
Par Étienne
-
Publié dans : Échecs et jeux mathématiques
Ecrire un commentaire - Voir les 13 commentaires
Ecrire un commentaire - Voir les 13 commentaires
Commentaires
La tourterelle
Dans un parc à Chartres
Articles récents
- Racing Métro 92 - La Rochelle
- La tempête se lève
- Je connais tous les chemins de mon pays
- Bac de philo, c’est tous les jours
- La fête de la musique
- Les grenouilles qui tournent
- Le premier anniversaire de la semaine
- Au cirque
- Il fait beau on sort dehors !
- Nos pensées (de parents) du moment
Catégories
- lestourtereaux (165)
- Travaux (66)
- Actualités (22)
- Évasions (47)
- Contes, récits et poèmes (19)
- Citations (11)
- Échecs et jeux mathématiques (14)
- Gourmandise (7)
- Aiguilles et tissus (8)
- Silicium (15)
- À découvrir (9)
- La société de consommation (6)
- Le dico québécois (41)
Calendrier
| Mai 2012 | ||||||||||
| L | M | M | J | V | S | D | ||||
| 1 | 2 | 3 | 4 | 5 | 6 | |||||
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||
| 14 | 15 | 16 | 17 | 18 | 19 | 20 | ||||
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | ||||
| 28 | 29 | 30 | 31 | |||||||
|
||||||||||
Pour un premier concours de Sudoku su mon blog j'avais mis la barre très haut.
J'ai également eu une fois une grille qui à un moment donné permettait plusieurs solutions différentes. C'est assez amusant aussi.
Comment j'ai trouvé cette grille.
J'ai un petit logiciel sur mon palm (Sudoku) qui permet de lancer une conception aléatoire de grille. Il ne reste plus qu'à trouver la solution.
Généralement les grilles sont "normales" mais celle là m'avait donné du fil à retordre...
A bientôt
Une nouvelle grille plus simple mais je ne suis pas certain que les 4 règles de résolution ne coincent pas ... à un moment.
Et pour Bestiolle, il me semble que les sudoku ne doivent admettre qu'une solution et une seule pour être vraiment valides. Enfin perso en tout cas je préfère (pour que la logique aille jusqu'au bout) cette définition :-)
J'y ai également trouvé de nombreuses opinions sur ce qu'est un sudoku considéré comme « intéressant ». À peu près tout le monde s'accorde sur le fait qu'il ne doit y avoir qu'une seule solution mais les opinions sont partagées sur le fait qu'un sudoku devrait pouvoir être soluble sans faire appel à un processus d'essai et d'erreur (guessing en Anglais). Ce qui semblerait indiquer que les ensembles de règles que l'on retrouve sur la toile ne sont pas suffisants pour résoudre tous les problèmes.
Finalement, sur SourceForge, il y a déjà toute une panoplie de logiciels permettant de résoudre ou de créer des sudoku que ça ne vaut pas la peine de passer du temps à en écrire un, surtout que le nombre total de grilles complètes est maintenant connu et qu'il est possible de les énumérer rapidement (au sens où étant donné un entier entre 1 et N, où N est le nombre de grilles complètes possibles, on peut lui associer une grille complète et réciproquement).
Etant en master d'informatique je me suis amusé à ecrire un résolveur de sudoku
J'ai donc essayé quelques grilles avant de tomber sur celle la .
Après avoir passé cette grille dans mon résolveur il affirme que celle ci (enfin j'ai utilisé celle du site originale) n'est résolvable que si l'on effectue un choix au hasard.
Pour les gens intéressés mon logiciel (en JAVA) sera disponible dans quelque jours sur mon site perso :
http://ogz.free.fr
Je le mettrais en ligne dès que j'aurais réussi à trouver l'algo pour créer des grilles difficiles (pour l'instant il les résoud et en crée des simples seulement !!)
@+
La résolution du défi est assez simple. Tu peux d'abord exclure le 8 de la colonne 2 des carrés 1 et 4 (puisque le 8 se trouve obligatoirement dans le carré 7 2ème colonne.
Ensuite il faut utiliser la méthode des couleurs. Il te faut colorier les cases avec deux couleurs différentes lorsque deux possibilité et seulement deux sont possibles sur un carré,une ligne ou une colonne. Dans ton cas, on fait la méthode sur le 1. Dans le deuxième carré, deux cases sont possibles pour le 1. Je colorie la première en bleu et l'autre (col 5) en jaune. Par suite, le 1 (col 5 carré 5) est en bleu ainsi que le 1 col 3 lign 3 carré 1. Par suite le 1 colonne 2 carré 4 est en jaune et le 1 col 2 lign 2 en bleu, le 1 col 3 lign 5 en bleu. on peut alors enlever tous les 1 des cases reliées directement à des cases de couleurs différentes. Tu peux enlever le 1 des cases col 2 lign 2, col 3 ligne 3, col 3 lign 5, col6 ligne 2, ...
Tu termine ensuite facilement ton sudoku.
La méthode des couleurs est intéressante mais on peut débattre s'il s'agit ou non d'une technique d'essai-erreur. En fait, une couleur représente simultanément deux raisonnements : « Que se passe-t-il s'il y a ou s'il n'y a pas de chiffre x dans telle case ? ». Le fait qu'il y ait plus d'une case de la même couleur dans un même groupe nous permet effectivement d'éliminer le chiffre x dans toutes les cases de la même couleur, sinon il y aurait impossibilité (i.e. les deux cases doivent contenir le chiffre x selon l'arrangement des couleurs).
Pour honorer ton long commentaire, le sudoku en cours de résolution avec les cases colorées :
Vous trouverez un excellent logiciel d'aide à la résolution, entièrement logique quand cela est possible à l'adresse ci-dessus. Ce logiciel est entièrement gratuit de surcroit
http://angusj.com/sudoku/
Fabrice
Une piste possible pour une cinquième règle...
Sur l'exemple que tu cites, le carré central possède deux cases ayant un même choix (5,6), tandis que le carré de dessous offre une case (5.6) et une case (5.6.8). On déduit de la règle n°5 qu'il faut inscrire 8 dans la case présentant trois choix. (La résolution du reste s'avère alors d'une facilité déconcertante...)
Règle n°5 :
Si deux cases placées dans des carrés distincts et dans un même groupe (colonne ou ligne) offrent un même choix de deux chiffres possibles,
et si dans un des deux carrés on retrouve encore ce même double choix dans une seconde case, tandis que dans l'autre carré, on trouve une case située dans un même groupe que la case précédente, présentant un choix triple comprenant les deux chiffres précédement énoncés,
alors cette dernière a pour valeur le troisième chiffre possible pour cette case.
(Sinon, en effet, la grille aurait deux solutions possibles).
Cependant, cette règle n'est valide qu'en sachant que la solution est unique (c'est ce que tu indiques à la fin de ton texte), ce qu'à priori on ne sait pas...
Si, André a parfaitement raison, d'autant qu'une des règles fondamentales du Sudoku est que chaque grille n'a qu'une solution unique. Une des astuces est donc de supprimer tous les candidats conduisant à des grilles présentant plusieurs solutions possibles. A cet effet, l'exemple choisi par André est juste.
En variante un peu plus sioux à la proposition d'André : il y a un doublon 7-8 en bas de colonne 2. En bas de colonne 7, les deux dernières cases, on a 7-8-9 et 6-7-8. Le 7 est obligatoirement dans une de ces deux cases. Or si on avait aussi un 8, on aurait deux doublons parallèles 7-8 qui donneraient à la grille deux solutions possibles : les 7 en B8/G9 avec les 8 en B9/G8, ou vice-versa. Le vice-versa n'étant pas acceptable, le 7 étant forcément en G8 ou G9, on en déduit que le 8 ne peut pas être dans ces deux cases.
Au final, on aboutit à la même conclusion à laquelle André était arrivé plus simplement que moi.
Cependant, si on se place d'un point de vue d'un logiciel de création/validation de grille, on ne peut pas utiliser de telles astuces puisque l'objectif sera, tout en résolvant une grille, de valider qu'il n'y a qu'une seule solution.
On pourrait également préciser que si une de ces règles s'applique, alors la grille est invalide (elle n'a pas une solution unique).
bonjour
je suis le webmaster de http://www.sudoku-gratuit.fr
si vous voulez d'autre sudoku diabolique ou des variantes de sudoku, allez sur mon site
Pour installer sudoku sur facebook, blog ou siteweb consulter:
http://sudoku-maroc.ma
je vous propose une méthode qui permet de résoudre le problème:
Dans la case ( 2ème ligne, 6èmè colonne) le doublet est 1, 8
ces deux chiffres ont, dans la deuxième ligne la même probabilité (ils apparaissent chacun deux fois). mais dans la 6ème colonne, le 8 n'apparait que deux fois, tandis que le 1 apparait 3 fois : c'est donc le 8 qui est le plus probable dans cette case.
Et en effet, il permet la résolution du sudoku