Sudoku sans contradictions

Julia Paule · 2 Aug

Bonjour, voici une question que je me suis posée il y a longtemps et qui me revient pendant ces vacances : est-il possible de résoudre toutes les grilles de Sudoku sans faire de suppositions, c'est-à-dire sans se dire par exemple : "si je mets un 2 dans cette case, alors blabla, etc, j'arrive à une contradiction, donc il n'y a pas un 2 dans cette case".
Je ne sais pas si ma question est bien claire, si elle va intéresser quelqu'un, et si la logique mathématique peut apporter une réponse à cette question.
Autrement dit, sans procéder par élimination des possibilités, mais seulement par raisonnement direct.

JFS · 2 Aug

Bonjour,

Sur les sites où l'on propose une aide à la résolution de Sudoku, et à la fin de problèmes labelisés très difficiles, bien souvent on procède par hypothèse pour voir si l'on arrive à une contradiction.

samok · 2 Aug

Bonjour,

la question est claire mais mérite d'être précisée : il y a différents bidules-dokus.

Je suppose que vous avez en tête les grilles 9x9 avec comme tuile de base des carrés 3x3.

Si vous considérez des shi-dokus de taille 4x4, avec comme tuile de base des carrés 2x2 :

-> il faut 4 indices pour que la grille soit unique

-> une fois les indices donnés, cela se résout sans hypothèse

Pour les plus grandes dimensions cela se complique très vite, et il y a des personnes plus calées que moi qui ont conclu que non, pour des histoires que de manière générale c'est un problème NP-Complet.

Si vous aviez raison, ils auraient tort.

Si vous aviez raison cela irait très vite de résoudre un $mn\times mn$-doku de tuile de base $m\times n$.

Médiat_Suprème · 2 Aug

Pour le Sudoku 9x9, les programmes que je connais mettent tous en place du back-tracking, mais la très grande majorité des grilles (mais pas toutes) n'en ont pas besoin.

PS : Ce fil est placé dan un mauvais sous-forum.

Julia Paule · 2 Aug

Merci pour vos réponses. J'ai en tête les grilles 9×9 les plus difficiles. Les grilles faciles se résolvent sans faire d'hypothèses.
@JFS Il me semble que ce n'est pas parce que l'aide à la résolution sur certains sites procède par hypothèses qu'on ne peut pas faire autrement, logiquement parlant. Aurais-tu un exemple d'un tel site ?
@samok tu veux dire que ces personnes ont conclu qu'il fallait faire des hypothèses pour des grilles suffisamment difficiles ?

jelobreuil · 2 Aug

Bonsoir Julia Paule,

D'abord, tu parles de grilles de quels niveaux ? "Difficile" ? "Expert" ? de 8 à 10 sur 10 ? Parce qu'en-deça d'un tel niveau, je ne pense pas que faire des suppositions soit nécessaire ...

D'après mon expérience de ce passe-temps, je ne fais presque jamais de suppositions de la forme que tu cites, je cherche plutôt à déduire le ou les chiffres qu'on peut placer dans une case donnée à partir de ceux déjà présents dans les ligne-colonne-carré auxquels ladite case appartient et à comparer les possibilités ... Ce n'est qu'en cas de blocage total que je fais des suppositions, et cela n'arrive qu'avec des grille de niveau "top" !

Bien cordialement, Jean-Louis B.

PS : nos messages sont presque simultanés ...

samok · 2 Aug

Pour une grille de n'importe quel format donné, avec des indices donnés qui conduisent à une solution unique, la méthode sans hypothèse n'est pas la panacée. Voilà ce que j'ai compris et que je dis.

Julia Paule · 2 Aug

Merci @Médiat_Suprème . Je viens de voir ce qu'est le back-tracking. Mais c'est seulement la façon de procéder des programmes informatiques, pour des raisons d'optimisation j'imagine, et cela ne prouve pas que logiquement on soit obligé de faire des suppositions.
Je viens de faire une grille de Sudoku en faisant au moins 4 ou 5 suppositions sans arriver à une contradiction. La solution est différente de la mienne. On peut en conclure que cette grille est fausse (il faut une solution unique).

