Le raisonnement par contradiction consiste à tester une hypothèse contrôlée et à suivre uniquement des déductions valides jusqu’à ce que la branche reste possible ou devienne impossible. Si une hypothèse viole inévitablement les contraintes du nonogramme, l’état opposé est forcé.
Il s’agit d’une logique avancée. Elle doit venir après l’épuisement de la résolution ordinaire des lignes et de la propagation des contraintes.
La règle centrale
Supposons qu’une case non résolue ne puisse être que remplie ou vide.
Supposez provisoirement qu’elle est vide.
Si cette hypothèse finit par laisser une ligne ou une colonne sans aucun motif valide, elle ne peut appartenir à aucune solution correcte. La case doit donc être remplie.
Le raisonnement fonctionne de la même façon dans l’autre sens.
La preuve est la contradiction, pas le fait qu’une branche « semble moins bonne ».
Exemple : une mauvaise hypothèse détruit un indice
Considérez cet état partiellement résolu d’un puzzle 5×5.
Lignes :
1 21241 1
Colonnes :
1 11 11 21 21 1
Après la propagation ordinaire, la grille est :
???■?
???.?
.. ?■?
?■■■?
?.?.?
Pour la branche d’exemple, supposons que R1C1 soit vide.
Cette hypothèse force la ligne 1 dans son unique motif restant, ce qui modifie ensuite plusieurs colonnes. En poursuivant uniquement avec de la logique de ligne ordinaire, la ligne 2 finit par contenir deux cases remplies séparées alors que son unique indice est 1.
La ligne 2 possède alors zéro motif valide. La branche est impossible.
L’hypothèse R1C1 = vide est donc fausse, et R1C1 doit être remplie.
Le point important est que toutes les étapes suivant l’hypothèse sont des déductions forcées ordinaires. Seul le choix initial de la branche est provisoire.
La contradiction n’est pas une devinette aveugle
Deviner à l’aveugle consiste à choisir un état parce qu’il semble plausible puis à continuer comme s’il était vrai.
Le raisonnement par contradiction garde explicitement l’hypothèse provisoire :
- choisissez un état candidat précis ;
- propagez uniquement les conséquences logiquement forcées ;
- cherchez une impossibilité nette ;
- si une contradiction apparaît, annulez la branche et validez l’état opposé ;
- si aucune contradiction n’apparaît, ne considérez pas l’hypothèse comme prouvée simplement parce qu’elle a survécu à un court test.
Une branche qui reste possible n’est pas automatiquement correcte.
Qu’est-ce qui compte comme contradiction ?
Par exemple :
- une ligne n’a plus aucune disposition compatible avec ses indices et ses cases connues ;
- un bloc continu rempli devient plus long que tous les indices compatibles ;
- les blocs encore requis n’ont plus assez d’espace pour tenir ;
- une case remplie confirmée ne peut être couverte par aucun bloc ;
- l’ordre des indices devient impossible ;
- une même case devrait être à la fois remplie et vide.
Une différence esthétique avec l’image qui se dessine n’est pas une contradiction.
Utilisez la plus petite hypothèse utile
Un bon test de contradiction commence généralement par une seule case ou un placement de bloc très contraint, pas par une longue chaîne spéculative de choix sans rapport.
Préférez les candidats dont les deux branches ont des conséquences immédiates fortes. Les contradictions sont alors plus faciles à détecter et le raisonnement reste vérifiable.
Propagez assez profondément, mais gardez la branche sous contrôle
Après l’hypothèse, utilisez les mêmes outils que d’habitude :
- motifs de ligne valides ;
- limites de placement des blocs ;
- attribution aux segments ;
- blocs terminés ;
- croisement lignes-colonnes ;
- propagation des contraintes.
N’introduisez pas une deuxième hypothèse non prouvée à l’intérieur de la première branche. Si la branche se bloque sans contradiction, revenez à l’état initial, sauf si vous entrez volontairement dans une logique de recherche ou de backtracking.
Choisissez des branches informatives, pas simplement incertaines
Chaque case indéterminée possède deux états, mais la plupart constituent de mauvais points de branchement.
Une bonne branche se trouve souvent à un endroit où l’un ou l’autre état modifierait immédiatement une ligne très contrainte. Bons candidats :
- une case partagée par seulement deux motifs de ligne restants ;
- l’extrémité d’un bloc qui n’a plus que deux placements possibles ;
- une attribution indice-segment avec exactement deux alternatives survivantes ;
- une case dont l’état remplirait ou casserait un bloc presque fixé.
Évitez de brancher sur une case très libre dans une grande zone ouverte où les deux états laissent des dizaines de possibilités. Vous créeriez un arbre spéculatif long sans donner beaucoup de levier aux contraintes.
Distinguez anticipation courte et recherche complète
Une preuve par contradiction peut être minuscule :
supposer X → une ligne croisée perd son dernier motif valide → rejeter X.
Elle peut aussi demander une cascade plus longue à travers plusieurs lignes et colonnes avant que l’impossibilité apparaisse.
Le statut logique reste le même tant que :
- une seule hypothèse provisoire est clairement identifiée ;
- chaque marque suivante est forcée sous cette hypothèse ;
- la contradiction finale est explicite ;
- aucun second choix arbitraire n’est caché dans la branche.
Dès que vous ajoutez d’autres décisions non justifiées parce que la première branche s’est bloquée, vous quittez une preuve propre par contradiction pour vous rapprocher d’une recherche générale avec backtracking.
Tenez un journal de branche
Pour les puzzles difficiles, séparez mentalement ou physiquement trois catégories d’informations :
- faits racines — états permanents prouvés avant l’hypothèse ;
- conséquences de branche — états forcés seulement tant que l’hypothèse est active ;
- conclusion de branche — contradiction explicite ou absence de conclusion pour l’instant.
Lorsque la branche échoue, supprimez toutes ses conséquences ensemble. Le seul nouveau fait permanent est la négation de l’hypothèse qui a échoué.
Lorsque la branche se bloque sans contradiction, supprimez aussi ses conséquences et revenez aux faits racines inchangés.
Cette discipline empêche les états hypothétiques de contaminer la grille réelle.
Les conséquences partagées relèvent de l’analyse de cas multilignes
Si les deux états exhaustifs d’une proposition restent possibles mais forcent tous deux la même case en aval, cet état commun est tout de même valide.
C’est une technique avancée utile, mais la preuve n’est pas « une branche a mené à une contradiction ». VeyraPlay la classe comme raisonnement multilignes à conséquence partagée / à deux voies et développe la méthode générale dans G-040.
Méthode de contradiction pas à pas
- épuisez d’abord la propagation normale ;
- choisissez une case non résolue ou un cas de bloc très contraint ;
- copiez mentalement l’état actuel ou isolez-le ;
- supposez un des états candidats ;
- propagez uniquement les conséquences forcées ;
- arrêtez immédiatement si une ligne n’a plus de motif valide ou si une autre contradiction dure apparaît ;
- rejetez l’hypothèse échouée et marquez l’état opposé sur la grille réelle ;
- relancez la propagation ordinaire depuis ce nouvel état prouvé.
Erreurs fréquentes
Considérer « je suis bloqué » comme une contradiction
Une branche qui ne produit plus de déduction peut parfaitement rester valide.
Faire plusieurs devinettes dans une même branche
Vous ne savez alors plus quelle hypothèse a provoqué la contradiction.
Rejeter une branche à cause de l’image
Seules les contraintes des indices peuvent prouver une impossibilité.
Utiliser la contradiction trop tôt
De nombreuses impasses apparentes disparaissent après une vérification soigneuse des motifs de ligne, des X, des attributions de segments et des lignes croisées récemment modifiées.
Conserver une hypothèse survivante comme un fait
Ne pas trouver de contradiction n’est pas une preuve, sauf si vous avez établi exhaustivement que l’alternative est impossible.
Place de cette technique dans la hiérarchie de résolution
Un ordre utile est :
- logique directe de ligne ;
- logique de segments et de plages de blocs ;
- déductions par motifs de ligne valides ;
- croisement et propagation ;
- raisonnement multilignes et conséquences partagées ;
- contradiction / anticipation contrôlée ;
- recherche complète ou backtracking seulement lorsque le puzzle ou le solveur l’exige.
Les puzzles conçus pour être résolus par des humains cherchent souvent à permettre la majeure partie de la progression avant l’étape finale de recherche.
Que faut-il apprendre ensuite ?
Le raisonnement par contradiction relie la résolution humaine aux idées utilisées par les solveurs informatiques : probing d’états candidats, détection de branches impossibles et, lorsque la propagation pure ne suffit plus, recherche.
FAQ
Le raisonnement par contradiction est-il une forme de devinette ?
Il utilise une hypothèse temporaire, mais la conclusion n’est déductive que lorsqu’une branche est prouvée impossible. C’est bien plus rigoureux que choisir un état et espérer qu’il fonctionne.
Que faire si les deux hypothèses restent possibles ?
Ce cas ne prouve pas encore la case choisie. Revenez à l’état initial ou cherchez une conséquence commune aux deux branches.
Les débutants doivent-ils utiliser le raisonnement par contradiction ?
En général, pas en premier. Une logique de ligne solide et la propagation résolvent une grande partie des puzzles ordinaires et sont plus faciles à vérifier.