SUDOKU VARIANTE
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.

SUDOKU VARIANTE


 
portailportail  AccueilAccueil  Grilles en lignesGrilles en lignes  Tournois du forumTournois du forum  Dernières imagesDernières images  RechercherRechercher  S'enregistrerS'enregistrer  ConnexionConnexion  
Le Deal du moment : -55%
-55% Friteuse sans huile – PHILIPS – ...
Voir le deal
49.99 €

 

 Hypothèse et raisonnement déductif

Aller en bas 
Aller à la page : 1, 2  Suivant
AuteurMessage
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 12:56

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Jeu 04/01/2007 19:06 Sujet du message: Hypothèse et raisonnement déductifHypothèse et raisonnement déductif Icon_quote

A qui s’adresse cet article :
Au sudokas qui résolvent les grilles de sudoku non triviales (bloquées par choix unique) en mettant en évidence des éliminations par un cheminement logique ; ceux qui connaissent des motifs et des techniques de résolutions « avancées », et qui lisent ou écrivent les raisonnements déductifs proposés sur les forums.

Merci d'avance pour toutes les corrections ou compléments que vous apporterez

I Introduction
Il a trois aspects qu’il faut bien dissocier avant d’en venir aux mains sur un forum dédié à notre jeu préféré :

1) La phase de recherche.
2) La rédaction
3) Le fond du raisonnement

La phase de recherche, ça ne nous regarde pas. C’est intime. Nous ne sommes pas des voyeurs.
Pour ce qui est de la rédaction, voilà un exemple :

Motif (xy-wing) : « Avec le xy-wing des cases a1(1 ou 2), d1(1 ou 3) et a4(2 ou 3), j’élimine le 3 de la case d4.
Chaine mixte : « a4=3|a4=2---a1=2|a1=1---d1=1|d1=3 élimine d4=3 »
ou : « 3.a4-2.a4 / 2.a1-1.a1 / 1.d1-3.d1 »
ALS : « ALS A :case a4=23, B : case a1=12, C case d1=13. A-2-B-1-C élimine le voyeur 3 de d4 ».
On peut aussi colorier.
Mais on peut aussi rédiger le raisonnement de cette façon :
Disjonction de cas : « a1=1 ou 2. Dans le cas a1=1 alors d1=3 et dans le cas a1=2, a4=3, on élimine d4=3 »
Par l’absurde : « Si d4=3 alors d1=1, donc a1=2, et il n’y a plus de candidats pour la case a4. Donc d4#3 ».

-> Un raisonnement présenté sous la forme « Si .. alors » se voit souvent taxé de raisonnement à hypothèse – de méthode essai-erreur (connotation très péjorative).
-> A l’inverse certains prétendent qu’en utilisant un motif (ex le xy-wing), on ne fait pas d’hypothèse…

Pourtant il est évident que c’est la même configuration, et donc la même élimination, qui se trouve justifié (rédigé) de différentes façons. Le raisonnement de fond est le même bien sûr.

Les arguments (recevables) pour défendre les motifs, et s’interdire au maximum la présentation en « si..alors » sont essentiellement d’ordre esthétique… pour la beauté de l’art en somme – ce qui dans mon esprit n’est pas du tout péjoratif !

Mais, cet article n’a pas pour but de défendre telle présentation plutôt que telle autre.
En particuliers le débat sur « la bonne/belle façon de résoudre une grille» est hors sujet ici.

Je ne veux pas non plus débattre sur l’intérêt qu’il y a (ou non) à mettre en évidence des motifs pour résoudre une grille et/ou se dispenser d’une rédaction « si..alors.. »

Mon point de départ pour cet article, c’est :
« Tous les motifs et toutes les techniques s’appuient sur les règles du sudoku et se démontrent par un raisonnement déductif ».
En d’autres termes, à moins d’utiliser une boule de cristal (ou son intuition), un sudoka qui résout une grille (qui bloque par choix unique) pratique plus ou moins consciemment le raisonnement déductif : « Si…alors… »
Pour mettre définitivement les pieds dans le plat, mon postulat de départ est : « Tout n’est que raisonnement à hypothèse ».

L’objet de ce sujet est donc de répertorier et classer les différents types de raisonnements déductifs, et la portée des techniques les plus générales de résolution d’une grille.

Par la même occasion j'espère montrer pourquoi il est illusoire de chercher des critères objectifs permettant de faire la différence entre une méthode essai-erreur et une méthode d'élimination "noble". Libre à chacun de résoudre une grille comme il l'entend, ou de ne pas se reconnaitre dans certaines résolutions, mais accuser quelqu'un de faire des hypothèses - et donc de ne pas pas résoudre une grille par la logique - c'est remettre en cause la phase de recherche (considération très subjective), mais en aucune façon la logique dudit raisonnement.

Enfin : il y a des éliminations qui reposent sur une hypothèse, une sorte de règle facultative, « un sudoku (bien posé) admet une unique solution ». Je nommerai cette "règle" : «hypothèse d’unicité»

Quelque définition pour suivre le fil
Ensemble fort
C'est une extension de la notion de jumeaux.
Un ensemble fort natif est composé de :
1) Tous les chiffres restant dans une case.
2) Toutes les positions possibles d'un chiffre dans (au choix) une ligne, une colonne ou une région.

Un ensemble fort (pas forcement natif) est une ensemble dont au moins une proposition est juste.

J'évoque la transformation d'ensemble fort :
- transports ou dérivations sont des synonymes.
- il y a transformation quand un ensemble fort est "transformé" en un nouvel ensemble fort.
exemple : {a1=1 e1=1 f1=1} est une ensemble fort natif (le seul 1 de la ligne 1 sont en a1, e1 ou f1), les chaines a1=2 / a3=2 et e2=1/e4=1 transforme l'ensemble fort en {a3=2 e4=1 f1=1}
(Pour les notation des "voisins/jumeaux" se référer à l'article de papyg sur les
chaines mixtes)
Merci à papyg pour ces remarques et les corrections qu'il m'a permis d'apporter à cet article.


II. Typologie grossière des raisonnements déductifs sur une grille de sudoku.
A. Les banalités.
Rien d’extraordinaire ici, juste des trivialités qui servent de trames à tous les raisonnements logiques que l’on peut faire sur une grille de sudoku :

1) Le coup de massue
C’est lorsqu’un candidat permet de finir la grille
Si (dans cette case il y a ce candidat) alors (je finis la grille).
Ce raisonnement n’est satisfaisant que dans le cadre de l’hypothèse d’unicité.
Il se peut que sur une grille particulièrement difficile plusieurs coups de massue successifs (ou simultanés) soient nécessaires.
C’est sans conteste lui qui permet de battre tous les records de vitesse.
Par contre c’est le raisonnement que les sudokas qui résolvent « par la logique » détestent ! Même ceux qui jouent avec l’hypothèse d’unicité. Intellectuellement c’est le moins satisfaisant de tous les raisonnements (justes) que l’on puisse imaginer.

2) Par l’absurde
Si (ce candidat dans cette case) alors (situation absurde)

La conclusion d’un tel raisonnement est qu’alors on élimine le candidat de départ.