JLapin · 2 Aug

Je ne vois pas comment se passer du raisonnement par disjonction de cas pour les Sodoku les plus difficiles.

Georges Abitbol · 2 Aug

J'ai trois réponses :

1) Je ne sais pas si la question a vraiment un sens. Quand tu te dis "il faut qu'il y ait un 1 dans cette ligne, et il ne peut être ni là, ni là, ni là, donc il est là", est-ce que tu fais un raisonnement avec des suppositions ? D'une certaine façon, tu te dis "s'il est là, alors il y a un problème parce qu'il y a déjà un 1 là, donc il n'est pas là". Cela arrive souvent en logique, d'avoir des questions qui semblent avoir un sens, mais qui n'en ont pas vraiment. Genre "peut-on démontrer le corollaire Y sans démontrer le théorème X", qui, souvent, a la réponse triviale qu'il suffit de détricoter la démonstration qu'on a déjà de X pour l'adapter au cas particulier de Y et du coup la camoufler... Mais bon, pour le sudoku, j'avoue que moi-même, je trouve la question intéressante.

2) Exercice : regarder la vidéo https://www.youtube.com/watch?v=pezlnN4X52g&pp=ygUUc3Vkb2t1IGNvbXB1dGVycGhpbGU%3D et se demander s'il n'existe pas un nombre énorme de variantes de l'astuce présentée qui pourraient suffire.

3) Exercice : programmer soi-même un résolveur de sudoku simple, avec un mode "sans supposition" que l'on définit soi-même, et le tester sur des sudokus divers et variés. Là, il y aura une réponse !

Julia Paule · 2 Aug

Merci @jelobreuil je procède de la même façon.
@samok d'accord, la méthode sans hypothèse n'est peut-être pas la meilleure ou la plus rapide, mais cela ne répond pas à ma question, à savoir si on peut toujours raisonner par déduction directe (sans raisonnement par l'absurde) même si c'est très compliqué pour l'esprit humain.

samok · 2 Aug

Quand je disais que ce n'était pas la panacée ce n'est pour des raisons d'optimalité ou autre (genre l'élégance) mais qu'elle ne permettrait pas d'aboutir pour toutes les grilles et indices donnés qui conduisent à solution unique.

Et je me répète je ne parle pas que des grilles 9x9.

raoul.S · 2 Aug

Georges Abitbol a dit :
3) Exercice : programmer soi-même un résolveur de sudoku simple, avec un mode "sans supposition" que l'on définit soi-même, et le tester sur des sudokus divers et variés. Là, il y aura une réponse !

Il y a longtemps j'avais écris un programme "sans supposition" (sans backtracking quoi) et effectivement il y avait les grilles les plus difficiles qui ne pouvaient pas être résolues par le programme. Mais je n'ai pas pu déterminer si ce n'est pas moi qui n'avait pas programmé assez de "raisonnements logiques" sans backtracking.

JFS · 2 Aug

Un site où pour les grilles difficiles où on utilise la méthode de supposition
https://www.top-sudoku.com/sudoku/fr/rentrer-un-enonce-sudoku.php

Médiat_Suprème · 2 Aug

@Julia Paule : Oui, le fait qu'une grille particulière ne se résolve pas avec les critères courants, mais nécessite du back-tracking (études d'hypothèses) ne prouve pas qu'il n'existe pas un critère (sans doute bien compliqué) qui évite le BT. C'est d'ailleurs ce que dit @raoul.S (je suis exactement dans le même cas

).

samok · 2 Aug

Sans supposition, par raisonnement direct, ...

si je suis sur la même table d'encodage et de décodage (avant on disait, sur la même longueur d'onde) signifie-t-il bien :?

