Sudoku tueur - Killer sudoku

A ne pas confondre avec le sudoku de niveau "tueur" (c'est-à-dire très difficile) .
Exemple de problème de Killer Sudoku.
Solution à l'exemple ci-dessus.
Le même problème d'exemple, car il serait imprimé en noir et blanc.

Killer sudoku (également killer su doku , sumdoku , sum doku , sumoku , addoku ou samunamupure ) est un puzzle qui combine des éléments de sudoku et de kakuro . Malgré son nom, le sudokus tueur plus simple peut être plus facile à résoudre que les sudokus ordinaires, selon les compétences du solveur en calcul mental ; les plus difficiles, cependant, peuvent mettre des heures à se fissurer.

Un problème typique est illustré à droite, en utilisant des couleurs pour définir les groupes de cellules. Le plus souvent, les puzzles sont imprimés en noir et blanc, avec de fines lignes pointillées servant à délimiter les «cages» (voir ci-dessous la terminologie).

Histoire

Les puzzles de sudoku tueur étaient déjà une variante établie du sudoku au Japon au milieu des années 1990, où ils étaient connus sous le nom de «samunamupure». Le nom provient d'une forme japonaise des mots anglais «sum number place». Killer sudokus a été présenté à la plupart des anglophones par le Times en 2005.

Traditionnellement, comme pour les puzzles de sudoku ordinaires, la disposition de la grille est symétrique autour d'un axe diagonal, horizontal ou vertical, ou d'un quart ou d'un demi-tour autour du centre. C'est une question d'esthétique, cependant, plutôt que obligatoire: de nombreux fabricants de puzzle japonais feront de petits écarts par rapport à la symétrie parfaite dans le but d'améliorer le puzzle. D'autres créateurs de puzzles peuvent produire des puzzles entièrement asymétriques.

Terminologie

Cellule
Un seul carré qui contient un nombre dans la grille
Rangée
Une ligne horizontale de 9 cellules
Colonne
Une ligne verticale de 9 cellules
Aucun filet
Une grille 3 × 3 de cellules, comme indiqué par les lignes plus audacieuses dans le diagramme ci-dessus; aussi appelé une boîte
Cage
Le groupement de cellules indiqué par une ligne pointillée ou par des couleurs individuelles.
loger
Tout ensemble non répétitif de 9 cellules: peut être utilisé comme terme général pour "ligne, colonne ou nonet" (ou, dans les variantes Killer X, "longue diagonale")

Des règles

L'objectif est de remplir la grille avec des nombres de 1 à 9 de manière à ce que les conditions suivantes soient remplies:

  • Chaque ligne, colonne et nonet contient chaque nombre exactement une fois.
  • La somme de tous les nombres d'une cage doit correspondre au petit nombre imprimé dans son coin.
  • Aucun numéro n'apparaît plus d'une fois dans une cage. (Ceci est la règle standard pour les sudokus tueurs, et implique qu'aucune cage ne peut inclure plus de 9 cellules.)

Dans «Killer X», une règle supplémentaire est que chacune des longues diagonales contient chaque numéro une fois.

Ambiguïté de cellule en double

Par convention au Japon, les cages de sudoku tueur n'incluent pas de numéros en double. Cependant, lorsque le Times a introduit pour la première fois le sudoku tueur le 31 août 2005, le journal n'a pas rendu cette règle explicite. Même si la grande majorité des puzzles de sudoku tueurs suivaient de toute façon la règle, les solveurs anglophones étaient confus quant aux stratégies de résolution appropriées étant donné l'ambiguïté. Le 16 septembre 2005, The Times a ajouté une nouvelle décision selon laquelle «dans chaque forme de ligne pointillée, un chiffre PEUT être répété si les règles normales de ligne, colonne et boîte 3x3 ne sont pas enfreintes». Mais le 19 septembre, la règle est devenue «Dans chaque forme de ligne pointillée, un chiffre NE PEUT PAS être répété si les règles normales de ligne, colonne et boîte 3x3 ne sont pas enfreintes» - ce qui crée encore plus de confusion. Cette règle révisée est restée bloquée et la norme mondiale n'est pas de doublons dans les cages.

Stratégies de résolution

Moins de combinaisons possibles

En général, le problème est mieux abordé en partant des sommes extrêmes - des cages avec les sommes les plus importantes ou les plus petites. En effet, ceux-ci ont le moins de combinaisons possibles. Par exemple, 5 cellules dans la même cage totalisant 34 ne peuvent être que 4, 6, 7, 8 et 9. Pourtant, 5 cellules dans la même cage totalisant 25 ont douze combinaisons possibles.

Dans les premiers stades du jeu, la façon la plus courante de commencer à remplir des nombres est de regarder ces cages à somme faible ou élevée qui forment une «ligne droite». Comme le solveur peut en déduire que certains nombres se trouvent dans une certaine ligne ou colonne, ils peuvent commencer à «hachurer» en face d'eux.

La règle de 45

Une autre technique peut être dérivée de la connaissance que les nombres dans toutes les maisons (lignes, colonnes et nonets) totalisent 45. En additionnant les cages et les nombres uniques dans une maison particulière, l'utilisateur peut déduire le résultat d'une seule cellule . Si la cellule calculée se trouve dans la maison elle-même, elle est appelée «innie»; à l'inverse, si la cellule est à l'extérieur, on l'appelle un «outie». Même si cela n'est pas possible, les joueurs avancés peuvent trouver utile de calculer la somme de deux ou trois cellules, puis d'utiliser d'autres techniques d'élimination (voir ci-dessous pour un exemple de cela). Cette technique '45' peut également être étendue pour calculer les innies ou outies de N maisons adjacentes, comme la différence entre les sommes de cage et N * 45.

Arithmétique d'horloge

Un raccourci pour calculer ou vérifier la valeur d'un seul 'innie' ou 'outie' sur un grand nombre de cages consiste à additionner les cages en utilisant l'arithmétique 'clock' (correctement, Modular Arithmetic modulo 10), dans laquelle tous les chiffres autres que le dernier d'un nombre quelconque sont ignorés.

Lorsque deux nombres sont additionnés, le dernier chiffre du total n'est affecté par rien d'autre que les derniers chiffres des deux nombres originaux. L'addition d'un nombre se terminant par 7 et d'un nombre se terminant par 8 aboutit toujours à un nombre se terminant par 5, par exemple. Ainsi, par exemple, 1 7 + 1 8 = 3 5 devient, en arithmétique d'horloge, 7 + 8 = 5. Le plus grand nombre qu'un 'innie' ou 'outie' peut contenir est 9, donc ajouter ou soustraire cette valeur changera le dernier chiffre du total d'une manière qu'aucune autre valeur ne le ferait - ce qui permet de calculer directement «innie» ou «outie». L'arithmétique des horloges a l'avantage que vous ne traitez que des sommes à un chiffre, plutôt que des sommes comme, par exemple, 58 + 27 - et même si le concept n'est pas familier au départ, il devient rapidement trivial.

Exemple: Un ensemble de cages forme un nonet complet avec un «outie». Les cages ont des valeurs 8, 1 0 , 1 4 , 7, 1 4 .

  • En utilisant l'arithmétique normale, ceux-ci totalisent 53. Un seul nonet totalise 45, donc le 'outie' doit contenir un 8.
  • Vérifier que, en utilisant l'arithmétique d'horloge sur ces valeurs à tour de rôle: 8 + 0 = 8; 8 + 4 = 2; 2 + 7 = 9; 9 + 4 = 3. Le total de l'horloge est donc de 3, ce qui signifie que le total réel se termine également par 3 (ce que nous avons vu que c'est le cas). Tout nombre impair de maisons (dans ce cas, 1 nonet) a toujours un total arithmétique se terminant par 5 - donc, le seul `` outie '' que nous pourrions ajouter pour changer ce 5 en 3 est, encore une fois, 8.

L'arithmétique de l'horloge a l'avantage supplémentaire que, lorsque les chiffres finaux de deux totaux de cage totalisent 10 (1 3 et 2 7 , par exemple), la paire ne fera aucune différence sur le total de l'horloge et peut simplement être ignorée.

L'arithmétique des horloges doit tout au plus être utilisée avec précaution pour les maisons avec plus d'un «innie» ou «outie», lorsque plusieurs ensembles de valeurs peuvent aboutir au même nombre final, mais peuvent toujours être utiles comme vérification arithmétique rapide.

Numéros cohérents dans les combinaisons

Même si certaines cages peuvent avoir plusieurs combinaisons de nombres disponibles, il peut souvent y avoir un ou plusieurs nombres cohérents dans toutes les solutions disponibles. Par exemple: une cage à 4 cellules totalisant 13 a les combinaisons possibles de (1, 2, 3, 7), (1, 2, 4, 6) ou (1, 3, 4, 5). Même si, au départ, il n'y a aucun moyen de dire quelle combinaison de nombres est correcte, chaque solution disponible contient un 1. Le joueur sait alors avec certitude que l'un des nombres dans cette cage est 1 (quelle que soit la solution finale). Cela peut être utile si, par exemple, ils ont déjà déduit une autre cellule dans un nonet dans lequel la cage réside comme ayant le numéro 1 comme solution. Ils savent alors que le 1 ne peut résider que dans des cellules qui sont en dehors de ce nonet. S'il n'y a qu'une seule cellule disponible, c'est un 1.

Analyse initiale du problème de l'échantillon

Le problème de l'échantillon.

Moins de combinaisons possibles

Les deux cellules en haut à gauche doivent être 1 + 2. Les 3 cellules à droite totalisant 15 ne peuvent donc pas avoir un 1 ou un 2, elles doivent donc être soit 3 + 4 + 8, 3 + 5 + 7, soit 4 + 5 + 6.

Les deux cellules verticales en haut à gauche du nonet en haut à droite ne peuvent pas être 2 + 2 car cela signifierait des doublons, elles doivent donc être 1 + 3. Le 1 ne peut pas être sur la ligne supérieure car cela entre en conflit avec nos 2 premières cellules, donc la cellule supérieure de cette paire est 3 et la cellule inférieure 1. Cela signifie également que la cage à 3 cellules 15 à gauche ne peut pas contenir un 3 et donc 4 + 5 + 6.

De même, le 16 voisin doit être 9 + 7.

Les quatre cellules de la cage en haut à droite (au total 15) ne peuvent inclure qu'une des 1, 3, 7 ou 9 (le cas échéant) en raison de la présence de 1, 3, 7 et 9 dans le nonet supérieur droit. Si l'un des 1, 3, 7 ou 9 est présent, il doit s'agir du seul carré du nonet ci-dessous. Par conséquent, ces 4 cellules sont l'une de 1 + 2 + 4 + 8 ou 2 + 3 + 4 + 6; les 2 cellules au milieu du bord gauche doivent être 1 + 5 ou 2 + 4; etc.

45 exemple de règle

En regardant le nonet sur le côté gauche au milieu, nous pouvons voir qu'il y a trois cages qui ne se croisent pas dans un autre nonet; ceux-ci totalisent 33, ce qui signifie que la somme des deux cellules restantes doit être de 12. Cela ne semble pas particulièrement utile, mais considérez que la cellule en bas à droite du nonet fait partie d'une 3-cage de 6; elle ne peut donc contenir que 1, 2 ou 3. Si elle contenait 1 ou 2, l'autre cellule devrait contenir respectivement 11 ou 10; c'est impossible. Il doit donc contenir 3 et l'autre cellule 9.

Compléments

Avec 6 cellules, cages 7 cellules ou 8 cellules, la corrélation des combinaisons avec leurs 3 cellules, 2 cellules, ou 1 cellules complémentaires simplifie habituellement les choses. Le tableau pour 6 cages cellulaires est le complément du tableau 3 cellules totalisant jusqu'à 45 moins la valeur indiquée; de même, le tableau à 7 cellules complète le tableau à 2 cellules . Une cage à 8 cellules ne manque bien sûr qu'un seul chiffre (45 moins la somme de la cage).

Par exemple, le complément d'une cage à 7 cellules totalisant 41 est une cage à 2 cellules totalisant 4 (car 9–7 = 2 et 45–41 = 4). Comme une cage à 2 cellules totalisant 4 ne peut contenir que 1 et 3, on en déduit qu'une cage à 7 cellules totalisant 41 ne contient ni 1 ni 3.

Tables totales de cage

Les tableaux suivants répertorient les combinaisons possibles pour différentes sommes.

1 cellule 
 1: 1
 2: 2
 3: 3
 4: 4
 5: 5
 6: 6
 7: 7
 8: 8
 9: 9
2 cellules 
 3: 12
 4: 13
 5: 14 23
 6: 15 24
 7: 16 25 34
 8: 17 26 35
 9: 18 27 36 45
10: 19 28 37 46
11: 29 38 47 56
12: 39 48 57
13: 49 58 67
14: 59 68 
15: 69 78
16: 79
17: 89
3 cellules 
 6: 123
 7: 124
 8: 125 134
 9: 126 135 234
10: 127 136 145 235
11: 128 137 146 236 245
12: 129 138 147 156 237 246 345
13: 139 148 157 238 247 256 346
14: 149 158 167 239 248 257 347 356
15: 159 168 249 258 267 348 357 456
16: 169 178 259 268 349 358 367 457
17: 179 269 278 359 368 458 467
18: 189 279 369 378 459 468 567
19: 289 379 469 478 568
20: 389 479 569 578
21: 489 579 678
22: 589 679
23: 689
24: 789
4 cellules 
10: 1234
11: 1235
12: 1236 1245
13: 1237 1246 1345
14: 1238 1247 1256 1346 2345
15: 1239 1248 1257 1347 1356 2346
16: 1249 1258 1267 1348 1357 1456 2347 2356
17: 1259 1268 1349 1358 1367 1457 2348 2357 2456
18: 1269 1278 1359 1368 1458 1467 2349 2358 2367 2457 3456
19: 1279 1369 1378 1459 1468 1567 2359 2368 2458 2467 3457
20: 1289 1379 1469 1478 1568 2369 2378 2459 2468 2567 3458 3467
21: 1389 1479 1569 1578 2379 2469 2478 2568 3459 3468 3567
22: 1489 1579 1678 2389 2479 2569 2578 3469 3478 3568 4567
23: 1589 1679 2489 2579 2678 3479 3569 3578 4568
24: 1689 2589 2679 3489 3579 3678 4569 4578
25: 1789 2689 3589 3679 4579 4678
26: 2789 3689 4589 4679 5678
27: 3789 4689 5679
28: 4789 5689
29: 5789
30: 6789
5 cellules 
15: 12345
16: 12346
17: 12347 12356
18: 12348 12357 12456
19: 12349 12358 12367 12457 13456
20: 12359 12368 12458 12467 13457 23456
21: 12369 12378 12459 12468 12567 13458 13467 23457
22: 12379 12469 12478 12568 13459 13468 13567 23458 23467
23: 12389 12479 12569 12578 13469 13478 13568 14567 23459 23468 23567
24: 12489 12579 12678 13479 13569 13578 14568 23469 23478 23568 24567
25: 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567
26: 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568
27: 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569 34578
28: 13789 14689 15679 23689 24589 24679 25678 34579 34678
29: 14789 15689 23789 24689 25679 34589 34679 35678
30: 15789 24789 25689 34689 35679 45678
31: 16789 25789 34789 35689 45679
32: 26789 35789 45689
33: 36789 45789
34: 46789
35: 56789
6 cellules 
21: 123456
22: 123457
23: 123458 123467
24: 123459 123468 123567
25: 123469 123478 123568 124567
26: 123479 123569 123578 124568 134567
27: 123489 123579 123678 124569 124578 134568 234567
28: 123589 123679 124579 124678 134569 134578 234568
29: 123689 124589 124679 125678 134579 134678 234569 234578
30: 123789 124689 125679 134589 134679 135678 234579 234678
31: 124789 125689 134689 135679 145678 234589 234679 235678
32: 125789 134789 135689 145679 234689 235679 245678
33: 126789 135789 145689 234789 235689 245679 345678
34: 136789 145789 235789 245689 345679
35: 146789 236789 245789 345689
36: 156789 246789 345789
37: 256789 346789
38: 356789
39: 456789
7 cellules 
28: 1234567
29: 1234568
30: 1234569 1234578
31: 1234579 1234678
32: 1234589 1234679 1235678
33: 1234689 1235679 1245678
34: 1234789 1235689 1245679 1345678
35: 1235789 1245689 1345679 2345678
36: 1236789 1245789 1345689 2345679
37: 1246789 1345789 2345689
38: 1256789 1346789 2345789
39: 1356789 2346789
40: 1456789 2356789
41: 2456789
42: 3456789
8 cellules 
36: 12345678
37: 12345679
38: 12345689
39: 12345789
40: 12346789
41: 12356789
42: 12456789
43: 13456789
44: 23456789
9 cellules 
45: 123456789

Voir également

Liens externes