La situation absurde peut être :
- une conclusion en contradiction avec l’hypothèse de départ
ou :
- plus aucun candidat pour une case
- un chiffre n’a plus de position possible dans une zone (une ligne, une colonne ou une région)
- un chiffre apparait deux fois dans une même zone
ou plus généralement :
- un ensemble devient sous-complet (* notion qui sera développé plus tard).

Toute les éliminations peuvent se rédiger sur ce schéma… mais éventuellement avec des raisonnements compliqués dans le ALORS.

Les éliminations par Rectangle Interdit avec l’hypothèse d’unicité sont de ce type. Un candidat est éliminé, car sinon la grille à plusieurs solutions (situation absurde)…

3) La disjonction de cas.
On étudie chacune des éventualités d’une ensemble fort (natif à priori).
Si chacune des éventualités aboutit à la même conclusion… on en tire cette conclusion.

Parmi les éventualités de départ une seule est juste (fatalement) et les autres sont fausses.

En partant d’un mauvais candidat, il est possible que des cheminements logiques différents aboutissent à des conclusions différentes. C’est un phénomène qui est source de malentendu quelques fois…
Un candidat qui a la propriété d’aboutir à deux conclusions contradictoires peut-être éliminé car il est forcement faux (s’inscrit dans le cadre du point numéro deux).
Mais un mauvais candidat n’aboutit pas forcement à une contradiction triviale (il existe des grilles de sudoku pour les quels toutes les hypothèses aboutissent à une situation de blocage par choix unique…).

Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 12:57

B. Les chaines et les arbres d’implications.
Evidemment, on ne se limite pas à un seul « Si truc Alors machin ».
On enfile les si..Alors.. comme des perles. Mais il y plusieurs façons de s’y prendre :

1) chaine d’implication amnésique ou à candidature persistante.
Voici une (petite) chaine d’implication :
Si X alors Y donc Z

a) Chaine d’implication amnésique
Si dans le raisonnement précédant Z n’est que la conséquence de Y, on dira que c’est une chaine amnésique (inutile de se soucier de X pour la suite du raisonnement).
La plupart des motifs reposent sur des chaines amnésiques.

b) Chaine d’implication à candidature persistante
A l’inverse si pour conclure Z il faut X et Y (ou même seulement X), la candidature de X est persistante.

2) Imbrication de disjonction de cas
Selon le motif :
Si X alors
ou bien A et alors…
ou bien B et alors…
ou bien C et alors…

et Si pas X alors.. .


Vous vous demandez à quoi servent des raisonnements aussi compliqués ?
… A justifier les triplets, les swordfish (3-3-3), les quadruplets… ! (en somme les raisonnements sur les ensembles complets – entre autre)


III. Technique générale de résolution
Dans cette partie je n’évoquerais pas les motifs reposant sur la règle d’unicité.

Les motifs simples ont l’avantage d’être facile à repérer, mais leur portée est limitée. A ma connaissance tous sont des cas particuliers d’une (ou même bien souvent plusieurs) techniques « générales » de résolution.
Ces techniques générales de résolution sont des cadres théoriques, avec leur vocabulaire et leur notation propre (quelque fois propre à chacun…).

Voici les cadres théoriques dont je vais parler :
Les chaines mixtes
Le coloriage
Les ALS/EQC
Les ensembles forts et les transformations (dérivations) d’ensembles forts.

Les chaines mixtes et le coloriage pour l’essentiel c’est la même chose. La nuance est que le coloriage propose en plus une « méthodologie » papier-crayon pour mettre en évidence des chaines mixtes. Mais en exploitant le marquage des candidats, on peut aussi pousser des raisonnements plus « complets »…

Les ALS/EQC et les ensembles forts sont équivalents il me semble (voir les échanges avec léon1789 à ce sujet). Mais les points de vues de départ diffèrent, et chacun de ces cadres à ses spécificités les rendant plus ou moins appropriés à certaines configurations.

1) Les chaines mixtes et le coloriage : les chaines d’implications amnésiques.
Les deux s’appuient sur des ensembles forts de deux candidats (les jumeaux) et sur des conflits entre candidats (contraintes).
a, A, b et B sont des propositions de candidat dans une case où a et A sont jumeaux (c'est-à-dire au moins une des deux propositions est vraie) et il en va de même pour b et B.
Les coloristes notent cette situation {aA} et {bB}. Ceux qui pratiquent les chaines mixtes ont chacun leur notation…Mettons qu’ils notent a-A et b-B (pour reprendre les notations de papyg)…
Quand A et b sont en conflits (au plus un est juste) :
On établit qu’au moins a ou B est juste : {aB}
En chaine mixte : a-A / b-B.

On peut rédiger le raisonnement de différentes façons.
Si un candidat est incompatible (en conflit) avec a et B alors la situation est absurde : on l’élimine.
Ou par disjonction de cas :
Code:

Ou bien a (et les candidats en conflit avec a sont éliminés)
Ou bien pas a et alors B (et les candidats en conflit avec B sont éliminés)
Dans ces chaines mixtes (ou dans les gestions de conflits et de tenailles) le « morceau » :

Code:

A / b-B correspond à l’implication : Si ( A ) Alors (pas b) et donc ( B )
En résumé : Si A alors B
Toutes les chaines d’implications amnésiques (simple – qui ne font pas intervenir d’objet) reposent sur des chaines mixtes (ou du coloriage).
Ex
Si a1=1 alors d2=3 : pour pouvoir conclure ainsi, c’est que a1=1 élimine un candidat (en l’occurrence un chiffre 1) de d2. Si l’on conclut d2=3 c’est que d1=1 et d1=3 sont jumeaux (ce sont les deux seuls candidats).

La conséquence c’est que les raisonnements par l’absurde qui se ramènent à :
Si A alors … alors (pas A), par une chaine d’implications amnésiques cache une chaine mixte.

Les chaines mixtes (et le coloriage classique) ne permettent pas de disjonction de plus de deux cas.

Il est important de noter que la majorité des motifs simples sont des chaines mixtes.

2) Une spécificité du coloriage.
Passage corrigé suite aux explications de PhB (merci PhB)

Le coloriage classique (sur la base de jumeaux) se résume à mettre en évidence des chaines mixtes.

Mais le coloriage peut s'étendre en coloriant les candidats d'un ensemble fort de plus de deux candidats (ensemble ternaire ou plus -> voir les articles de PhB à ce sujet).

Dans ce cas le coloriage donne accès aux "déplacements" (ou "transports" ou "dérivation") d'ensemble fort par des chaines mixtes.

Il s'agit alors de raisonnements qui font intervenir une disjonction de plus de deux cas.

Les raisonnements à candidatures persistantes restent prohibés pour le coloriage car les candidatures persistantes empechent "l'equivalence des marques".

3) les réseaux d’ALS et les ensembles forts.

Avec de tels réseaux on peut présenter tous les raisonnements déductifs : les candidatures persistantes, et les multiples disjonctions de cas (ce qui peut correspondre entre autre à la résolution récursive naïve d’un solveur).

