Sudoku Qu’est-ce que le Sudoku Battenburg ?
Le Sudoku Battenburg est un sudoku ordinaire avec de petits marqueurs sur certains des coins où quatre cases se rejoignent. Remplissez la grille de sorte que :
- chaque ligne, colonne et bloc 3×3 contienne 1 à 9 une seule fois ;
- et que, là où se trouve un marqueur, les quatre cases autour forment un damier pair/impair — les deux d’une diagonale impaires et les deux de l’autre paires —, alors que là où il n’y a aucun marqueur, elles n’en forment pas.
Le marqueur est dessiné comme un minuscule damier rose et jaune, comme une tranche de gâteau Battenberg. Il ne dit pas quelle diagonale est impaire ; dans un sens comme dans l’autre, cela compte. Chaque grille les montre tous : si quatre cases forment un damier dans la solution, leur coin est marqué.
Une grille 9×9 a 64 coins où quatre cases se rejoignent. Sur cette page, une grille en marque en médiane 10 à 13, si bien qu’une cinquantaine de coins ne portent aucun marqueur — et chacun d’eux dit que les quatre cases autour ne forment pas un damier. Ces coins vides sont l’essentiel de l’information de la grille, et c’est la moitié de la règle que l’on oublie.
Que dit un marqueur avant qu’on place quoi que ce soit ?
Pensez parité avant de penser chiffres. Autour d’un marqueur, une seule parité connue fixe les quatre cases, parce qu’un damier ne peut tomber que de deux façons. Reportez-le tout de suite dans vos notes au crayon :
Un coin vide fonctionne à l’inverse et demande plus d’éléments : dès que trois de ses quatre cases sont connues, la quatrième doit casser le damier si les trois en formeraient un autrement.
Lisez chaque coin ainsi, puis comptez. Chaque ligne, colonne et bloc contient cinq chiffres impairs et quatre pairs ; dès que cinq cases d’une maison sont connues impaires, les autres sont paires, et dès que quatre sont connues paires, les autres sont impaires. Sur 40 grilles par niveau, lire les marqueurs et compter les parités raye en médiane 42 notes au crayon en Facile et 77 en Expert avant qu’un chiffre soit placé, fixe la parité d’environ 30 à 40 cases que les lignes, les colonnes et les blocs laissaient ouvertes, et règle entièrement 11 cases en Facile, 4 en Expert.
Les marqueurs servent-ils vraiment à quelque chose ?
Chaque grille de 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 les marqueurs, 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 ses marqueurs et plusieurs sans eux. Comme sudoku ordinaire, les indices du niveau Facile ont en médiane 3 solutions et jusqu’à 31, ceux du Moyen une médiane de 12, et ceux du Difficile et de l’Expert plus de 200 sur chaque grille essayée. Un solveur qui ignore les marqueurs cale sur chaque grille, à chaque niveau.
Le générateur de cette page faisait déjà juste avant cette réécriture ; sa vérification était complète, et 160 anciennes grilles sur 160 passaient le même test. Ce qui n’allait pas, c’était la vitesse. Il ne testait un marqueur qu’une fois ses quatre cases remplies, si bien que sa recherche errait : une grille Expert prenait 73 millisecondes en médiane et jusqu’à un tiers de seconde sur un ordinateur de bureau, et plus d’une seconde dans une série plus courte, le tout pendant le chargement de la page. La réécriture lit les marqueurs au fur et à mesure et distribue chaque niveau en environ 2 millisecondes, 10 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. Lire les marqueurs et compter les parités est le coup propre à cette variante, et le solveur le fait gratuitement avant chaque étape.
| Niveau | Indices | Marqueurs | Notes rayées au premier regard | Cases réglées | Les singles suffisent | Au-delà de notre solveur |
|---|---|---|---|---|---|---|
| Facile | 34–38 | 13 | 42 | 11 | 98 % | 3 % |
| Moyen | 30 | 11 | 60 | 10 | 93 % | 8 % |
| Difficile | 25 | 12 | 73 | 8 | 85 % | 15 % |
| Expert | 21 | 10 | 77 | 4 | 50 % | 48 % |
40 grilles par niveau issues du générateur de cette page, graine fixe ; médianes, et parts arrondies. Le nombre de marqueurs varie beaucoup d’une grille à l’autre, de 3 à 21 des 64 coins. Le solveur connaît les singles nus et cachés, les Locked Candidates, les paires nues et triplets, et le X-Wing ; une grille Expert a eu besoin des Locked Candidates, et c’est pourquoi cette ligne n’atteint pas 100. Les grilles « au-delà de notre solveur » ont tout de même exactement une solution. Facile descend de quelques indices sous 38 quand c’est ce qu’il faut pour que les marqueurs portent la grille.
C’est une variante où les niveaux montent vraiment. Les singles nus et les singles cachés, une fois les marqueurs lus, terminent 39 grilles Facile sur 40, 37 en Moyen et 34 en Difficile. L’Expert est une vraie marche : la moitié de ses grilles tombe avec les singles, et l’autre moitié va au-delà de tout ce que connaît notre solveur, même avec chaque marqueur lu et chaque maison comptée. Toutes ont une seule solution, et aucune ne demande de deviner, mais une grille Expert est ici un vrai casse-tête.
Le générateur remplit une grille, en déduit chaque marqueur et retire les chiffres un à un, ne gardant un retrait que tant que la grille a exactement une solution sous la règle des marqueurs, coins vides compris ; 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. La vérification d’unicité la plus profonde a pris 33 étapes de recherche sur les 4 000 permises.
Quel niveau choisir ?
Commencez en Facile, même si le sudoku ordinaire vous est facile. La première chose à apprendre, ce sont les coins vides, et le Facile donne assez de chiffres pour voir trois cases d’un coin à la fois. Moyen et Difficile demandent la même compétence avec moins d’indices ; presque chaque grille tombe encore avec les singles dès qu’on lit les marqueurs.
L’Expert est la marche : la moitié de ses grilles va au-delà des singles. Si une grille Expert bloque, arrêtez de regarder les chiffres : faites le tour des coins et notez chaque case dont vous pouvez prouver la parité, puis comptez les cases impaires et paires, maison par maison.
Ce qui se passe mal dans un Sudoku Battenburg
- Ignorer les coins vides. Une cinquantaine des 64 coins n’ont pas de marqueur, et chacun d’eux interdit un damier. L’essentiel de l’information de la grille est là.
- Croire qu’un marqueur dit quelle diagonale est impaire. Ce n’est pas le cas. Il dit que les deux diagonales diffèrent ; une case connue décide dans quel sens.
- Lire un marqueur sur les mauvaises quatre cases. Un marqueur appartient aux quatre cases qui partagent son coin, deux au-dessus et deux en dessous. Il ne dit rien des cases voisines de celles-ci.
- Mal compter les parités. Cinq impaires et quatre paires par maison, jamais l’inverse : il y a cinq chiffres impairs, 1, 3, 5, 7 et 9, et quatre pairs.
- Attendre les chiffres. L’essentiel de ce casse-tête se résout d’abord en parités. Une case connue impaire n’a que cinq candidats, et une maison dont les parités sont réglées se sépare en deux petits casse-têtes.
D’où vient le Sudoku Battenburg ?
C’est Bram de Laat qui l’a inventé. Il a publié le premier sur son blog, Para’s Puzzle Site, le 9 février 2013, comme sa contribution à la Daily Sudoku League de la semaine, en le présentant comme un type de sudoku de son invention. Le nom, écrivait-il, vient des marquages Battenburg — le motif à damier des voitures de police britanniques —, même si c’est surtout au gâteau Battenberg, un damier lui aussi, qu’il le rattachait. Sa règle est celle qu’utilise cette page : partout où deux chiffres impairs et deux pairs forment un damier, un marqueur est donné.
À 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, et un mauvais chiffre est signalé dès qu’il est placé, y compris un chiffre qui enfreint un marqueur. 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 et de son bloc ; 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 Battenburg donne la parité un coin à la fois. Le Sudoku Pair-Impair la donne d’un coup, chaque case ombrée paire ou impaire, et c’est l’entrée la plus douce dans le raisonnement par parité. Le Sudoku Kropki marque aussi les lignes entre les cases, avec des points qui disent que deux voisines diffèrent de un ou que l’une est le double de l’autre, et le Killer Sudoku remplace la parité par des sommes.