Wednesday, July 30, 2014

Grille de la semaine #94 [League of Extraordinary Ladies and Gentlemen #68]

Dernière grille de cette série consacrée à la résolution détaillée de jeux créés pour les épreuves de sélection de l'équipe de France 2014, un Little Killer Sudoku 6 parmi 9 de mon coéquipier et co-auteur Sylvain Caudmont. Ce n'était certes pas la grille la plus difficile de la série, mais elle comportait suffisamment d'étapes dignes d'intérêt pour mériter une étude approfondie.
Pour rappel, les grilles de la League sont jouables en ligne à l'adresse http://sudokucup.com/node/3172 avec un délai de 24h.

Final puzzle of this series, a  Little Killer Sudoku 6 parmi 9 made by my co-author and teammate Sylvain Caudmont. Not one the hardest puzzles of the round, but with enough interesting things to spot to deserve a detailed study.
Remember that you can solve the puzzles from the League online on http://sudokucup.com/node/3172 with a 24h delay.

Règles :
La grille comporte 6 chiffres différents à déterminer entre 1 et 9.
Chaque ligne, colonne et région doivent contenir les chiffres en question.
Les indices extérieurs correspondent à la somme des chiffres se situant dans la diagonale désignée par la flèche.
°°°°°°°°°°°°°°°°°°°°
Use a set of 6 different digits amongst 1, 2, 3, 4, 5, 6, 7, 8 and 9.
Each row, column and region must contain the digits of the set.
Clues outside the grid represent the sum of digits in the indicated direction.

#107 Little Killer Sudoku 6 Parmi 9 [Sylvain Caudmont]

 




Cheminement :


Étape 1 :

L'entame d'un Little Killer Sudoku passe souvent par la confrontation des minimums et des maximums. Ici, commençons par observer que la somme 14 en deux chiffres ne pourra être formée qu'à l'aide du couple 59 ou du couple 68. L5C6 contiendra donc au minimum un 6, et L6C5 un 5.



Étape 2 :

Combinons ces informations au second indice 14 pour déterminer que, la somme de L2C1, L3C2, L4C3 et L5C4 valant au minimum 1+1+6+1=9, L6C5 ne peut pas valoir plus de 5. L6C5 valant au moins 5, et au plus 5, L6C5=5 et les trois cases restantes tombent à la suite.



Étape 3 :

Terminons-en avec les 1 : en région 4, le 1 ne peut se trouver en L4C6 car il deviendrait impossible de satisfaire l'indice 20 en 3 cases => L4C5=1 et L1C6=1.



Étape 4 :

Suite au placement des 1, on a L2C6=5.



Étape 5 :

L'étape qui suit est un peu plus subtile. Il va dans un premier temps nous falloir remarquer qu'en région 6, le 6 se trouve obligatoirement dans une des deux cases pointées par l'indice 20 en 6 cases.



Étape 6 :

Ceci étant noté, et la somme des cases L1C1, L2C2, et L3C3 étant supérieure ou égale à 7 (2+3+2), on peut en déduire que le 9 ne saurait être présent en L4C4, faute de quoi nous aurions L1C1+L2C2+L3C3+L4C4=16 ou plus, qui ajoutés au 6 en L5C5 ou L6C6 contrediraient l'indice 20. Donc L5C3=9 et L1C4=9. Le même raisonnement permet d'éliminer le 9 de L2C2 et de placer un 9 en L2C3.



Étape 7 :

Les 6 en régions 4 et 6 sont maintenant évidents :



Étape 8 :

La somme 20 en 3 cases, compte tenu de la présence du 6 en son sein, n'a plus qu'une possibilité : 7+6+7=20.



Étape 9 :

Rebelote. De même qu'à l'étape 6, il suffit de déterminer la somme minimale des cases L1C1, L2C2, L4C4 et L6C6 pour constater que la présence d'un 7 en L3C3 est exclue : L3C1=7, et les autres 7 tombent.



Étape 10 :

Il ne nous reste plus qu'un chiffre à déterminer ! Nous savons que chaque ligne, colonne et région doivent contenir les chiffres 1, 5, 6, 7 et 9 ainsi qu'un ultime chiffre que nous nommerons X. Or nous avons suffisamment de lignes, colonnes et régions quasiment pleines pour pouvoir déterminer l'emplacement des six occurrences de ce chiffre mystère.