- Dans la case (i,j) de la tuile t(i,j) : un nombre est donné ou déduit récursivement de manière directe

-> les autres cases de la ligne i, de la colonne j et de la tuile t ne contiennent pas ce nombre : hop, on les raye

-> s'il ne reste qu'une seule possibilité dans une case alors c'est celle là : elle sera utilisée ensuite.

Je pense être en mesure de fournir une grille 6x6 où, compte tenue des indices donnés qui ne mènent qu'à une seule solution, la supposition est nécessaire (s'il on est d'accord sur la partie d'avant). Allez, pour dimanche.

lourrran · 2 Aug

Georges Abitbol a parfaitement reformulé le problème dans son point 1)
Quand on fait une supposition, parfois, sans utiliser la gomme ni le crayon, on arrive à dérouler le fil sur 2 ou 3 étapes, et à voir que ça bloque. Dont-on considérer cela comme une 'supposition' ?
Et toutes les grilles moyennes ou difficiles ont forcément des situations de ce type. Et évidemment, dans les grilles difficiles, il y a des situations où il faut dérouler tel ou tel scénario un certain temps avant de voir qu'il y a blocage, et des fois, ça ne peut pas se faire 'de tête'.
En terme de stratégie, faire des suppositions, c'est efficace, dans l'objectif de 'fermer des portes' : à tel moment, pour telle case, les nombres possibles sont 1, 2 et 3 ; j'ai le sentiment que 3 va amener à un blocage ; je mets un 3, je déroule, et je constate qu'il y a effectivement un blocage. Et donc les valeurs possibles dans cette case sont seulement 1 et 2. J'ai un peu avancé.

Pour les amateurs de jeux de ce type, j'aime beaucoup ce site ; il y a certains jeux où je bloque à peu près systématiquement, par exemple aquarium (niveau special daily)

Julia Paule · 2 Aug

D'accord @samok tu m'apportes la réponse : pour les grilles très difficiles, il faut faire des suppositions.
J'étais pourtant persuadée du contraire (avec un empilement de déductions s'écrivant des "et" et des "ou", une sorte d'algèbre de Boole quoi, permettant d'amener d'autres déductions, etc..., on pouvait s'en sortir).
@Georges Abitbol merci.
1) Dans "il y a un 1 forcément là car...", ou "il y a un 3 ou un 5 ici car ... ", ou "il n'y a ni 2 ni 7 ici car...", il n'y a pas de supposition. Mais à l'inverse on peut évidemment fabriquer une supposition artificiellement même quand il n'y en a pas besoin : "s'il n'y a pas de 1 là, alors c'est une contradiction".
2) Je vais m'accrocher pour regarder la vidéo en anglais. Petite remarque sur le lien : les grilles où moins de 7 chiffres sur les 9 sont représentés sont forcément fausses.
3) si j'arrive à programmer un résolveur de Sudoku sans supposition, j'aurais la réponse, mais cela me paraît très difficile, voire même impossible vue la réponse de samok.

Julia Paule · 2 Aug

En fait non @samok, tu parles d'un argument de problème NP-complet, qui a rapport à la complexité (je viens de le voir dans Wiki), mais pas à l'impossibilité. La résolution sans supposition est très complexe, mais pas impossible en temps fini pour quelqu'un ou une machine qui a du temps et des ressources. Je ne suis pas persuadée de l'impossibilité de la résolution de tout Sudoku, même très difficile ou très grand, sans supposition.
Je rejoins donc @raoul.S et @Médiat_Suprème.

Foys · 2 Aug

