Sudoku Qu’est-ce que le Sudoku Anti-Cavalier ?
Le Sudoku Anti-Cavalier est un sudoku ordinaire avec une règle empruntée aux échecs. Remplissez la grille de sorte que :
- chaque ligne, colonne et bloc 3×3 contienne les chiffres de 1 à 9 une seule fois ;
- et deux cases séparées par un saut de cavalier ne contiennent jamais le même chiffre — deux cases dans une direction et une de côté, le L du cavalier aux échecs.
Rien dans la grille ne signale la règle. Elle s’applique partout, à chaque case, et une case a entre deux et huit cases à un saut de cavalier. Les voisines en diagonale ne sont pas des cases de cavalier : deux cases qui se touchent par un coin peuvent contenir le même chiffre dès qu’elles sont dans des blocs différents.
Un saut de cavalier ne reste jamais dans une ligne ou une colonne, mais il peut rester dans un bloc : depuis R1C1, il n’atteint que R2C3 et R3C2, et les deux sont déjà dans le bloc de R1C1. Chaque case, sauf les neuf centres de bloc, a exactement deux de ses cases de cavalier dans son propre bloc, où les règles ordinaires interdisent déjà une répétition. Des 224 paires de cavalier de la grille, 72 sont dans ce cas ; la règle en ajoute donc réellement 152.
Que dit la règle du cavalier avant qu’on place quoi que ce soit ?
Imaginez les cases de cavalier de chaque indice. Chacun retire son chiffre de jusqu’à huit cases de plus que dans un sudoku ordinaire, et combien dépend de la place de la case :
| Case | Où dans la grille | Cases de cavalier | Hors de son bloc | Voisines |
|---|---|---|---|---|
| R1C1 | Les quatre coins (4 cases) | 2 | 0 | 20 |
| R1C2 | Les cases de bord à côté d’un coin (8 cases) | 3 | 1 | 21 |
| R1C5 | Le reste du bord (20 cases) | 4 | 2 | 22 |
| R2C2 | Un pas en diagonale depuis un coin (4 cases) | 4 | 4 | 24 |
| R2C3 | Le deuxième anneau, hormis celles-là et ses quatre milieux (16 cases) | 6 | 4 | 24 |
| R2C5 | Le milieu de chaque côté du deuxième anneau (4 cases) | 6 | 6 | 26 |
| R3C3 | Le 5×5 intérieur, hormis son centre (24 cases) | 8 | 6 | 26 |
| R5C5 | Le centre | 8 | 8 | 28 |
Les « voisines » sont les cases qui ne peuvent pas répéter le chiffre d’une case : les 20 de sa ligne, de sa colonne et de son bloc, plus ses cases de cavalier hors du bloc. En moyenne sur les 81 cases, cela fait 23,75, environ un cinquième de plus que les 20 du sudoku ordinaire. La règle est la plus forte au milieu de la grille et ne fait rien dans les coins.
Sur une vraie grille, gardez donc les cases de cavalier dans vos notes au crayon dès le départ :
C’est un filet régulier, pas une vague. Sur 40 grilles par niveau, les cases de cavalier des indices rayent en médiane 17 notes au crayon en Facile et 29 en Expert avant qu’un chiffre soit placé, et fixent d’emblée quatre cases en Facile et deux en Moyen. Une case vide en Facile part de 2,7 candidats selon sa ligne, sa colonne et son bloc, et de 2,3 une fois les cases de cavalier comptées. Le vrai travail vient ensuite : chaque chiffre que vous placez se retire aussi de ses cases de cavalier, si bien que la règle rapporte jusqu’au bout de la résolution.
La règle du cavalier sert-elle vraiment à quelque chose ?
Chaque grille que distribue cette page est construite pour que la solution en dépende : le générateur retire des chiffres tant que la grille a une seule solution avec la règle du cavalier, puis vérifie les mêmes indices comme un sudoku ordinaire et continue de creuser jusqu’à ce qu’ils n’en aient plus une seule. Sur la grille ci-dessus :
Nous avons vérifié 160 grilles neuves, 40 par niveau : chacune a une seule solution avec la règle du cavalier et plusieurs sans elle. En sudoku ordinaire, les indices d’une grille Facile ont en médiane trois solutions et jusqu’à 27, ceux de Moyen une médiane de 20, et ceux de Difficile et Expert plus de 200 sur chaque grille essayée. Un solveur qui ignore la règle du cavalier se bloque sur chaque grille, à chaque niveau.
Le générateur de cette page avait déjà juste avant cette refonte — sa vérification d’unicité était complète, et 160 grilles sur 160 ont passé le même test. Ce qui n’allait pas, c’était la vitesse : il remplissait la grille case par case sans anticipation, et le pire des 1 000 remplissages mesurés a demandé plus de 100 000 étapes. Une grille prenait en médiane de 25 à 57 millisecondes et jusqu’à 310 sur un ordinateur, tout cela pendant le chargement de la page ; sur un téléphone, c’est un gel visible. La refonte produit le même genre de grille en 2 à 4 millisecondes environ, 9 au pire.
En quoi les quatre niveaux diffèrent-ils ?
Nous avons passé 40 grilles neuves par niveau dans un solveur qui connaît une technique à la fois, puis retiré des techniques pour voir quelles grilles s’arrêtaient. La règle du cavalier n’est pas une technique ici : comme une ligne ou un bloc, elle retire simplement un chiffre placé des cases qu’elle atteint.
| Niveau | Indices | Notes rayées d’emblée par la règle du cavalier | Cases fixées | Les singles suffisent | Demande des Locked Candidates | Demande un sous-ensemble | Au-delà de notre solveur |
|---|---|---|---|---|---|---|---|
| Facile | 34–38 | 17 | 4 | 100 % | 0 % | 0 % | 0 % |
| Moyen | 29–30 | 21 | 2 | 98 % | 3 % | 0 % | 0 % |
| Difficile | 25 | 26 | 0 | 83 % | 15 % | 0 % | 3 % |
| Expert | 21 | 29 | 0 | 28 % | 53 % | 3 % | 18 % |
40 grilles par niveau issues du générateur de cette page, graine fixe ; médianes, et parts arrondies, si bien qu’une ligne peut dépasser un peu 100. Notre étape Locked Candidates inclut la version cavalier : quand toutes les places restantes d’un chiffre dans une maison voient une même case, par ligne, colonne, bloc ou saut de cavalier, cette case perd le chiffre. Le solveur connaît aussi les paires nues et les triplets, et le X-Wing ; les grilles « au-delà de notre solveur » ont tout de même exactement une solution. Facile et Moyen descendent de quelques indices sous la cible quand c’est ce qu’il faut pour que la règle du cavalier porte la grille.
Les niveaux sont de vraies marches, et Expert en est une grande. Les singles nus et les singles cachés, cases de cavalier nettoyées, terminent toutes les grilles Facile et 39 sur 40 en Moyen. C’est en Difficile qu’arrivent les Locked Candidates, sur environ une grille sur sept. En Expert, les singles seuls terminent à peine plus d’une grille sur quatre : la moitié demande des Locked Candidates, et environ une sur six dépasse tout ce que connaît notre solveur. Cette page promettait autrefois que Difficile demandait des paires et des Pointing Pairs ; mesuré, Difficile tombe aux singles plus de quatre fois sur cinq.
Le générateur remplit une grille qui respecte déjà la règle du cavalier, puis retire les chiffres un à un, ne gardant un retrait que tant que la grille a exactement une solution ; une recherche qu’il ne peut pas terminer répond « non prouvé » et le chiffre reste. Nous avons re-résolu 160 grilles neuves avec un compteur écrit exprès : chacune avait exactement une solution, et chaque solution tenait toutes les paires de cavalier à distance. La vérification d’unicité la plus profonde a pris 84 étapes de recherche sur les 4 000 permises.
Quel niveau choisir ?
Commencez en Facile, même si le sudoku ordinaire vous est facile. La règle du cavalier est invisible, et les premières grilles servent à prendre l’habitude de vérifier les L ; en Facile, chaque grille tombe aux singles dès que vous le faites. Moyen, c’est la même compétence avec moins d’indices : moins de choses arrivent gratuitement au départ, et davantage vient des cases de cavalier des chiffres que vous placez.
Difficile ajoute des Locked Candidates sur environ une grille sur sept, y compris la version cavalier, où un chiffre coincé dans deux ou trois cases d’un bloc s’exclut de toute case que toutes atteignent. Expert est une vraie marche : moins d’un tiers de ses grilles tombent aux singles. Chacune a quand même exactement une solution, et aucune n’exige de deviner.
Ce qui se passe mal dans un Sudoku Anti-Cavalier
- Oublier la règle. Rien dans la grille ne vous la rappelle. Une grille qui bloque à mi-chemin est presque toujours une grille où un chiffre a été placé sans nettoyer ses cases de cavalier.
- Compter sur les coins. Les deux cases de cavalier d’un coin sont dans son propre bloc ; la règle n’y apprend rien de neuf. Regardez le milieu de la grille, où une case en atteint huit.
- Confondre avec le roi. Deux cases qui se touchent en diagonale ne sont pas à un saut de cavalier. Dans des blocs différents, elles peuvent contenir le même chiffre.
- Ne vérifier que dans un sens. Le cavalier saute dans les deux sens : un 5 en R3C4 exclut le 5 de R5C5, et un 5 en R5C5 l’exclurait de R3C4. Chaque paire vaut des deux côtés, alors nettoyez tout le L à chaque fois.
- Croire que la règle remplace les règles ordinaires. Elle ajoute des voisines, elle n’en retire aucune. Lignes, colonnes et blocs font encore l’essentiel du travail sur chaque grille.
D’où vient le Sudoku Anti-Cavalier ?
Michal Stajszczak l’a présenté sur mathpuzzle.com, le site de casse-têtes d’Ed Pegg, le 20 août 2006, comme « a new (I hope) variant of sudoku » : un sudoku ordinaire où les mêmes chiffres ne sont jamais « knight move connected ». Les auteurs de compétition l’ont repris sous des noms comme « No Knight Step Sudoku », et il est devenu célèbre en mai 2020 grâce au « Miracle Sudoku » de Mitchell Lee, qui combinait la règle anti-cavalier avec une règle anti-roi et une interdiction des voisins consécutifs, et partait de deux chiffres donnés seulement. Alex Bellos l’a publié comme Monday Puzzle dans le Guardian le 18 mai 2020, et la résolution de la chaîne YouTube Cracking the Cryptic est devenue virale.
À quoi servent les boutons ?
Choisissez une case, puis un chiffre de 1 à 9 ; la page s’ouvre en Moyen. Une case choisie met en évidence sa ligne, sa colonne et son bloc ainsi que les cases à un saut de cavalier, et un chiffre qui se répète dans l’une d’elles est signalé comme conflit. Sous la grille :
- Notes active et désactive les notes au crayon. Un bon chiffre s’efface des notes de sa ligne, de sa colonne, de son bloc et de ses cases de cavalier ; un mauvais laisse vos notes tranquilles.
- Effacer vide la case choisie ; appuyer deux fois sur le même chiffre fait de même.
- Annuler reprend la dernière modification d’une case, mais pas les notes qu’un bon chiffre a effacées ailleurs, ni le compteur d’erreurs.
- Indice remplit une case avec sa réponse, choisie au hasard et non la case que vous pourriez déduire ensuite.
- Résoudre demande d’abord confirmation, puis remplit la grille et arrête le chrono.
- Nouvelle partie distribue une autre grille au niveau où vous êtes ; les boutons de niveau en distribuent une au leur.
Les chiffres 1–9, les flèches, Retour arrière ou Suppr et Ctrl+Z fonctionnent au clavier. La grille est enregistrée dans ce navigateur après chaque coup et vous attend à votre retour.
Pour aller plus loin
Le Sudoku Anti-Cavalier est la variante qui ajoute une règle invisible au lieu d’en dessiner une. Le X Sudoku ajoute les deux grandes diagonales comme maisons supplémentaires, et l’Hyper Sudoku quatre blocs grisés ; tous deux gardent la nouvelle contrainte bien visible. Le Sudoku Kropki est l’autre variante du site fondée sur les cases voisines, avec des points qui disent comment deux chiffres qui se touchent sont liés, et le Killer Sudoku est celui qu’il vous faut si vous préférez l’arithmétique à la géométrie.