Les chaines objets sont aussi de cette nature, mais elles ne permettent pas de présenter n’importe quel raisonnement. D'autre, elles sont amnésiques entre deux relations de voisinage : seuls les objets au sein des jumeaux sont succeptibles de mettre en ooeuvre des disjonction de plus de deux cas et/ou des candidatures persistantes.

Au sujet des transformations d’ensemble fort.
La dérivation :
Des ensembles forts sont des ensembles dont au moins une des propositions est vraie.
Exemple {a1=1 a1=2 a1=3} et {b1=1 b1=3 b1=4} sont deux ensembles forts natifs (dès lors que les seuls candidats possibles en a1 sont 1, 2 et 3 et en b1 1, 3 et 4).
La contrainte entre a1=1 et b1=1 permet de conclure que {a1=2 a1=3 b1=3 b1=4} est un nouvel ensemble fort.

En transformant les ensembles forts on peut justifier toutes les éliminations des mauvais candidats d’une grille (du moins je crois).
Présenté ainsi, les démonstrations s’apparentent à des arbres généalogiques : deux ensembles forts donnent un nouvel ensemble fort.
On élimine alors les candidats en contradiction avec toutes les propositions d’un ensemble fort.

Mais on peut aussi présenter les choses sous la forme de réseau mixte – inspiré des réseaux d’ALS. Voir les discutions avec léon1789.
A ma connaissance je suis le seul à pratiquer ce sport Hypothèse et raisonnement déductif Icon_confused
On utilise alors le principe des tiroirs : chaque entité (une case pour les ALS) doit être remplie par un candidat. Les contraintes limite le nombre de candidat. Si un voyeur rend l’ensemble sous-complet la situation devient absurde et ce candidat (voyeur) est éliminé.




IV Les ensembles complets.

Il y a deux raisons qui m’amènent à parler plus spécifiquement des ensembles complets :
- ils sont la base des ESC, et via le principe des tiroirs ils aboutissent à la mise en œuvre des réseaux.
- ils me donnent l’occasion de revenir sur une notion polémique et/car opaque : celle de « méthode à hypothèse ».

1) Qu’est ce qu’un ensemble complet ?
Evidemment typiquement les ensembles complets sous les n-uplets (paire, triplet, quadruplet, francs ou cachés).
Et évidemment, ce sont les « presque » n-uplet francs qui servent intégralement de support au ESC.
Par un jeu de miroir, on peut étendre un peu la notion d’ensemble complet.
Tout le monde connait la dualité entre les n-uplets francs et les n-uplets cachés.

Un n-uplet est franc lorsque n cases d’une même zone sont constituées (au plus) des même n chiffres-candidats.
En renversant les rôles :
Un n-uplet est caché lorsque n chiffres-candidats occupents les n mêmes cases (au plus) d’une zone.

Mais il y a d’autres renversements possibles.
Un x-wing est une paire de position :
On a par exemple un x-wing lorsqu’un chiffre donné (équivalent à la zone) occupe les deux mêmes colonnes (équivalent aux chiffres) pour deux lignes données (équivalents aux deux cases). On a alors une paire franche de colonnes dans les deux lignes considérées, ou bien une paire cachée de lignes dans les deux colonnes en questions…

Les deux tableaux suivants sont de même nature :

Code:

Les candidats en ligne 1
a b c d... cases
1 X o X o o...
2 X o X o o...
3 X ...
...
chiffre

paire cachée 12 en a1 c1


Code:

Les 1 dans la grille
a b c d... colonne
1 X o X o o...
2 X o X o o...
3 X ...
...
ligne

x-wing ligne 1 et 2 (sur les colonnes a et c)

La notion d'ensemble complet ne se limite donc pas au n-uplet franc : il y a des ensembles complets de positions et un n-uplet caché et aussi un n-uplet franc en renversant les rôle des cases et des chiffres.

2) Le principe des tiroirs.
C’est le principe simple qu’on utilise sur les ensembles complets :
Pour remplir n entités avec des objets différents, il faut au moins n objets.

Et c’est ce principe qui est aussi à la base des ESC.
Un réseau d’ESC qui devient sous-complet est un réseau d’ESC qui a moins de libertés que de contraintes. La différence (liberté – contrainte) évalue en quelque sorte le nombre d’objets disponibles. Si un voyeur en fait trop disparaitre : on ne peut plus remplir tous les tiroirs-ESC…

Un dernier mot encore : les ESC se limitent à des ensembles de cases q ui forment des presque n-uplets francs. Mais on peut assouplir encore les choses pour obtenir des réseaux d’ensembles presque complets qui ne sont plus nécessairement des n-uplets presque francs.
On peut par exemple intégrer dans un réseau d’ESC des presque n-uplets cachés, ou des presque swordfish.
Un peu dans l’esprit des chaines objets qui étendent, assouplissent et rendent plus puissantes les chaines mixtes…

3) « Méthode à hypothèse » ?
Il y a à mon avis deux raisons pour lesquels beaucoup de motifs et de techniques générales privilégient les jumeaux :
- il y est plus facile de travailler sur deux éventualités que sur trois…

mais surtout :
- dès qu’un des jumeaux est faux, alors l’autre est vrai.

Presque plus personne ne dit qu’un motif qui ne met en œuvre que des jumeaux, est une méthode à hypothèse ou une technique essai-erreur… avec tout ce qu’il y a de péjoratif dans ces expressions. D’ailleurs s’interdire ces méthodes c’est se limiter aux alignements…

Et par conséquent, sans doute pour dessiner une ligne de partage entre les méthodes nobles et les méthodes essai-erreur tant honnies, des définitions de « méthodes à hypothèses » sont apparues :" lorsqu’une même assertion est utilisée plusieurs fois dans le raisonnement déductif".

Ce n’est pas très clair (pour moi), mais l'idée est de pointer ce qui paraît être la spéficité de la méthode essai-erreur : la candidature persistante, et donc dans une certaine mesure les disjonctions de cas.

Car il y a un lien très fort entre candidature persistante et disjonction de plus de deux cas...
En effet : si une candidature persistante est nécessaires c'est forcement parcequ'on en déduit quelque chose sur un ensemble fort d'au moins 3 candidats ! ( = disjonction d'au moins 3 cas ! Typiquement on déduit la valeur d'une case qui au départ possédait trois candidats)


Le cas d’un simple triplet pose problème. Démontrer les éliminations causées par un triplet oblige à des candidatures persistantes (et une disjonction de cas) :

Avec un triplet franc : a1=123 a2=123 a3=123
On peut évidemment éliminer a4=1…
Mais pour le démontrer de façon élémentaire – sans le principe des tiroirs :

si a4=1 alors
ou bien a1=2 alors a2=3 et il n’y a plus de candidat pour a3 (absurde) : candidature persistante de a1=2 et a4=1
ou bien a1=3 alors a2=2 et il n’y a plus de candidat pour a3 (absurde) : candidature persistante de a1=3 et a4=1
Donc a4=1 est absurde.

En implications "élémentaires" :

Code:

a4=1 => a1=2 ou 3
a1=2 et a4=1 => a2=3 a4=1 et a1=2 et a2=3 => a3 vide
a1=3 et a4=1 => a2=2 a4=1 et a1=3 et a2=2 => a3 vide
conclusion a4=1 impossible


Si on s’autorise le principe des tiroirs, il n’y a plus de problèmes, mais tout les travaux de léon1789 montre alors qu’avec le principe des tiroirs (les réseaux d’ESC) aucune méthode n’est plus à hypothèse, puisque toutes peuvent se traduire en ESC !

Evidemment le même problème se pose avec les swordfish, les quadruplets et les ESC en général…

S'interdire de telles "méthodes à hypothèse" parce qu'elles correspondent aux "méthodes essai-erreur" contraint à ne plus appliquer les triplets...!!!


Quelques liens (réseaux d'ESC et réseaux mixtes)
Technique ESC
et en particuliers : Traduction d'un raisonnement persistant par ESC

Réseaux (mixte) d'ESC - hypothèse imbriquée

Et la désormais référence :
Technique ALS/EQC/ESC

Sans oublier : Technique : Chaîne de Jumeaux/Voisins (de papyg)

Dernière édition par dxp le Dim 04/02/2007 0:50; édité 3 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 12:57

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Jeu 04/01/2007 21:48 Sujet du message: Re: Hypothèse et raisonnement déductifHypothèse et raisonnement déductif Icon_quote



dxp a écrit:

1) Le coup de massue
C’est lorsqu’un candidat permet de finir la grille
Si (dans cette case il y a ce candidat) alors (je finis la grille).

Ce raisonnement n’est satisfaisant que dans le cadre de l’hypothèse d’unicité.
Il se peut que sur une grille particulièrement difficile plusieurs coups de massue successifs (ou simultanés) soient nécessaires.
C’est sans conteste lui qui permet de battre tous les records de vitesse.
Par contre c’est le raisonnement que les sudokas qui résolvent « par la logique » détestent ! Même ceux qui jouent avec l’hypothèse d’unicité. Intellectuellement c’est le moins satisfaisant de tous les raisonnements (justes) que l’on puisse imaginer.
Je poursuis... Ce(s) coup(s) de massue ressemble(nt) à un (des) joker(s) que l'on joue "par miracle" pour continuer la résolution de la grille. Hypothèse et raisonnement déductif Icon_evil
Il est clair que de tels coups ne conviennent pas du tout dans le cadre d'une explication/démontration de résolution : comment expliquer que l'on "intuite" g4=3 ? ...le prétexte que le coup permet de trouver une/la solution n'est évidemment pas satisafaisant ! ...sinon autant donner directement "par miracle" la solution de la grille... un méga coup de massue sur toutes les cases en même temps ! Hypothèse et raisonnement déductif Icon_wink

Pour aller plus loin, si je ne me trompe pas, il existe une conjecture (en clair, un théorème qui a l'air vraiment vrai, mais pas vraiment démontré) : sur toute grille à solution unique, il suffit de révéler (seulement) deux cases bien choisies pour la résoudre en choix uniques.
Ceci veut dire que toute grille est trivialisée par deux coups de massue bien placés... on est donc l'intérêt de mettre des coups de massue ???
Hypothèse et raisonnement déductif Icon_smile
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 12:58

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Jeu 04/01/2007 22:28 Sujet du message: Re: Hypothèse et raisonnement déductifHypothèse et raisonnement déductif Icon_quote



dxp a écrit:

2) Une spécificité du coloriage.
Le coloriage, s’appuyant sur des marquages de candidats peut être poussé pour marquer les conséquences d’une hypothèse. Et par la même mettre en place des chaines d’implications à candidature persistante.
C'est une différence importante avec les chaînes mixtes (ou d'objets) je trouve !

Parmi les 4 types de raisonnements étudiés (chaînes, coloriage, réseaux d'ESC, ensembles forts), seules les chaînes (mixtes ou d'objets simples) sont "amnésiques"... et sont loin de pouvoir résoudre les grilles les plus ardues... à moins que l'on considère des chaînes de sous-réseaux d'ESC par exemple (règle i+, pub Hypothèse et raisonnement déductif Icon_wink )
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 12:58

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Jeu 04/01/2007 23:03 Sujet du message: Re: Hypothèse et raisonnement déductifHypothèse et raisonnement déductif Icon_quote

Merci leon1789 pour toutes ces remarques et précisions.



leon1789 a écrit:


dxp a écrit:

2) Une spécificité du coloriage.
Le coloriage, s’appuyant sur des marquages de candidats peut être poussé pour marquer les conséquences d’une hypothèse. Et par la même mettre en place des chaines d’implications à candidature persistante.
C'est une différence importante avec les chaînes mixtes (ou d'objets) je trouve !
C'est exact ! Mais j'attends l'avis d'un coloriste avant de m'avancer plus car je ne suis pas certain que les coloristes apprécient beaucoup un tel marquage d'hypothèse...
De plus il n'est pas exclus que certaine subtilité dans les raisonnements par coloriage m'est echappées.
Enfin toujours pour ce qui est du coloriage, il me semble qu'on peut étendre le coloriage a des ensembles forts de plus de 2 candidats (jumeau). On ferait alors du multi-coloriage non plus bi-chromatique, mais multi-chromatique. La gestion des conflits et des tenailles doit tenir il me semble. Ce type de coloriage deviendrait donc aussi puissant que les réseaux d'ESC ou les réseaux "mixtes".

(et bravo pour la nouvelle règle i+ et le découpage en sous-réseaux)
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:05

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 05/01/2007 11:12 Sujet du message: Re: Hypothèse et raisonnement déductifHypothèse et raisonnement déductif Icon_quote



dxp a écrit:

C'est exact ! Mais j'attends l'avis d'un coloriste avant de m'avancer plus car je ne suis pas certain que les coloristes apprécient beaucoup un tel marquage d'hypothèse...
Pour moi (non spécialiste du coloriage), un tel marquage révèle des possibilités étendues pour cette méthode (tout comme les ens. forts ou les réseaux d'ESC capable de "traduire" un raisonnement avec hypothèse).



dxp a écrit:

(et bravo pour la nouvelle règle i+ et le découpage en sous-réseaux)
Merci Hypothèse et raisonnement déductif Icon_smile ... mais cela devient vraiment une usine à gaz maintenant.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:05

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Dim 07/01/2007 13:00 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Un petit complément, en attendant les lumières d'un coloriste chevronné :

A la lecture de la solution proposée par PhB pour la grille 117 de papyg :

Le coloriage permet aussi la disjonction de plus de deux cas, par l'emploi des conflits ternaires (ou plus).
Typiquement : quand tous les candidats d'une case sont coloriés (de façon différentes bien sur) alors exactement une des couleurs est juste.

C'est donc à la fois un conflit (une contrainte / ensemble faible) et une
tenaille (un ensemble fort).

La gestion de ses "conflits - tenailles" permet entre autre de déterminer des équivalences de couleurs (et donc des fusions de nappes).

Cependant, ce n'est à priori pas suffisant pour traduire tous les raisonnements.



Les coloristes - comme tout le monde - adaptent leur outil selon les besoins : j'imagine que quand les besoins s'en font sentir un coloriage "multi-teinte" est envisageable.

Les coloristes intègrent déjà la gestion d'ESC (des paires qui apparaissent sous une hypothèse) pour établir des conflits, des tenailles ou des fusions de nappes en mettant donc en oeuvre des raisonnements qui ne sont pas 100% coloriage.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:05

PhB
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 14 Déc 2005
Messages: 369




Hypothèse et raisonnement déductif Icon_minipostPosté le: Mar 09/01/2007 18:06 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Bonjour dxp,

En lisant votre article, je ne vois pas nettement ou commence le travail de déduction dans la partie consacrée au coloriage.



Code:

A B C D
------------------------------------------
1 | 1Axx xxxx xxxx 1X2Y4Z
2 | 1a3A xxxx xxxx 3a2A


Il me semble que c'est votre figure de départ. Est-ce bien le cas ?

J'avoue ne pas très bien saisir ce que veut dire la "candidature persistante de A1=1". Voulez-vous dire qu'en présence de cette figure, il n'y a pas d'autres possibilités que A1=1 ?

Merci de vos précisions,
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:05

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Mar 09/01/2007 18:16 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

En a1 il faut imaginer qu'il y a d'autre candidats possibles.

En marquant a1=1 par A, alors on marque aussi A :
a2=3, d2=2 et : d1=4 !

La candidature de a1=1 est "persistante" car il faut tenir compte de a1=1 et de d2=2 pour conclure d1=4.

Le schéma logique est le suivant :
a1=1 => a2=3 => d2=2 => (en se souvenant de a1=1) d1=4.

Les choses seraient différentes si les deux seuls candidats de d2 étaient 2 et 4.

Ce n'est qu'une minuscule illustration, et je n'y met pas réellement en oeuvre du coloriage.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:06

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 03/02/2007 19:06 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

J'ai corrigé mon article en tenant compte des remarques de PhB (le coloriage necessite l'équivalence des marques et donc interdit les candidatures persistantes).

Merci Papyg pour le lien vers GEM : je n'ai pas encore trouvé le temps d'éplucher ça.

Par ailleurs, le coloriage tel que le pratique Joel m'intrigue : j'espère également trouver le temps de comprendre la "portée" de cette approche.


Dernière édition par dxp le Dim 04/02/2007 0:54; édité 1 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:06

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Dim 04/02/2007 0:53 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Article complété/corrigé. Merci Papyg. S'il reste des points obscurs : me les signaler...
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:06

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 7:47 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



Code:
+---------------------------+---------------------------+---------------------------+
| 9 123 5 | 8 12 34 | 7 6 134 |
B Bb Aa

| 134 7 6 | 15 9 45 | 234 8 234 |
B b A

| 123 8 124 | 23 7 6 | 14 5 9 |
A a
+---------------------------+---------------------------+---------------------------+

couleurs A,a sur les 3 de la ligne 3 et maison 2 ;
couleurs A,a sur les 4 de la maison 2 ;
couleurs B,b sur les 1 de la ligne 2 et maison 2 ;
couleurs B,b sur les 2 de la ligne 1 ;

On peut alors conclure que A=B : en effet,
a3=3 (A) et f2=4 (A) implique a2=1 (B), donc A -> B
b1=2 (B) et a2=1 (B) implique a3=3 (A), donc A <- B

Ce raisonnement est-il valable pour fusionner les nappes A,B et a,b ?
Il y a-t-il un truc ternaire ?
Il y a-t-il candidatures persistantes ?

Personnellement, je réponds oui aux trois questions.
Et vous ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:06

PhB
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 14 Déc 2005
Messages: 369




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 10:27 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Je crains que votre raisonnement soit incomplet ici. Vous dites :
- A juste => B juste
- B juste => A juste

Ce n'est pas suffisant pour en conclure que A = B. Vous devez aussi prouver que:
- A faux => B faux
- B faux => A faux

Dans ce cas de figure, ça marche, mais cela ne sera pas garanti tout le temps.

En fait, il y a un moyen beaucoup plus simple de conclure a la fusion des nappes A et B en complétant le coloriage:


Code:

A B C D E F G H I
+-------------------+------------------+-----------------+
1| 9 123 5 | 8 12 34 | 7 6 134 |
| B | Bb Aa | |
2| 134 7 6 | 15 9 45 | 234 8 234 |
| B | bB Aa | |
3| 123 8 124 | 23 7 6 | 14 5 9 |
| A | Aa | |
+-------------------+------------------+-----------------+

D2=1b5B, F2=4A5a
Or D2+F2=5 (jumeaux en ligne 2) => fusion des nappes A et B avec B=A
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:07

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 10:41 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



PhB a écrit:
Je crains que votre raisonnement soit incomplet ici. Vous dites :
- A juste => B juste
- B juste => A juste

Ce n'est pas suffisant pour en conclure que A = B. Vous devez aussi prouver que:
- A faux => B faux
- B faux => A faux
Vos craintes sont légitimes, mais en réalité il n'y a jamais de problème :
"A faux => B faux" est équivalent "B vrai => A vrai"
"B faux => A faux" est équivalent "A vrai => B vrai"
(car une couleur est soit fausse soit bonne.)

Ainsi A=B dès lors que "A vrai <=> B vrai" ou "A faux <=> B faux".



PhB a écrit:

En fait, il y a un moyen beaucoup plus simple de conclure a la fusion des nappes A et B en complétant le coloriage:
Effectivement ! A force de vouloir simplicifier l'exemple, j'ai oublié de vérifier s'il n'y avait pas un chemin direct.
Je revoie donc ma copie Hypothèse et raisonnement déductif Icon_redface et je réitère mes questions sur le même exemple moins simplifié (aucun court-circuit cette fois, je crois) :


Code:

+--------------------------+-------------------------+--------------------------+
| 9 12345 1345 | 8 12 34 | 7 13456 13456 |
B Bb Aa

| 134 7 6 | 125 9 245 | 2345 8 2345 |
B b A

| 123 12458 12458 | 2357 257 6 | 1245 1245 9 |
A a
+--------------------------+-------------------------+--------------------------+

couleurs A,a sur les 3 de la ligne 3 et maison 2 ;
couleurs A,a sur les 4 de la maison 2 ;
couleurs B,b sur les 1 de la ligne 2 et maison 2 ;
couleurs B,b sur les 2 de la ligne 1 ;

On peut alors conclure que A=B et a=b : en effet,
a3=3 (A) et f2=4 (A) implique a2=1 (B), donc A => B
b1=2 (B) et a2=1 (B) implique a3=3 (A), donc A <= B

Ce raisonnement est-il valable pour fusionner les nappes A,B et a,b ?
Y a-t-il un truc ternaire ?
Y a-t-il candidatures persistantes ?

Personnellement, je réponds oui aux trois questions. Et vous ?


Eliminations possibles :
f2#2 car e1=2 (b) ou bien f2=4 (A)
b1#4 car b1=2 (B) ou bien f1=4 (a)

Comment vos outils (chaînes mixtes, ens. forts, ESC, réseau mixte, etc.) vous permettent-il les mêmes éliminations ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:07

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 19:46 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