Pour l'anecdote, le backtracking est dans la correspondance de Curry-Howard ce qui distingue le raisonnement classique de l'intuitionniste. En effet le programme qui prouve $(\neg A) \vee A$ est celui qui fait une sauvegarde $s$ de l'état en cours du système et renvoie un objet $k$ typé $\neg A$ qui accomplit la chose suivante: si jamais plus tard on a un objet qui prouve $A$ (i.e. un $x$ de type $A$) l'appel de $k$ sur $x$ rétablit le système dans l'état $s$ où il avait été sauvegardé et renvoie cette fois $x$; ainsi dans tous les cas vous renvoyez bien un objet de type $A$ ou un objet de type $\neg A$ (pour contester efficacement le fait qu'un objet donné est de type $\neg A = A \to \perp$ ou même plus généralement de type $A \to B$, il est nécessaire de tester son comportement sur un objet de type $A$).

L'utilisation répétée du mécanisme précédent est bien sûr ce qu'on appelle couramment le backtracking.

Voir la "réalisabilité classique" de Jean-Louis Krivine.

Julia Paule · 3 Aug

@Foys Je ne connais pas assez la logique pour comprendre tes propos.
En fait ma question revient à : est-ce que toute supposition dans une grille de Sudoku qui mène à une contradiction peut être transformée en déduction directe ? Par exemple il existe une preuve de l'irrationalité de $\sqrt 2$ par déduction directe (autre donc que la classique démonstration par l'absurde).
(Plus généralement, est-ce qu'en mathématique, toute démonstration par l'absurde peut être logiquement transformée en déduction directe ? Je mets entre parenthèses car je ne crois pas).
Finalement cela m'apparaît assez facile d'écrire un programme de résolution du Sudoku par déduction directe (en examinant et en écrivant dans chaque case les possibilités, et en les éliminant au fur et à mesure), mais je ne saurais pas, comme raoul.S, si cette méthode permettrait de résoudre toutes les grilles.
Encore faut-il savoir comment sont fabriquées les grilles à solution unique. Certainement par un programme.

Dom · 3 Aug

Voici une ligne dans une grille 9x9 :
1-2-3-$\square$-5-6-7-8-9
Comment trouve-t-on que la case manquante contient le chiffre 4 (et pas autre chose) ?

Édit : est-ce un raisonnement « direct » ou une disjonction des cas ? (même instantanée)

GaBuZoMeu · 3 Aug

Bonjour,

Une remarque qui n'a rien de mathématique. J'ai constaté expérimentalement que dans le cas de grille "expert" où on est coincé avec les méthodes de déduction directe, il y a tout de même une heuristique qui permet souvent de faire le bon choix quand on a dans plusieurs cases des "bascules" (hésitations entre deux chiffres) : choisir la bascule et la possibilité dans cette bascule qui permet, à vue de nez, de débloquer le plus de cases possibles.

Médiat_Suprème · 3 Aug

Quelle règle peut-on appliquer à cette grille (hors BT bien sûr)

Image: https://les-mathematiques.net/vanilla/uploads/editor/bh/986rlkgf9l0l.jpg

Cyrano · 3 Aug