Étape 11 :

Cette étape est à mon goût la plus élégante de la résolution, et la comprendre pourra certainement vous être utile à l'avenir sur d'autres jeux.
Dans la grande diagonale correspondant à l'indice 20 en 6 cases, nous avons L1C1+X+X+X+6+X=20. Dit autrement : L1C1+6+4X=20. 6 est pair ; 4X est pair quel que soit X ; et 20 est pair. Par conséquent, la différence entre 20 et (6+4X), à savoir L1C1, doit également être paire : L1C1#5, donc L1C1=6, et les derniers chiffres tombent à l'exception de notre fameux X.



Étape 12 :

Enfin, reste à trouver quel chiffre satisfait l'équation 6+6+4X=20, ce qui ne devrait pas vous poser problème outre mesure. C'en est fini !



Sur cette ultime solution, je conclus cette série de résolutions détaillées. J'espère qu'elle vous aura été utile et, au delà de l'aspect technique, qu'elle vous aura permis de pénétrer brièvement l'esprit du concepteur de jeux et de percevoir une partie de ce qui fait à nos yeux la beauté de notre activité de création.
Les championnats du monde de sudoku et de jeux de logique débutent dans à peine plus de dix jours ; ils feront l'objet d'un prochain message. Notez dès maintenant qu'une première version du livret d'instructions des épreuves de sudoku est disponible depuis la nuit dernière, à l'adresse http://uk2014.org/download.php?fileid=151&md5=d13558d4aec3f77af9d2941209c77617. N'hésitez pas à y jeter un oeil.

Wednesday, July 23, 2014

Grille de la semaine #93

Le Battleships est un des jeux que j'apprécie le moins de résoudre et, ce qui va souvent de pair, je souffre le plus souvent d'un dramatique manque d'efficacité sur les jeux de ce type. Toutefois, un des aspects intéressants des puzzles est qu'il est parfois possible de dénicher - ou de concevoir - des variantes d'un jeu qui en modifient suffisamment le principe pour que le résultat propose une expérience infiniment plus plaisante à nos yeux que l'original. C'est ainsi qu'en tombant sur cette variante de Battleships j'eus le sentiment que je pourrais en tirer quelque chose qui me réconcilierait dans une certaine mesure avec son aïeul, et je conçus la grille suivante ; raisonnablement facile, mais porteuse d'un cheminement que j'espère esthétique.

As much as I dislike Battleships, I was glad the day I first saw this variant since I felt I could make something nice out of it, which would in some way reconcile me with one of my most dreaded puzzles. The result is as follows; a rather easy puzzle but with some nice deductions to make, or so I hope.

Règles :
 Retrouvez la position de chacun des bateaux de la flotte, sachant que deux bateaux ne peuvent se toucher orthogonalement ou diagonalement.
°°°°°°°°°°°°°°°°°°°°
Shade in the position of the listed ships so that no ships touch each other, not even diagonally.

#106 Retrograde Battleships

 




Cheminement :


De façon générale je décrirai les bateaux à l'aide de leur taille et de leur position relative, ou des coordonnées des cases qui les composent. Par commodité, je désignerai par "bateau de taille 4" ou "bateau de 4 unités" un bateau rectiligne de 4 cases. Les autres bateaux de 4 cases hériteront du vocable "bateau circulaire".

Étape 1 :

Notons en premier lieu l'agencement particulier des bateaux de 4 unités ; disposés en carré, ils exercent une importante contrainte sur les bateaux de 3 unités : en effet, si nous noircissons les deux bateaux de 3 unités situés à l'extérieur du carré en question, il devient plus que délicat de placer un bateau de 4 unités. De plus, il est visiblement impossible de noircir les deux bateaux de 3 unités situés à l'intérieur du carré (ils sont en contact diagonalement). Nous allons donc devoir noircir exactement un bateau de taille 3 dans le carré, et un en dehors. Conclusion : les bateaux de taille 1 situés dans le carré sont éliminés car ils touchent les deux bateaux de taille 3.



Étape 2 :