leon1789 a écrit:

Ce raisonnement est-il valable pour fusionner les nappes A,B et a,b ?
Y a-t-il un truc ternaire ?
Y a-t-il candidatures persistantes ?

Personnellement, je réponds oui aux trois questions. Et vous ?

Moi aussi !

Je n'ai peut-être pas assez insisté, mais les disjonctions de plus de deux cas et les candidatures persistantes sont les deux faces d'une même médaille (c'est essentiellement une question de présentation)



Code:

+--------------------------+-------------------------+--------------------------+
| 9 12345 1345 | 8 12 34 | 7 13456 13456 |
B Bb Aa

| 134 7 6 | 125 9 245 | 2345 8 2345 |
Bxy b A

| 123 12458 12458 | 2357 257 6 | 1245 1245 9 |
uvA a
+--------------------------+-------------------------+--------------------------+

Il y a deux conflits/tenailles ternaires : {Auv} et {Bxy}

Les conflits [Bu] et [Bv] se réduisen en une conflit (au plus un de juste) : [Buv]
On obtient alors : [a A][uv B] qui donne [aB] (ou {Ab}) soit B => A
Idem de l'autre côté...

Le reseau complet est un peu retord (mais je vais finir par le sortir). Voila en tout cas la première élimination sous forme de réseau mixte (je le présente sous la forme d'une chaine mixte avec deux chemins parallèles issus du "ternaire") :



Code:

|2.a3 ------------- 2.b1|
4.f2/4.f1 - 3.f1/3.d3 - 3.a3| B |2.e1
A a A a |1.a3 - 1.a2/1.d2 - 1.e1| b
B b B

Puisque c'est un reseau mixte, on peut forcement le traduire en ESC, mais dans la mesure ou il y a beaucoup de jumeau de position (et peu de paires de candidats en case) se sera un peu plus laborieux...

La redac en ensemble fort c'est un mélange du coloriage et du reseau mixte... (Tout dépend de la présentation que l'on souhaite : ou bien en reseaux, ou bien sous forme "généalogique").
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:09

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 20:48 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



dxp a écrit:

Il y a deux conflits/tenailles ternaires : {Auv} et {Bxy}

Les conflits [Bu] et [Bv] se réduisen en une conflit (au plus un de juste) : [Buv]
On obtient alors : [a A][uv B] qui donne [aB] (ou {Ab}) soit B => A
Idem de l'autre côté...
On est d'accord. Je voulais juste apporter une nuance à ta phrase


dxp a écrit:

Les raisonnements à candidatures persistantes restent prohibés pour le coloriage car les candidatures persistantes empechent "l'equivalence des marques".
____________________________________________________________


dxp a écrit:



Code:

|2.a3 ------------- 2.b1|
4.f2/4.f1 - 3.f1/3.d3 - 3.a3| B |2.e1
A a A a |1.a3 - 1.a2/1.d2 - 1.e1| b
B b B
Bien joué !
On peut remarquer qu'il va falloir donner deux chaînes (similaires) pour démontrer les deux éliminations f2#2 et b1#4.
(Je ne parle même pas des deux horribles réseaux d'ESC sous-jacents...)

Alors qu'avec le coloriage, les deux éliminations arrivent en même temps, après la fusion de A et B (la fusion qui, elle, a coûté deux preuves simples).

Sur ce coup, le coloriage est quand même un peu plus "joli", non ?


Dernière édition par leon1789 le Ven 09/02/2007 22:17; édité 2 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:09

papyg
Admin
Hypothèse et raisonnement déductif RangAdmin
Hypothèse et raisonnement déductif 136

Inscrit le: 11 Oct 2005
Messages: 1130




Hypothèse et raisonnement déductif Icon_minipostPosté le: Ven 09/02/2007 22:01 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Pour dxp :

Vous avez interverti les symboles / et — dans votre réseau !

papyg
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:09

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 13:11 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

papyg vous avez raison ! Entre mes notations perso, celle des EQC et les chaines mixtes que vous proposés : j'y perd ma cabalistique... Hypothèse et raisonnement déductif Icon_twisted

Il se trouve que pour présenter des reseaux, la notation des EQC est plus adapté pour "dessiner".

Je rectifie la première chaine :


Code:


/2.a3 / 2.b1-2.e1
4.f2-4.f1 / 3.f1-3.d3 / 3.a3 | B b
A a A a \1.a3 / 1.a2-1.d2 / 1.e1-2.e1
B b B b
Dans cette chaine on voit B=>A.

L'autre chaine (qui élimine b1=4) met en évidence A=>B

Voici le reseau complet, mais la notation n'est pas celle des chaines mixtes : --- symbolise une contrainte c'est à dire un lien faible, une charnière ou encore des voisins.
Les groupes qui apparaissent sont des "jumeaux" (des ensembles forts) :


J'espère que le réseau reste lisible.


Code:

+ *
4 --- f2(4 reg 2)f1 --- f1(3 reg 2)d3 --- 3 +
4(f1)3 -- d3(3 lig 3)a3 -- 3(a2) (a3)1 --- a2(1 lig 2)d2 --- 1(e1)2
* 1 --- d2(1 reg 2)e1 --- e1(2 lig 1)b1 --- 2
+ *
Ce reseau a 12 libertés et 10 contraintes : il faut voir 3 éléments.
Les * éliminent b1=4 et les + éliminent f2=2.



Pour revenir au coloriage :
Effectivement, le coloriage simplifie beaucoup les chaines compliquées.
Et leon tu as raison.
Moralité : je vais encore devoir reprendre le paragraphe concerant la spécificté du coloriage. Mais cette fois le paragraphe va changer de titre (car les chaines objets et le chemin parallèle font comme la gestion du ternaire en coloriage... il offre de nouveau outils).

La gestion des "disjonctions de plus de 2 cas" (conflits ternaires) semble en pleine évolution pour le coloriage.

Justement : je reviens sur le lien entre ensemble fort et "conflit ternaire" (au plus).
Si {abc} et {xyz} sont deux ensembles forts (au moins une assertion de juste) et que [cxy] est un conflit/ensemble faible (au plus un de vrai) , alors : {ab z} est un ensemble fort (une tenaille).

"L'algèbre" de cette réduction peut se présenter ainsi : {ab [c}{xz] z} donne {abz}.
Preuve : Si a ou b sont vrais : a ou b sont vrais dans {ab z}
Sinon : c est vrai donc x et y sont faux donc z est vrai dans {abz}

C'est cohérent avec les chaines de conflits du coloriage.




Code:

+--------------------------+-------------------------+--------------------------+
| 9 12345 1345 | 8 12 34 | 7 13456 13456 |
B Bb Aa

| 134 7 6 | 125 9 245 | 2345 8 2345 |
Bxy b A

| 123 12458 12458 | 2357 257 6 | 1245 1245 9 |
uvA a
+--------------------------+-------------------------+--------------------------+

Bxy et Auv sont avant tout des tenailles - en tout cas ce sont des tenailles pour ce que j'en fait :

Les vrais conflits ternaires (au plus un de juste) sont [Buv] et [Axy] (on a [Bu], [Bv], [uv] et [Ax], [Ay] et [xy] )

On obtient alors : [aA][uv B] ou plus explicitement [a {A][uv} B] qui donne [aB] : B vrai => a faux => A vrai
et : [b B][xy A] qui donne [bA] soit A vrai => b faux => B vrai
[aB][bA] permettent bien la fusion des couleurs (A<=>B).

Remarque : on peut mettre en évidence la transformation des ensembles forts : {A uv} {B b} donne par le conflit [uvB] : {Ab} c'est à dire [aB].

Pour comparaison je proposerai bien une présentation en marquage d'hypothèse (façon Bonjour). A ce sujet, sur la 131 cette façon de faire m'a permis un nombre impréssionant d'éliminations... jusqu'a ce que je me rende compte qu'une de mes marques permettait de remplir toute la grille... (snif). C'était raté pour un exposé convaincant...
Hypothèse et raisonnement déductif Icon_cry
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:10

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 15:59 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Je suis surpris que dxp donne un seul réseau mixte (j'ai du mal à le lire) permettant de prouver simultanément b1#4 et f2#2. Je m'attendais à deux réseaux...

En fait, c'est qu'une net-boucle doit permettre de faire le même travail :


Code:

+--------------------------+-------------------------+--------------------------+
| 9 12345 1345 | 8 12 34 | 7 13456 13456 |
| 134 7 6 | 125 9 245 | 2345 8 2345 |
| 123 12458 12458 | 2357 257 6 | 1245 1245 9 |
+--------------------------+-------------------------+--------------------------+


3d3--3f1 | 4f1--4f2 | 4a2~~~ | 1a3 ~~~~~~~~~~~~~~~~~~~~~~~ |@
~~1a2 | ~~ 3a3 |
3a2~~~~~~~~~~~~~~~~~~~~~~~~~ | 1d2--1e1 | 2e1--2b1 | 2a3~~ |@

Cette boucle provoque l'équivalence entre 1a2 et 3a3, c'est-à-dire l'égalité entre les couleurs B et A exactement !

Dernière édition par leon1789 le Sam 10/02/2007 16:45; édité 2 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:10

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 16:21 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



Code:

+ *
4 --- f2(4 reg 2)f1 --- f1(3 reg 2)d3 --- 3 +
4(f1)3 -- d3(3 lig 3)a3 -- 3(a2) (a3)1 --- a2(1 lig 2)d2 --- 1(e1)2
* 1 --- d2(1 reg 2)e1 --- e1(2 lig 1)b1 --- 2
+ *
Lecture du reseau :


Code:

4(f1)3 se lit : dans la case f1 les candidats sont 4 ou 3 (jumeaux 4.f1-3.f1)


Code:

d3(3 lig 3)a3 se lit : les seuls 3 de la ligne 3 sont en d3 ou a3 (jumeau 3.d3-3.a3)
reg pour région.

Avec la notation des chaines mixtes de papyg (voisins séparés par | au lieu de /) :



Code:

4.a2 | 4.f2-4.f1 | 3.f1-3.d3 | 3.a3
/ | | \
4.f1-3.f1 | 3.d3-3.a3 | 3.a2 | | 1.a3 | 1.a2-1.d2 | 1.e1-2.e1
\ | | /
1.a2 | 1.d2-1.e1 | 2.e1-2.b1 | 2.a3


Le bloc :


Code:

4.a2
/ |
3.a2 |
\ |
1.a2
montre l'ensemble fort a2=134 (une relation de gémélités... sur trois candidats.

Effectivement il y a de la boucle dans l'air.

Je trouves qu'il est difficile de trouver une notation simple claire, précise, parlante et visuelle pour les reseaux (j'avais déjà ce problème avec les reseaux d'ALS qui obligent à décrire la composition des ALS avant de présenter les chaines ou réseaux).


Dernière édition par dxp le Sam 10/02/2007 21:17; édité 1 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:10

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 20:44 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

J'ai encore une question pour tout le monde ! Désolé, mais je suis un peu du genre acharné, comme Bonjour (qui nous l'a avoué il y a peu). Hypothèse et raisonnement déductif Icon_smile
Quand je regarde cette boucle


Code:

+--------------------------+-------------------------+--------------------------+
| 9 12345 1345 | 8 12 34 | 7 13456 13456 |
| 134 7 6 | 125 9 245 | 2345 8 2345 |
| 123 12458 12458 | 2357 257 6 | 1245 1245 9 |
+--------------------------+-------------------------+--------------------------+


3d3--3f1 | 4f1--4f2 | 4a2~~~ | 1a3 ~~~~~~~~~~~~~~~~~~~~~~~ |@
~~1a2 | ~~ 3a3 |
3a2~~~~~~~~~~~~~~~~~~~~~~~~~ | 1d2--1e1 | 2e1--2b1 | 2a3~~ |@
(où ~ symbolise évidemment une triplette), on n'arrive pas à prouver les deux éliminations b1#4 et f2#2 (bien qu'il soit clairement établit que 1a2 <=> 3a3). Pourquoi ? Il manque des renseignements ! ...des renseignements a priori surperflus pour réaliser la boucle, mais essentiels pour prouver ces éliminations !! Dxp a réussi à placer dans son réseau suffisament d'infos qui, vu de loin, ont l'air redondantes, mais qui permettent de conclure au final... Comment faire avec cette boucle ?

Dxp,
à part la coquille de fin de réseau 1.e1-2.e1 (et non 1.e1-1.e2), il y a un truc qui me chagrine...
Quittons l'exemple et gardons uniquement l'hypothèse e1=(12), et imaginons qu'on écrit 1.e1-2.e1, et puis aussi 1.e1-2.e1 | 1.e1-2.e1, ce qui évidemment n'apporte rien... Sauf que si on l'écrit avec ton jeu, il vient 1(e1)2 --- 1(e1)2 . Je me trompe ?
On compte alors libertés - contraintes = 2-1 = 1. Tout candidat voyant deux éléments est éliminé, même si c'est du genre


Code:
+ +
1(e1)2 --- 1(e1)2
donc e1=1! Etonnant, non ?! Hypothèse et raisonnement déductif Icon_smile Où est l'erreur ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:10

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 21:16 Sujet du message: Hypothèse et raisonnement déductif Icon_quote



leon1789 a écrit:

Dxp,
à part la coquille de fin de réseau 1.e1-2.e1 (et non 1.e1-1.e2), il y a un truc qui me chagrine...
Quittons l'exemple, et imaginons qu'on écrit 1.e1-1.e2, et puis aussi 1.e1-1.e2 | 1.e1-1.e2, ce qui évidemment n'apporte rien. Sauf que si on l'écrit avec ton jeu, il vient 1(e1)2 --- 1(e1)2 . Je me trompe ?
On compte alors libertés - contraintes = 2-1 = 1. Tout candidat voyant deux éléments éliminés, même si c'est du genre

Rrrrhhh : encore une coquille. Hypothèse et raisonnement déductif Icon_evil Merci, je vais corriger.

Je ne sais pas si j'ai tout compris mais :
1) 12 libertés - 10 contraintes = 2. Les voyeurs doivent voir 3 (!!!) assertions ?
2) C'est bien ce double aspect 1.e1-1.e2 et 1.e1|1.e2 qui semble impératif pour le reseau et qui rend ce reseau "retord".
Je pense qu'il y a moyen de s'en tirer avec une nouvelle liaison : "=" exactement un de juste (liaison à la fois faible et forte). Un lien exclusif Hypothèse et raisonnement déductif Icon_wink en somme.