Dans les sudokus les plus compliqués on se sert abondamment des listes de possibilités sur chaque case. (C'est pourquoi je préfère faire mes sudokus sur l'ordi car l'annotation est plus facile)

Les techniques avancées sont notamment le X wing et le Y wing : https://sudoku.com/fr/regles-du-sudoku/y-wing/

nicolas.patrois · 3 Aug

lourrran a dit :

Pour les amateurs de jeux de ce type, j'aime beaucoup ce site ; il y a certains jeux où je bloque à peu près systématiquement, par exemple aquarium (niveau special daily)

Et moi, celui-ci (jouable en ligne, installable dans Windows et Linux)… C’est le même qui développe putty.

samok · 3 Aug

J'ai pas tout lu mais par rapport à mon intervention précédente :

le rodoku ci-dessous à compléter avec les lettres A, B, C, D, E, F en ligne colonne et bloc (les tuiles 2x3 )

ne peut se résoudre par déduction directe et a une unique solution (d'après mes savons calculs).

Médiat_Suprème · 3 Aug

Et ? Ce puzzle se résout trivialement et ne prouve ni même n'illustre quoi que ce soit.

samok · 3 Aug

Bon, très bien, le ton n'invite pas au questionnement, chalut.

Dom · 3 Aug

Quelqu’un a-t-il pu définir « raisonnement direct » ?
Par exemple, pour la grille de samok, on cherche à trouver les B.

On regarde les autres B déjà connus, on raye toutes les cases où B est interdit. On peut les nommer les cases nonB. Et alors, effectivement, dans le bloc médian de droite, il ne reste qu’une case visible : on a trouvé un nouveau B directement.

Ce raisonnement est-il ce que l’on nomme un « raisonnement direct » ? En existe-t-il d’autres ?

lourrran · 3 Aug

Je pense qu'on peut nommer ceci 'raisonnement direct'.
raisonnement direct n°1 : Dans tel bloc, il faut mettre un B, et il y a un seul emplacement possible, donc on place le B à cet emplacement. Idem en remplaçant bloc par 'ligne' ou par 'colonne'.
raisonnement direct n°2 : Dans telle case, il faut mettre un symbole, et le seul symbole possible est B, donc on place un B dans cette case.
Comme on est sur un forum de maths, j'ai envie de caser le mot 'dual' à ce moment.

Puis on a les raisonnements indirects : Dans tel bloc, je dois placer un B ; il y a seulement 2 cases possibles, et je constate que si je le place dans la 1ère, alors ça m'oblige à un certain nombre de mouvements, qui conduisent à une impasse.
Ou, raisonnement dual du précédent : dans telle case, j'ai seulement 2 valeurs possibles, mais l'une des 2 va conduire à une impasse.
Et ces raisonnements indirects peuvent être très difficiles à mener... On va parfois passer par plein de routes avant de voir que toutes ces routes sont des impasses.

Dom · 3 Aug

Dans le raisonnement 2 : il reste un truc pas clair. Que signifie « le seul symbole possible est B » ? Car ça peut faire suite à des essais erreurs etc. Ça fait penser à « de l’indirect ».

Médiat_Suprème · 3 Aug

Pour moi, un raisonnement direct est un raisonnement sans back-tracking (sans l'étude d'une hypothèse $H_1$à partir d'une position $P$, avec retour en $P$ si on aboutit à une impossibilité, et teste de l'hypothèse $H_2$ toujours à partir de $P$).
Si dans une ligne, il n'y a qu'une seule cellule qui puisse accueillir le nombre $n$, alors on peut conclure, c'est direct.

Dom · 3 Aug

N’est-ce pas un problème humain plutôt ?
On voit d’un seul coup d’œil que ladite case ne peut contenir que le nombre n.

Mais finalement, n’a-t-on pas exclu les autres possibilités en un clin d’œil ?

En fait je comprends l’histoire du « retour sur P ». Ça peut être alors de dire « retour sur P en 1 étape s’appelle un raisonnement direct » ou quelque chose comme ça.

lourrran · 3 Aug

Prenons cette grille (9x9)
??? AC? ?D?
?E? ??? ???
??F ??? ???

G?? ??? ???
H?? ??? ???
??? ??? ???

I?? ??? ???
??? ??? ???
??? ??? ???

Dans la vraie vie, on aurait aussi d'autres informations, ici ou là. En particulier dans les 4 derniers blocs, ceux où je n'ai que des points d'interrogation.
Dans la première case en haut à gauche, je ne peux pas mettre A ni C ni D, à cause de la première ligne. Je ne peux pas mettre E ni F, à cause du premier bloc, et je ne peux pas mettre G ni H ni I, à cause de la première colonne. Je ne peux mettre que B.
C'est un raisonnement direct, au même titre que : il me faut un B dans le premier bloc, et le seul endroit où je peux le mettre est dans telle case.
Sur la grille donnée en exemple, le raisonnement direct n°1 ne permet pas d'avancer.

En terme de programmation, si on ne veut pas se prendre la tête, j'ai l'impression qu'on recenserait pour chaque case la liste des lettres autorisées. Si pour une case, on a une seule lettre autorisée, on la fige. Sinon on fait du back-tracking, brutal.
Si on est un peu plus courageux, on combine les 2 axes. Est-ce que, avec le raisonnement direct n°1, je peux placer des lettres. Idem avec le raisonnement direct n°2. Et si aucun des 2 ne donne de résultat sur, on fait des hypothèses, du back-tracking.

Dom · 3 Aug

Ok. C’est en effet un cas « immédiat »
J’ai encore l’impression qu’on essaye le A… ha non. Le B ? non plus, ainsi pour les autres lettres.

Évidemment c’est très rapide.

Je pense encore (sans certitude) que c’est du cas par cas. Et que la seule chose qui change c’est qu’on revient à la configuration P en un seul coup et pas après avoir parcouru d’autres cases.

Je peux me tromper.

Et de toute manière, si j’ai raison, ça n’est pas un drame puisque l’on se met d’accord sur ce cas particulier.

lourrran · 3 Aug

Oui, mais même pour ce que j'appelais raisonnement direct n°1, on peut encore discuter : 'est-ce vraiment un raisonnement direct'.
On sait qu'on doit avoir un B dans telle ligne. Il n'est pas dans telle colonne, ni dans telle autre, etc etc . Et donc il est dans cette cellule précisément. En programmation, il faut faire une boucle... ce n'est pas vraiment direct.

Médiat_Suprème · 3 Aug

@Dom : Si on maintient la liste des valeurs possibles pour les 81 cases, dans une grille vide, toutes les cases ont 9 valeurs possibles. Quand on rentre (1 par 1) les valeurs initiales, pour chaque case remplie, les possibles passent à 1 pour cette case, et on peut retirer une valeur à chaque case de la ligne, de la colonne et du carré. C'est du raisonnement direct. Ensuite, si on passe en revue toutes les cases, celles dont les possibles sont réduits à 1 peuvent être remplie, c'est encore du direct.

samok · 3 Aug

Ok j'ai merdé avec mon rodoku : il ne prend en compte qu'une des règles de déduction directe, la plus bourrine.

Pour moi il n'y en a que deux : la deuxième est celle que j'ai omise et soulignée par sieur Dom.

Je reviendrai, c'est demain Dimanche.

Médiat_Suprème · 3 Aug

Il y a beaucoup plus de 2 types de raisonnement directs, certains ne donnent pas forcément la réponse, mais permettent de diminuer les possibles de quelques cases et l'ensemble permet de conclure (pas dans 100% des cas, d'où le back-tracking)

Dom · 3 Aug

Ok Médiat_Suprème, c’est un modèle plus clair.

On écrit dans chaque case une inscription : l’ensemble des possibilités.
Une case peut éventuellement contenir l’inscription $\{1;2;3;4;5;6;7;8;9\}$ au début.
Grâce aux informations, on réduit la taille de l’inscription.
Dès que l’inscription d’une case est un singleton on dit qu’on a trouvé la case par un raisonnement direct.
(Je paraphrase, certes, c’est pour mieux « penser »)

Médiat_Suprème · 3 Aug

C'est bien l'idée.

lourrran · 3 Aug

Tout dépend où on place la limite entre raisonnement direct et raisonnement indirect.
Si je sais qu'en case A1, il y a soit 1 soit 2, et en case A2, idem, il y a soit 1 soit 2, alors dans toutes les autres cases de la ligne A, ou dans toutes les autres cases du bloc A1:C3, il ne peut plus y avoir ni de 1 ni de 2.
C'est un raisonnement direct, ou pas ?

Médiat_Suprème · 3 Aug

Oui, puisqu'aucune hypothèse n'a été testée, on sait exactement quoi faire à chaque étape, on ne dit pas "ah ben si je mets 2 dans telle case qu'il se passe".

Julia Paule · 3 Aug

Un autre type de raisonnement direct que le classique "dans cette ligne où on a placé 1 2 3 4 5 6 7 8, on ne peut mettre qu'un 9 dans la case vide" :
Dans une ligne de 9 cases, on sait par des déductions précédentes qu'un groupe de 2 cases doit contenir 1 et 2 (on ne sait pas laquelle doit contenir 1 et laquelle doit contenir 2), qu'un groupe de 3 cases doit contenir 3 4 5 (même principe), et qu'un autre groupe de 3 cases doit contenir 6 7 8 (même principe), alors on peut mettre directement un 9 dans la case restante. C'est un raisonnement par groupes.

Julia Paule · 3 Aug

Oui @lourrran c'est bien un raisonnement direct.
Et il n'y a pas de limite à placer entre un raisonnement direct ou pas. Cela en est un ou pas.
Si on est obligé de faire une supposition pour faire des déductions liées à cette supposition et aboutir à une contradiction, on est dans un raisonnement avec supposition. @Médiat_Suprème l'a très bien expliqué. Sachant qu'un raisonnement direct peut toujours se transformer à l'aide d'une supposition artificiellement : "si je mets un 1 dans cette case située sur cette ligne où il y a déjà un 1, ça bloque, donc il n'y a pas de 1 dans cette case", mais c'est artificiel, cela reste un raisonnement direct, la supposition était inutile.
EDIT : sauf qu'un raisonnement par supposition le reste tant qu'on ne sait pas le rendre direct, et c'est le but de ma question, à savoir si tous les raisonnements par supposition peuvent se transformer en direct, auquel cas toutes les grilles pourraient se résoudre seulement par des raisonnements directs.

raoul.S · 3 Aug

L'article Wiki du sudoku donne quelques techniques avancées utilisées par les joueurs plus experts. Par exemple la X-Wing . Sur cet autre site il y a également des techniques avancées, genre swordfish.

Julia Paule · 3 Aug

L'article de Wiki dit que de nouvelles techniques sont trouvées au fur et à mesure pour faire des raisonnements directs, mais qu'il y a des cas où on est encore obligé de faire du BT, bien que les joueurs en général n'aiment pas cette technique.

Julia Paule · 4 Aug

Si on a un raisonnement par supposition $H_1$ (par exemple, on met un $2$ dans cette case) $ \Rightarrow H_2 \Rightarrow H_3 \Rightarrow H_4 \Rightarrow H_5 =$ blocage (par exemple : on a deux $7$ dans la même colonne), on ne peut pas le transformer comme ça en raisonnement direct, parce qu'en réalité c'est $H_1 \Rightarrow H_1 + H_2 \Rightarrow H_1 + H_2 + H_3 \Rightarrow H_1 + H_2 + H_3 + H_4 \Rightarrow H_1 + H_2 + H_3 + H_4 + H_5$. Donc non $H_5$ ne donne rien pour remonter la pente.
C'est une évidence, mais parfois les évidences sont bonnes à dire.

Soc · 4 Aug

Un cas que je croise rarement mais que j'aime bien: si sur une ligne, dans 2 cases vides il n'y a que 2 nombres possibles qui soient les mêmes (4 et 6) par exemple, on peut exclure ces 2 nombres des autres cases de la ligne. Évidemment cela fonctionne aussi avec n'importe quelle autre quantité que 2 et aussi dans les blocs. Je vois ça comme des "orbites".

samok · 4 Aug

Pour moi la grille ci-dessous admet une unique solution et n'est pas déductible sans supposition.

En tout cas je l'ai vérifié à la main et un programme (qui a produit cette grille) avec les deux règles de déductibilité :

- Si une valeur est déterminée alors on raye les possibilités de valeurs dans les cases de la ligne, colonne et bloc de cette case

- Si une valeur possible d'une case n'apparaît pas dans les possibilités des autres cases de la ligne, colonne ou bloc, alors c'est que c'est cette valeur qui convient.

Sudoku sans contradictions

Réponses

Bonjour!

Catégories

In this Discussion