Nous venons de dire que, des deux bateaux de taille 3 situés en dehors du carré, un sera noirci. Celui-ci, quel qu'il soit, éliminera les cinq bateaux de taille 1 le touchant - ne laissant, dans l'ensemble de la grille, que 7 cases pouvant héberger un bateau d'une unité. Et dans tous les cas, l'un d'eux prendra place en L6C8 ou L7C8, éliminant les quatre cases en contact avec elles et par voie de conséquence les bateaux auxquelles elles appartiennent.



Étape 3 :

Deux bateaux de taille 4 ont sombré. Les deux restants sont en contact avec le bateau de taille 3 qui occupe L4C4, L4C5 et L5C4 : il coule à son tour, ainsi que les bateaux de taille 2 qui se trouvaient dans le même cas.



Étape 4 :

Retour aux coins. Nous l'avons vu, pour placer les bateaux de 1 unité et ceux de 4 unités, deux configurations sont possibles.

Configuration a :





 Configuration b :



Certaines cases seront, dans tous les cas, en contact avec un bateau : cela s'applique par exemple à L1C6 qui touchera L2C7 dans le cas de la configuration a, et L1C7 dans le cas de la B. Éliminons ces cases : ce sont pas moins de quatre bateaux de 2 unités que voilà disparus !





Étape 5 :

Il est temps de travailler sur les bateaux de 2 unités. Quatre restent, nous en faut trois. Noircir à la fois le bateau du haut et celui de gauche signifierait condamner nos deux bateaux de taille 4 ; cette possibilité est donc exclue. Par conséquent, si l'un d'entre eux deux au maximum sera noirci, les deux bateaux restants se trouvent validés. L'incertitude est maintenant levée concernant le bateau d'une unité en L6C8/L7C8, et celui-ci élimine le bateau circulaire du coin inférieur droit.



Étape 6 :

Les deux bateaux circulaires restants touchent le même bateau de taille 4 : nous savons ce que cela signifie pour celui-ci.



Étape 7 :

Nous savons également ce que cela veut dire pour le dernier bateau de 4 unités restant à flot : le naufrage de son alter-ego conforte sa position et lui permet d'éliminer deux bateaux supplémentaires.



Étape 8 :

Plus qu'un bateau de 3 unités de visible : notre choix est arrêté. Les cinq bateaux adjacents disparaissent bon gré mal gré et nous laissent face à une grille qui fleure bon la résolution victorieuse.



Étape 9 :

L'emplacement des trois bateaux unitaires est décidé d'emblée ; celui du dernier bateau de taille 2 est adopté dans la foulée, et son voisin immédiat étant éliminé, il nous offre sur un plateau la position du bateau circulaire.

Wednesday, July 16, 2014

Grille de la semaine #92 [League of Extraordinary Ladies and Gentlemen #67]

Aujourd'hui, étude d'un sudoku classique de difficulté modeste mais comportant quelques éléments intéressants que l'on retrouve régulièrement sur les grilles comportant peu de chiffres donnés (19 en l'occurrence).
Pour rappel, les grilles de la League sont jouables en ligne à l'adresse http://sudokucup.com/node/3172 avec un délai de 24h.

Today I will study a classic sudoku of moderate difficulty but which includes some interesting elements that we will often find on such sudokus with few given digits (19 here).
Remember that you can solve the puzzles from the League online on http://sudokucup.com/node/3172 with a 24h delay.

Règles :
Chaque ligne, colonne et région doivent contenir les chiffres de 1 à 9.
°°°°°°°°°°°°°°°°°°°°
Each row, column and region must contain the digits from 1 to 9.

#105 Sudoku

 




Cheminement :


Étape 1 :

Outre le motif formé par les chiffres donnés, la grille présente des éléments de symétrie ; les repérer permet une progression rapide, notamment au niveau de l'entame de la grille. Nous allons commencer par placer deux chiffres évidents, le 3 en L4C1 et le 8 en L6C9 (forcés par, respectivement, les 3 en L2C3/L6C8 et les 8 en L3C7/L4C2). Ceci fait, deux doublets symétriques l'un de l'autre apparaissent : 12/12 en L4C89 et 45/45 en L6C12.



Étape 2 :

Autre élément qu'il importait de visualiser rapidement : il est possible de compléter la ligne 5 d'emblée !



Étape 3 :

Symétrie là encore : les doublets posés à l'étape 1 vont s'accorder avec les chiffres donnés en régions 2 et 8 pour faire émerger deux doublets 12/12 et 45/45 supplémentaires, en région 5.



Étape 4 :

Les deux dernières cases de la région 5 se remplissent dans la foulée, et suivent quatre cases de plus en régions 4 et 6.



Étape 5 :

Employons-nous maintenant à casser les doublets en région centrale : en région 3, le 5 est forcément en L2C9 ou L3C9 ; par conséquent on a un 5 en L9C7, puis L8C5.



Étape 6 :

Voilà le cas du doublet 45 réglé : L4C5=4 et L4C6=5. Pour la forme, n'oublions pas L7C6=4.



Étape 7 :

Plusieurs placements faciles découlent, à commencer par les deux dernières cases de la colonne 6 : L1C6=3 et L2C6=9. S'ensuivent tous les 3 manquants et l'incertitude concernant le 5 en région 3 est levée.



Étape 8 :

Il est temps de s'attaquer, de la même façon, au doublet 12. Aidons-nous pour ce faire de la colonne 3 : 128 manquent, mais 1 et 8 figurent déjà en ligne 3 ; d'où on déduit L3C3=2. Combinons cette découverte au 2 de L2C7 pour poser un 2 en L1C5 et trancher définitivement la question de la région centrale.



Étape 9 :

Ce qui suit ne devrait vous poser aucune difficulté si vous avez assimilé les étapes précédentes. Procédons au plus simple, chiffre par chiffre : en partant de la région 8 et en progressant dans le sens horaire, nous allons pouvoir placer tous les 1 restants.



Étape 10 :

Même procédé avec les 8, mais... de façon symétrique ! Départ en région 2 et progression antihoraire :



Étape 11 :

Finissons-en avec la région 2 à l'aide du 6 en L4C4 et, sans déroger à l'habitude, plaçons tous les 7 (cette fois un aller-retour sera nécessaire), suivis des 6 et d'un 9 évident.



Étape 12 :

Pour conclure, le choix vous est laissé entre la solution évidente consistant à en passer par la région 9, et celle un peu plus subtile demandant de repérer un rectangle interdit. Le choix est vôtre !


Wednesday, July 9, 2014

Grille de la semaine #91

Cinquième grille de cette série, le Fillomino de l'épreuve 3 de puzzles ; grille de difficulté modérée pour un tournoi national mais comportant tout de même un cheminement bien défini. Cela ne vous aura peut-être pas échappé : la grille est conçue de façon presque symétrique. À l'exception des deux 5, chaque 4 est en effet symétrique d'un autre indice. Ce qui aurait pu n'être qu'un détail esthétique a en réalité un impact sur la résolution, comme nous le verrons.

This Fillomino comes from the third round of the french puzzle qualifiers. The puzzle was reasonably easy for such a competition but still had a defined solving path to be followed. You may have observed that there is quite an abundance of 4s in the grid (and that they are symmetrical to the other digits, except for the two 5s); as we will see, apart from the esthetic aspect it gives to the puzzle, this will also have an impact on its resolution.

Règles :
Placez un chiffre par case puis divisez la grille en zones comportant uniquement des chiffres identiques et dont l'aire (exprimée en cases) est égale à ce chiffre.
Deux zones de même aire ne peuvent se toucher orthogonalement.
°°°°°°°°°°°°°°°°°°°°
Place one digit per cell, then divide the grid into areas composed of cells each containing the same digit.
Each area's size must be equal to the digit it contains.
Two areas of the same size cannot touch each other orthogonally.

#104 Fillomino

 




Cheminement :


Étape 1 :

Mettons-nous en train en délimitant les quatre zones évidentes : les deux 1, ainsi que les deux 5 qui n'ont nul moyen de s'échapper.



Étape 2 :

Comme je le disais en introduction, l'abondance de 4 dans la grille n'est pas anodin. Ce sont eux qui vont nous fournir le point de départ, dans le coin supérieur droit : le 4 en L1C10, qu'il se prolonge en L1C9 ou L2C10, rejoindra le 4 en L2C9 pour former un bloc de 3 cases au moins ; ce dernier 4 ne pourra donc appartenir à la même zone que L3C8 (faute de quoi ces 4 formeraient une zone d'au moins 5 cases).
Notez qu'il est d'ores et déjà possible d'effectuer quelque progrès dans le coin supérieur gauche de la grille, mais cela ne nous mènera pas loin pour le moment ; gardons ce coin de côté pour la suite de la résolution, dans laquelle il s'inscrira naturellement.



Étape 3 :

De la même façon, L3C8 sera nécessairement lié à L4C7, ce qui impose de placer une bordure entre  L4C7 et L5C6.



Étape 4 :

Le 4 de L5C6 est à présent exploitable. Il ne peut se prolonger que d'une case vers le bas, sans quoi il entrera en contact avec au moins deux des 4 du secteur pour former une zone de 5 cases ou plus.
En vérité, il ne peut même pas se prolonger d'une case dans ce sens : considérons le 4 en L7C7 ; qu'il monte ou parte vers la gauche, il entrera en contact avec l'une des cases L6C8 ou L8C6, formant une zone de 3 cases. Un prolongement de L5C6 en L6C6 viendrait ajouter deux cases supplémentaires à cette zone, ce qui est exclu.
Interdisons par conséquent à notre 4 de descendre et prolongeons-le d'une case vers la gauche.



Étape 5 :

Nous pouvons prolonger notre avancée vers la gauche d'une case supplémentaire en raison de la présence d'un 4 en L4C7, qui nous empêche de monter de plus d'une case. Puis, ceci fait et le chemin du 6 devant à présent en passer par L4C5, il nous est possible d'en finir avec cette zone 4.



Étape 6 :

Le cheminement du 6 est tout tracé : il est déjà possible de le prolonger de 4 cases.



Étape 7 :

Joie ! En commençant par le 3 de L3C5, la totalité du coin supérieur gauche de la grille tombe en un clin d'oeil.



Étape 8 :

C'est tout pour la partie gauche de la grille ; nous allons en revenir à nos 4 et plus spécifiquement aux cases L1C6 et L2C7, dont le tracé de la zone qui les unit est maintenant un jeu d'enfant et fait apparaître une discrète zone 1, coincée entre les 4 ; ce n'est pas la dernière que nous croiserons.



Étape 9 :

Je l'annonçais, voici une autre zone 1 mise au jour par la réunion de L1C10 et L2C9 :



Étape 10 :

Une nouvelle zone 4 réunit L3C8 et L4C7 ; une zone 1 pour remplir l'espace, et nous allons enfin pouvoir nous attaquer au coin inférieur droit de la grille.



Étape 11 :

Si L6C8 se poursuit en L6C7 pour s'adjoindre les services de L7C7, la zone 4 considérée ne pourra pas faire plus de trois cases. Plaçons donc une bordure entre L6C7 et L6C8, et prolongeons L6C8 vers la droite : une zone 4 de plus !



Étape 12 :

Jouons les horlogers : en partant de la zone 4 fraîchement apparue, nous allons faire le tour de la zone 5 dans le sens horaire, alternant zones de 1 et 4 cases :



Étape 13 :

La fin approche ! L7C7 et L8C6 doivent se rejoindre mais ne pourront pas se prolonger vers le haut :



Étape 14 :

Notre zone 9 peut-elle tenir toute entière dans le corridor qui s'est ouvert à sa droite ? Certes pas, elle va devoir descendre d'une case au moins, et ceci élimine l'incertitude qui planait autour de notre zone 4 :



Étape 15 :

Le cas du 9 est réglé ; penchons-nous sur le 5 de L7C4 : il doit s'étendre d'au moins 3 cases vers la gauche, d'où L7C3, L7C2 et L8C2=5. La zone 6 est alors tracée et, par un mécanisme d'influence réciproque dont le jeu du Fillomino est friand, la zone 5 tombe à sa suite.
Concluons cette longue étape en posant deux 3.



Étape 16 :

La présence d'un 1 en L10C1 nous interdit de prolonger la zone 3 adjacente en L10C3, faute de quoi apparaîtrait une seconde zone 1 contiguë à la première : L9C1=3.



Étape 17 :

Enfin, et via le même mécanisme - appliqué en considérant la zone 2 de L8C3/L9C3 -, nous pouvons affirmer que L10C4 contiendra un 3 ; et deux ultimes zones d'une case viendront mettre un point final à cette résolution.