Pour ce que tu proposes : c'est le premier reseau sur lequel je suis tombé. Il me semble qu'il n'est pas opérant pour deux raisons :
1) deux doubles charnières (depuis a2=1 vers d2=1 et a3=1et depuis a3=3 vers a2=3 et d3=3)
2) C'est justement le soucis des 2 liaisons qui doivent être comptées fortes et faibles.

C'est bien cette config qui m'a fait dire que le reseau était retord. c'est cette config que l'on peut sans doute aménager avec un nouveau type de liaison.

-> a2=1 et d2=1 sont aussi des jumeaux.
-> a3=3 et d3=3 sont aussi des jumeaux.

Et comme ça le reseau fonctionne pour les deux éliminations... (mais je n'ai pas encore le théorème...).
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:11

leon1789
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert
Hypothèse et raisonnement déductif 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 22:22 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Effectivement, ce n'est pas évident de faire figurer un minimum d'info pour ne pas être redondant, mais en avoir suffisament pour conclure... Il faut du temps pour maturation...

Sinon, pour mon e1=1... Je ne suis pas très clair ce soir... Fatigue, hypoglycémie, et alcool... voilà mes (minables) excuses Hypothèse et raisonnement déductif Icon_smile Mais je reprends, car il y a un truc qui me chagrine ce soir.

Bon... Imaginons une grille où une case Z n'a que deux candidats x,y. On peut alors écrire la liaison forte xZ -- yZ. On peut même l'écrire deux fois pour former la chaine mixte xZ -- yZ / xZ -- yZ. Cette chaîne n'apporte évidemment aucune info autre que Z=(xy). On pourrait même écrire 40 fois la liaison forte dans une même chaîne, cela n'aurait pas le moindre intérêt...
Cependant, si j'écris la chaîne pour jouer à ton jeu (tu sais bien, le jeu auquel tu joues tout seul Hypothèse et raisonnement déductif Icon_wink ... pour l'instant), je traduit ainsi : x(case Z)y --- x(case Z)y.

