Le gratte-ciel et le cerf-volant au sudoku : deux motifs à un seul chiffre après le X-Wing
Le X-Wing est souvent la première technique avancée qu’on apprend au sudoku : un chiffre, deux lignes, deux colonnes, un rectangle parfait. Le problème, c’est que ce rectangle parfait se présente rarement. Plus souvent, la grille offre un rectangle presque parfait : un des quatre coins est décalé d’une ou deux colonnes, ou l’une des deux lignes est remplacée par une colonne. On a alors l’impression d’être passé tout près d’une déduction, sans pouvoir la faire.
Ces rectangles imparfaits ne sont pas des échecs. Deux d’entre eux sont des techniques à part entière, avec un nom chez les joueurs avancés : le gratte-ciel (Skyscraper en anglais) et le cerf-volant (2-String Kite, littéralement « cerf-volant à deux ficelles »). Comme le X-Wing, ils ne portent que sur un seul chiffre à la fois et ne demandent aucune hypothèse. Ils permettent d’effacer un candidat, parfois plusieurs, et cette petite élimination suffit souvent à relancer toute la grille.
Les deux exemples de cet article viennent d’une vraie grille de niveau expert de notre site, et chaque affirmation sur cette grille a été vérifiée par programme. Dans la suite, une case est repérée par sa ligne et sa colonne : L8C9 se lit « ligne 8, colonne 9 », en comptant depuis le coin en haut à gauche.
Deux mots de vocabulaire : lien fort et lien faible
Tout ce qui suit repose sur deux notions simples, qu’on retrouve dans toutes les techniques de chaînes.
- Il y a un lien fort entre deux cases pour un chiffre quand ce chiffre n’a plus que ces deux places dans une ligne, une colonne ou un bloc. L’une des deux cases porte forcément le chiffre : si l’une ne l’a pas, l’autre l’a.
- Il y a un lien faible entre deux cases quand elles se voient, c’est-à-dire partagent une ligne, une colonne ou un bloc. Elles ne peuvent pas porter toutes les deux le même chiffre : si l’une l’a, l’autre ne l’a pas.
Un lien fort se lit donc « si pas ici, alors là », un lien faible « si ici, alors pas là ». En enchaînant les deux, on fait circuler une information d’un bout à l’autre de la grille. Le gratte-ciel et le cerf-volant sont exactement la même chaîne, la plus courte qui soit utile : un lien fort, un lien faible, un lien fort, soit quatre cases. Ils ne diffèrent que par la nature des unités utilisées.
Du X-Wing au gratte-ciel
Rappelons le X-Wing, détaillé dans notre guide des techniques du sudoku. Un chiffre n’a que deux places dans une ligne, et que deux places dans une autre ligne, et ces quatre places tombent dans les deux mêmes colonnes. Le chiffre occupe alors forcément une diagonale du rectangle, donc ces deux colonnes sont « prises » : on l’efface de toutes leurs autres cases.
Imagine maintenant que les deux lignes partagent une colonne, mais pas l’autre. Le rectangle a un pied commun, appelé la base, et deux sommets qui ne sont pas alignés : de profil, on dirait deux immeubles de hauteurs différentes posés côte à côte, d’où le nom de gratte-ciel. Le raisonnement du X-Wing ne marche plus sur les colonnes, mais il en reste une partie :
- Les deux cases de la base sont dans la même colonne : au plus une des deux porte le chiffre.
- Si la base de la première ligne ne porte pas le chiffre, alors le sommet de cette ligne le porte (lien fort).
- Si c’est la base de la seconde ligne qui ne le porte pas, alors le sommet de la seconde ligne le porte.
- Comme au moins une des deux bases est vide de ce chiffre, au moins un des deux sommets le porte.
On ne sait pas lequel. Mais toute case qui voit les deux sommets à la fois ne peut pas porter le chiffre : quel que soit le sommet qui le reçoit, elle est dans son champ. C’est l’élimination du gratte-ciel. La même figure existe en version verticale, avec deux colonnes à deux candidats dont les bases partagent une ligne.
Un gratte-ciel sur une vraie grille
La grille de départ compte 28 chiffres donnés, en blanc sur la figure ; les chiffres en couleur sont ceux qu’on trouve ensuite. On y applique toutes les techniques classiques du guide, des singletons jusqu’aux triplets nus et cachés, en passant par les candidats verrouillés et les paires. Arrivé à 33 cases vides, plus rien ne bouge : c’est la première impasse. Pour la lisibilité, la figure n’affiche que les candidats du chiffre qui nous intéresse, le 8.
Regarde les lignes 1 et 9 :
- dans la ligne 1, le 8 ne peut aller qu’en L1C1 ou en L1C9 ;
- dans la ligne 9, il ne peut aller qu’en L9C1 ou en L9C7.
L1C1 et L9C1 sont toutes deux dans la colonne 1 : c’est la base. Les sommets, L1C9 et L9C7, ne sont pas dans la même colonne, ce n’est donc pas un X-Wing. Par le raisonnement ci-dessus, L1C9 ou L9C7 porte un 8, peut-être les deux.
Quelles cases voient ces deux sommets ? L1C9 commande la ligne 1, la colonne 9 et le bloc en haut à droite ; L9C7 commande la ligne 9, la colonne 7 et le bloc en bas à droite. Leurs champs se croisent en six cases : L1C7, L2C7, L3C7, L7C9, L8C9 et L9C9. Cinq sont déjà remplies. La sixième, L8C9, a encore le 8 parmi ses candidats : on peut l’effacer.
Une seule élimination, et pourtant la grille repart aussitôt. Dans la colonne 9, le 8 n’avait plus que deux places, L1C9 et L8C9. Il n’en reste qu’une : L1C9 = 8 par singleton caché. Le gratte-ciel a fait le travail difficile, un singleton termine.
Le cerf-volant : quand une ligne rencontre une colonne
Dans le gratte-ciel, les deux liens forts sont de même nature (deux lignes, ou deux colonnes) et le lien faible passe par la colonne commune. Le cerf-volant croise les genres : un lien fort dans une ligne, un autre dans une colonne, et le lien faible qui les réunit passe par un bloc.
Concrètement, on cherche un chiffre qui n’a que deux places dans une ligne et que deux places dans une colonne, avec une case de la ligne et une case de la colonne dans le même bloc (sans être la même case). Ces deux cases-là forment le nœud du cerf-volant. Les deux autres extrémités, qui partent en dehors du bloc, sont les « ficelles ». Le raisonnement est identique :
- Les deux cases du nœud se voient (même bloc) : au plus une porte le chiffre.
- Si la case du nœud côté ligne est vide de ce chiffre, l’autre extrémité de la ligne le porte ; même chose côté colonne.
- Donc au moins une des deux extrémités libres porte le chiffre.
La case à éliminer est très facile à trouver : c’est l’intersection de la ligne de l’extrémité colonne et de la colonne de l’extrémité ligne. Elle voit les deux bouts, l’un par sa ligne, l’autre par sa colonne.
Un cerf-volant sur la même grille
Restons à la même impasse et passons au 6 :
- dans la ligne 2, le 6 n’a que deux places, L2C1 et L2C8 ;
- dans la colonne 3, il n’a que deux places, L1C3 et L8C3.
L2C1 et L1C3 sont toutes deux dans le bloc en haut à gauche : voilà le nœud. Les extrémités libres sont L2C8, qui part vers la droite, et L8C3, qui descend. L’une des deux au moins porte le 6. La case à éliminer est à l’intersection de la ligne 8 et de la colonne 8 : L8C8, qui voit L8C3 par sa ligne et L2C8 par sa colonne. Elle a le 6 parmi ses candidats, on l’efface.
Là encore, la suite est immédiate. Dans la colonne 8, le 6 n’avait plus que L2C8 et L8C8. Il ne reste que L2C8 = 6, par singleton caché.
Deux noms, une seule idée
Une remarque qui aide à ne pas multiplier les recettes : sur cette grille, chaque élimination se trouve par les deux motifs. Le 8 de L8C9 tombe aussi par un cerf-volant formé de la ligne 1 (L1C1, L1C9) et de la colonne 2 (L2C2, L8C2), nouées dans le bloc en haut à gauche. Et le 6 de L8C8 tombe aussi par un gratte-ciel formé des lignes 2 et 7, avec sa base en colonne 1 (L2C1 et L7C1) et ses sommets en L2C8 et L7C7.
Ce n’est pas une coïncidence. Les deux techniques sont des cas particuliers d’une même chaîne de quatre cases sur un chiffre : fort, faible, fort. Le nom dépend seulement de l’endroit où passe le lien faible. Les joueurs qui pratiquent les chaînes parlent d’ailleurs souvent de chaîne X (une chaîne sur un seul chiffre), dont le gratte-ciel et le cerf-volant sont les formes les plus courtes.
| Motif | Liens forts | Ce qui relie les deux liens | Ce qu’on élimine |
|---|---|---|---|
| X-Wing | deux lignes (ou deux colonnes) | les deux colonnes communes | le chiffre dans le reste de ces deux colonnes |
| Gratte-ciel | deux lignes (ou deux colonnes) | une seule colonne commune, la base | le chiffre dans les cases qui voient les deux sommets |
| Cerf-volant | une ligne et une colonne | un bloc qui contient une case de chacune | le chiffre à l’intersection des deux extrémités libres |
Combien de fois on les rencontre
Pour savoir si ces motifs valent la peine d’être appris, nous avons passé au crible les 1 500 grilles expert de notre site. Chacune a été amenée à sa première impasse avec les techniques classiques, jusqu’aux triplets, puis on a cherché les motifs qui permettent au moins une élimination à ce moment précis :
- un cerf-volant utile est présent dans 741 grilles, soit environ 49 % ;
- un gratte-ciel utile dans 426 grilles, environ 28 % ;
- l’un ou l’autre dans 782 grilles, un peu plus d’une sur deux ;
- à titre de comparaison, un X-Wing utile n’est présent que dans 424 grilles.
Autrement dit, face à une grille expert bloquée, le cerf-volant se présente plus souvent que le X-Wing, et le gratte-ciel à peu près aussi souvent. Le solveur qui classe nos grilles ne connaît pas ces deux motifs : pour lui, une grille est expert parce qu’elle exige au moins un X-Wing, un XY-Wing ou un Swordfish. Sur la grille de cet article, par exemple, il n’y a pas de X-Wing à l’impasse, et le solveur passe par un XY-Wing. Le gratte-ciel et le cerf-volant sont donc une autre porte de sortie, souvent plus facile à voir quand on sait la chercher.
Comment les repérer en pratique
Le défaut de ces motifs, c’est qu’ils sont invisibles si on regarde toute la grille à la fois. La bonne méthode consiste à travailler un chiffre à la fois, exactement comme pour le X-Wing.
- Choisis un chiffre et isole ses candidats. En ligne, sélectionner le chiffre met ses notes en valeur ; sur papier, un surligneur aide.
- Liste les liens forts : les lignes, les colonnes et les blocs où ce chiffre n’a plus que deux places. C’est le travail principal, le reste en découle.
- Cherche deux lignes à deux candidats qui partagent une colonne (ou deux colonnes qui partagent une ligne) : si l’autre colonne est commune aussi, c’est un X-Wing ; sinon, c’est un gratte-ciel. Regarde alors les cases qui voient les deux sommets.
- Cherche une ligne et une colonne à deux candidats dont deux cases tombent dans le même bloc : c’est un cerf-volant. Vérifie la case à l’intersection des deux extrémités libres.
- Passe au chiffre suivant. Neuf chiffres, c’est vite parcouru une fois le réflexe acquis.
Une astuce de priorité : commence par les chiffres déjà bien placés dans la grille, ceux qui ont six ou sept exemplaires posés. Il leur reste peu de candidats, donc beaucoup de lignes et de colonnes à deux places, et les motifs y sont bien plus faciles à voir.
Les erreurs à éviter
- Un lien fort exige exactement deux candidats. Si une des lignes a trois places possibles pour le chiffre, le raisonnement s’effondre : la base peut être vide sans que le sommet soit rempli. Compte bien les notes, surtout si tu ne les as pas toutes mises à jour.
- On ne conclut rien sur les sommets eux-mêmes. Le motif dit qu’au moins un sommet porte le chiffre, pas lequel. Poser le chiffre dans un sommet « parce qu’il a l’air plus probable » est une supposition, et une erreur fréquente.
- La case éliminée doit voir les deux sommets. Voir un seul sommet ne suffit pas. Sur la figure 1, L8C9 voit L1C9 par la colonne 9 et L9C7 par le bloc en bas à droite ; c’est ce double regard qui autorise l’élimination.
- Ne pas confondre avec un X-Wing raté. Si les deux sommets sont dans la même colonne, c’est un X-Wing et les éliminations ne sont pas les mêmes : on élimine alors dans les deux colonnes entières.
- Au cerf-volant, le nœud compte deux cases distinctes. Si la case de la ligne et celle de la colonne sont la même case, il n’y a plus de lien faible, et plus de cerf-volant.
Et après ?
Une fois ces deux motifs maîtrisés, la suite logique est d’allonger la chaîne. Avec six cases ou plus sur le même chiffre, toujours en alternant liens forts et liens faibles, on obtient des chaînes X plus longues, et le coloriage, présenté dans notre article sur les grilles diaboliques, en est une façon visuelle de les suivre. Si tu veux d’abord consolider les bases qui mènent à l’impasse, l’article sur les paires nues revient en détail sur les groupes de candidats.
Le meilleur entraînement reste la pratique : lance une grille sur Sudoku en ligne, pousse-la jusqu’à ce que les techniques classiques ne donnent plus rien, puis passe les neuf chiffres en revue à la recherche d’un rectangle presque parfait. Sur nos grilles expert, un peu plus d’un de ces blocages sur deux cache un gratte-ciel ou un cerf-volant.