Polyominos

• 5Tétrominos libres, ceux à quatre carrés. Sept si l'on distingue une pièce de son reflet, comme le fait Tetris.
• 12Pentominos, à cinq carrés. Ce nombre ne bouge pas : il a été énuméré, pas estimé.
• 0Rotation autorisée dans Woodfit. Les pièces entrent telles qu'elles sortent du bac.

Des carrés, beaucoup de carrés

Un polyomino, au départ, c'est vraiment pas sorcier : tu prends des carrés de même taille et tu les colles bord à bord. Pas par un petit coin, hein. Il faut qu'ils partagent un côté entier. Voilà. Tu viens de faire des maths.

Le mot, lui, vient du mathématicien Solomon Golomb, qui a baptisé la famille en 1953 et en a fait un sujet de recherche à part entière.

Avec un seul carré, on parle de monomino. Avec deux, de domino. Trois donnent les trominos. Et à quatre carrés, on arrive aux tétrominos.

Ceux-là, tu les connais probablement déjà, même si tu n'as jamais prononcé « tétromino » de ta vie. Ce sont les fameuses pièces de Tetris.

Mathématiquement, il existe cinq tétrominos libres : deux formes sont considérées comme identiques si on peut passer de l'une à l'autre en la tournant ou en la retournant. Mais dans Tetris, retourner une pièce comme une crêpe n'est évidemment pas prévu. Les formes miroir sont donc parfois comptées séparément, ce qui donne les sept pièces familières du jeu.

Ajoute encore un carré et ça commence à devenir sérieux : tu obtiens les pentominos. Il en existe exactement douze libres. Pas onze, pas treize : douze.

Et avec ces douze petites bestioles, on peut déjà fabriquer des puzzles étonnamment retors. Remplir un rectangle, éviter les trous, comprendre pourquoi un assemblage est impossible alors qu'il avait pourtant « l'air de passer »… C'est exactement le terrain de jeu de Woodfit.

Combien y en a-t-il ?

Le nombre croît vite et on ne connaît pas de formule pour le calculer ; les valeurs ci-dessous viennent d’énumérations exhaustives par ordinateur. Deux formes ne comptent que pour une quand une rotation ou une symétrie transforme l’une en l’autre.

Tetris utilise sept pièces et non cinq parce qu’il traite les images miroir comme distinctes : S et Z, J et L, sont symétriques l’une de l’autre, et sur un écran plat aucune rotation ne transforme l’une en l’autre.

Le truc de la parité

Une vérification permet d’écarter les puzzles impossibles avant même de poser une pièce. Colorie la région cible comme un damier, puis compte.

Certaines pièces couvrent autant de cases sombres que de claires où qu’elles soient posées ; d’autres couvrent une répartition inégale, qui peut basculer d’un côté ou de l’autre selon leur position. Passe en revue ce que ton jeu de pièces peut couvrir et compare avec ce que la région contient réellement. Si les totaux ne peuvent pas coïncider, aucun agencement n’existe.

C’est le raisonnement qui montre qu’un échiquier privé de deux coins opposés ne peut pas être couvert par des dominos : les deux cases retirées sont de la même couleur, il reste donc 30 cases d’une couleur et 32 de l’autre, et chaque domino en prend une de chaque.

Lire un plateau

• Pose d’abord les pièces encombrantes. Les longues barres et les croix ont souvent le moins de positions qui marchent ; les petites formes compactes rentrent à peu près partout et peuvent attendre.
• Commence par les coins et les bords. Ils ont le moins de façons d’être couverts, donc ils se fixent tôt.
• Surveille la case isolée. Un trou d’une seule case que rien ne peut remplir signifie que l’agencement est déjà mort : autant recommencer plutôt que continuer.

Les douze pentominos

Les douze pentominos portent des noms de lettres d’après leur forme : F, I, L, N, P, T, U, V, W, X, Y, Z. Ensemble ils couvrent 60 cases, d’où le défi classique : paver un rectangle 6×10, 5×12, 4×15 ou 3×20 avec les douze.

Le rectangle 6×10 admet 2 339 solutions distinctes, en ne comptant qu’une fois celles qui se déduisent l’une de l’autre par symétrie. Le 3×20 en admet 2. Mêmes pièces, même aire : la forme du cadre suffit à expliquer l’écart, et c’est elle qui rend un plateau tolérant et un autre presque rigide.

Pourquoi c’est difficile

Décider si un ensemble de polyominos pave une région donnée est NP-complet. Au-delà des petits plateaux, on ne connaît pas de raccourci : une approche classique consiste à poser une pièce, revenir en arrière quand le placement échoue, et essayer la suivante.

Woodfit, comme le disent les règles plus haut, ne fait jamais tourner ni retourner une pièce. Ça réduit la recherche, puisque chaque pièce n’a qu’une orientation, mais ça supprime aussi le rattrapage habituel qui consiste à pivoter une forme gênante, et un creux de la bonne aire peut donc n’avoir aucune solution.

Dans ce jeu

Les commandes

Fais glisser une pièce du bac vers le creux. Un fantôme montre où elle va tomber quand la position est légale ; sinon les cases qui bloquent passent au rouge et la pièce retourne au bac.

Touche une pièce posée pour la reprendre, ou fais-la glisser directement ailleurs. Barre du haut : retour à gauche, ampoule et recommencer à droite. Elles se déclenchent au relâchement, glisse à côté pour annuler.

Les règles

Les pièces ne tournent jamais et ne se retournent pas : elles entrent telles qu’elles sont dans le bac. Chaque creux a toujours une solution, et trois étoiles, c’est aucune reprise.

L’ampoule retire le moins de pièces bloquantes possible et en pose une définitivement. C’est une vidéo récompensée dans l’app, et ça ne te coûte pas d’étoile.

La progression est gardée côté serveur : elle te suit sur un nouveau téléphone.

Questions fréquentes