Première question : je ne me suis pas planté dans la traduction ?

Ensuite, je compte les libertés (-> 2) et les contraintes (-> 1) , la différence étant 2-1=1 ... (Ce soir, je veux détailler pour éviter de dérailler Hypothèse et raisonnement déductif Icon_smile )
Conclusion : tout candidat voyant deux (1+1) éléments de la chaîne est éliminé.
Par exemple, un candidat x voyant la case Z voit deux éléments :


Code:
+ +
x(Z)y --- x(Z)y
donc il est éliminé ! Evidemment, on n'y croit pas... mais où est l'erreur dans tout ça ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:11

dxp
Sudoka Expert
Hypothèse et raisonnement déductif RangExpert


Inscrit le: 26 Oct 2006
Messages: 164




Hypothèse et raisonnement déductif Icon_minipostPosté le: Sam 10/02/2007 23:59 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

Ah euh... ça ?

Bon ... d'acord... y'a une embrouille :

Tu regardes une charnière ! Il faut la regarder complétement

Habituelement dans mes reseaux où les assertions vues par les voyeurs sont toutes à "l'exterieur" du reseau = pas de charnière.

-> Les deux reseaux/chaines (que tu t'attendais à avoir) éliminent bien l'un et l'autre les deux candidats.
-> Je les ai mixé et ça colle (ça marche vraiment : en pointant ce qui est vu par les voyeurs le système devient bien sous-complet).
-> Mon décompte de liberté ne tient pas... j'ai fait semblant de ne pas le voir.
-> Mais d'un point de vue logique/binaire il tient : les éliminations ne sont pas une supercherie !


Il faut donc scinder les deux chaines.

Pour que les * se retrouvent à l'exterieur du premier reseau, et les + à l'exterieur du deuxième. (mais les deux reseaux obtenus ne sont pas complétement disjoint).

....
aïe
Hypothèse et raisonnement déductif Icon_eek
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif EmptyDim Juil 05 2009, 13:11

papyg
Admin
Hypothèse et raisonnement déductif RangAdmin
Hypothèse et raisonnement déductif 136

Inscrit le: 11 Oct 2005
Messages: 1130




Hypothèse et raisonnement déductif Icon_minipostPosté le: Dim 11/02/2007 14:08 Sujet du message: Hypothèse et raisonnement déductif Icon_quote

dxp et léon,

J'ai l'impression que vous vous faites bien des noeuds au cerveau...
et ne vois pas où vous voulez aller avec tout çà !

Je reprends la question initiale de léon :


Code:

A B C D E F
+---------------------+----------------------+
| 9 12345 1345 | 8 12 34 |
| 134 7 6 | 125 9 245 |
| 123 12458 12458 | 2357 257 6 |
+---------------------+----------------------+
Eliminations possibles :
f2#2 car e1=2 (b) ou bien f2=4 (A)
b1#4 car b1=2 (B) ou bien f1=4 (a)

Comment vos outils (chaînes mixtes, ens. forts, ESC, réseau mixte, etc.) vous permettent-il les mêmes éliminations ?
Je retranscris sous forme chaîne (réseau) les deux éliminations :

Code:
2e1|—1e1 / 1d2—1a2 / 1a3—|
|—2b1 / 2a3—|3a3 / 3d3—3f1 / 4f1—4f2 =>-2f2

4f1|—3f1 / 3d3—3a3 / 3a2—|
|—4f2 / 4a2—|1a2 / 1d2—1e1 =>-4b1
Si léon veut absolument une chaîne unique, il suffit de rabouter les deux Hypothèse et raisonnement déductif Icon_wink :

Code:
4f1|—3f1 / 3d3—3a3 / 3a2—|
|—4f2 / 4a2—|1a2 / 1d2—1e1 / 2e1|—1e1 / 1d2—1a2 / 1a3—|
|—2b1 / 2a3—|3a3 / 3d3—3f1 / 4f1—4f2
... et on a même une belle boucle (en supprimant le dernier maillon).

Où est le problème ?

Nota :
la simple transcription des liens de voisinage/gémellité, en respectant l'alternance,
évite bien des erreurs de raisonnement logique ... même pour les plus chevronnés !

papyg
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Contenu sponsorisé





Hypothèse et raisonnement déductif Empty
MessageSujet: Re: Hypothèse et raisonnement déductif   Hypothèse et raisonnement déductif Empty

Revenir en haut Aller en bas
 
Hypothèse et raisonnement déductif
Revenir en haut 
Page 1 sur 2Aller à la page : 1, 2  Suivant

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
SUDOKU VARIANTE :: Historique de Sudoku Factory :: Tactiques-
Sauter vers: