Le Défi des 12 pièces : le casse-tête de logique

Le principe

• La grille compte 5 lignes de 11 cases, soit 55 alvéoles.
• Les 12 pièces sont faites de billes soudées : une pièce de 3 billes, trois de 4 billes et huit de 5 billes. Cela fait 55 billes, exactement le nombre de cases. Chaque pièce se tourne et se retourne, comme une pièce en plastique qu'on retourne sur la table.
• Chaque défi pose déjà une partie des pièces, marquées d'une pastille blanche : elles ne bougent pas. À vous de placer les autres.
• La grille est réussie quand toutes les cases sont remplies. Si vous trouvez une autre façon de tout faire tenir que celle prévue, elle compte aussi.

Cinq niveaux de difficulté

• 1 · Découverte. 3 pièces à poser. De quoi comprendre le jeu en quelques minutes, y compris pour les enfants.
• 2 · Facile. 5 pièces à poser.
• 3 · Intermédiaire. 7 pièces à poser.
• 4 · Difficile. 9 pièces à poser : il faut penser aux pièces qui resteront à la fin.
• 5 · Maître. Les 12 pièces sur la grille vide.

Chaque grille est tirée au hasard : l'ordinateur remplit la grille entière, puis retire les pièces que vous aurez à poser. Aux niveaux 1 à 4, il vérifie avant de vous la proposer qu'elle n'a qu'une seule solution. La grille vide du niveau 5 en a beaucoup plus : en les comptant toutes, le programme en a trouvé 455 670, sans compter les grilles simplement tournées ou retournées (1 822 680 en les comptant). En trouver une seule reste un vrai défi.

Le défi du jour

Chaque jour à minuit, heure de Paris, une nouvelle grille, la même pour tous les joueurs. Sa difficulté monte au fil de la semaine : niveau 2 le lundi et le mardi, niveau 3 le mercredi et le jeudi, niveau 4 du vendredi au dimanche. Réussissez-le plusieurs jours de suite pour allonger votre série.

L'aide sur les erreurs

Une grille peut devenir impossible bien avant d'être pleine : une pièce mal placée suffit, et sur la table, on ne s'en aperçoit souvent qu'à la toute fin. Ici, après chaque pièce posée, l'ordinateur vérifie qu'il reste au moins une façon de finir. Sinon, il vous le dit tout de suite, entoure en rouge la zone en cause et vous indique la pièce à retirer. Il nomme le problème :

• Une case isolée, ou un trou de deux cases : aucune pièce n'est assez petite pour le remplir.
• Une zone fermée au mauvais compte : 7 cases, par exemple, quand il ne reste que des pièces de 5. Aucune addition ne tombe juste.
• Une zone fermée à la mauvaise forme : le compte est bon, mais aucune pièce restante ne s'y emboîte.
• Une pièce sans place : elle ne rentre plus nulle part.
• Des pièces qui ne tiennent pas toutes ensemble : chaque zone paraît faisable seule, mais pas toutes à la fois. C'est l'erreur la plus difficile à voir, et l'ordinateur ne la signale qu'après avoir essayé toutes les combinaisons.

Dans les options, l'aide peut ne se déclencher que sur demande (bouton « Vérifier ») ou ne jamais s'afficher. Les poses sans issue sont alors comptées sans être signalées, et apparaissent dans le bilan de fin de grille.

Indices, chrono et étoiles

• L'indice vient en trois temps. D'abord la case la plus contrainte de la grille, celle que le moins de pièces peuvent couvrir : c'est souvent un coin, et c'est par là qu'il vaut mieux commencer. Ensuite, la pièce qui y va. Enfin, sa place exacte, qu'il suffit de toucher pour y poser la pièce.
• Le chrono démarre à votre premier geste et s'arrête quand la page n'est plus affichée. Il peut être masqué dans les options.
• Les étoiles récompensent une grille réussie : trois sans indice ni pose sans issue, deux avec une ou deux aides, une au-delà. Afficher la solution compte comme un abandon.
• Annuler revient sur votre dernière action. Et si vous fermez la page, la grille en cours reprend là où vous l'aviez laissée.

Les profils de joueurs

Chaque joueur de la famille peut avoir son profil, avec son pseudo et son avatar : bilan par niveau avec records de temps, série au défi du jour, historique, et conseils tirés des erreurs qui reviennent d'une grille à l'autre. Les grilles abandonnées ou réussies avec beaucoup d'aide sont mises de côté pour être refaites sans aide. Les profils restent dans le navigateur, et un fichier de sauvegarde permet de les retrouver sur un autre appareil.

Les 12 pièces

Comment l'ordinateur sait qu'une grille est impossible

Remplir la grille est ce que les mathématiciens appellent un problème de couverture exacte : chaque case vide doit être couverte une fois et une seule, et chaque pièce restante posée une fois et une seule. Pour le résoudre, le programme utilise l'algorithme X de Donald Knuth, informaticien de l'université Stanford et auteur de la série de référence The Art of Computer Programming. Il essaie les poses une à une, en commençant toujours par la case qui en admet le moins, et revient en arrière dès qu'une case ne peut plus être couverte. La technique des « liens dansants », que Knuth a décrite dans un article de 2000, lui permet de défaire et refaire chaque essai très vite.

Avant de lancer cette recherche, le programme fait les contrôles qu'un joueur peut faire à l'œil (cases isolées, zones au mauvais compte ou à la mauvaise forme), pour pouvoir nommer le problème. Sur la plupart des grilles, le verdict tombe en quelques millisecondes, sur votre appareil.

Source : Donald E. Knuth, « Dancing Links », 2000 (article en anglais).

Questions fréquentes