Le plateau quotidien fait sept tuiles de large et sept de haut. Il paraît petit. Puis vous comptez de combien de façons on peut le faire pivoter, et le nombre cesse tout à fait de paraître petit.
Rédigé et édité en anglais. Cette version française a été produite par traduction automatique ; en cas de doute sur un point précis, l'original anglais fait foi. Lire l'original en anglais →
Chaque tuile de Conduit possède quatre orientations possibles, tournée de zéro, un, deux ou trois quarts de tour par rapport à sa position. 1 Donnez à chacune des quarante-neuf cases de la grille quotidienne un choix indépendant parmi ces quatre-là, et le nombre d'états distincts du plateau est 449. Écrit en entier, cela donne 316 912 650 057 057 350 374 175 801 344, soit plus de trois cents milliards de milliards de milliards de configurations, parmi lesquelles le jeu vous demande d'en trouver une qui soit entièrement allumée et sans fuite.
Le brouillage qui vous remet un casse-tête choisit, pour chaque tuile, un nombre aléatoire de quarts de tour compris entre zéro et trois. 1 Le plateau que vous rencontrez est donc tiré uniformément dans cet espace gigantesque, à une exclusion près, soigneusement ménagée par le jeu pour éviter de vous distribuer une grille déjà résolue. 1 La force brute est hors de question : les tests du jeu lui-même relèvent qu'essayer les quatre rotations de chaque tuile est exponentiel, et ils ne lancent la recherche exhaustive que sur des plateaux miniatures de neuf cases ou moins. 2
Ce chiffre spectaculaire compte trop large, car certaines tuiles se moquent de la façon dont vous les tournez. Une croix, avec des connecteurs sur ses quatre côtés, paraît identique dans les quatre orientations ; la faire pivoter ne change rien. Une ligne droite n'a que deux aspects distincts, horizontal et vertical, parce qu'un demi-tour la ramène sur elle-même. Seules les formes asymétriques, le coude, le té et l'extrémité à connecteur unique, possèdent réellement quatre orientations distinctes. 3
| Forme | Connecteurs | Rotations distinctes | Symétrie |
|---|---|---|---|
| Extrémité (nœud/ampoule) | 1 | 4 | aucune |
| Ligne | 2 | 2 | demi-tour |
| Coude | 2 | 4 | aucune |
| Té | 3 | 4 | aucune |
| Croix | 4 | 1 | complète |
Les formes sont nommées dans les notes de conception du jeu ; les nombres d'orientations distinctes découlent du fait que le masque de connecteurs sur quatre bits reste inchangé sous les rotations énumérées. 3 L'espace de recherche effectif est plus petit que 449 d'un facteur égal exactement au produit de ces symétries par tuile, mais sur tout plateau comportant un bon mélange de coudes et de tés, il reste astronomiquement vaste.
Retournez la question. Oubliez les orientations que vous pourriez essayer ; demandez-vous plutôt combien de plateaux résolus sont possibles, tout simplement. Une grille de Conduit achevée est un ensemble de conduites connexe, où l'énergie atteint chaque tuile, et dépourvu de boucle inutile, parce que ce que construit le générateur est un arbre couvrant : connexe, acyclique, un seul chemin de la source vers chaque nœud. 3 Chacun de ces câblages est, précisément, un arbre couvrant du graphe de la grille, où les sommets sont les cases et les arêtes les frontières communes qu'une conduite peut franchir.
Et les arbres couvrants se comptent exactement. Le théorème matrice-arbre de Kirchhoff, un résultat de 1847, dit que le nombre d'arbres couvrants d'un graphe quelconque égale n'importe quel cofacteur de sa matrice laplacienne, un déterminant calculable en temps polynomial. 4 Pour les grilles, le compte explose avec la taille : un modeste quadrillage 4×4 possède déjà 100 352 arbres couvrants, et le nombre grimpe férocement à partir de là. Chacun d'eux est une solution de Conduit légitime et entièrement allumée. Le casse-tête est difficile non pas parce que les réponses sont rares, mais parce qu'elles sont cachées dans une foule bien plus vaste de quasi-réponses.
Les états résolus sont dénombrables et nombreux ; les états brouillés sont dénombrables et immensément plus nombreux. Résoudre, c'est chercher une aiguille dont vous savez qu'elle existe, parce que le jeu l'y a cachée exprès.
Vous pourriez espérer que le casse-tête se décompose : fixez le coin supérieur gauche, puis la tuile voisine, et avancez proprement jusqu'au coin opposé. Il arrive qu'une portion du plateau s'y prête. Une tuile placée dans un coin n'a que deux bords en contact avec des voisines, si bien que ses connecteurs sont fortement contraints ; une tuile extrémité posée sur le bord ne peut pointer que vers l'intérieur. Ces coups forcés offrent des points d'appui.
Mais les deux conditions de victoire ne s'enchaînent pas avec autant de complaisance. Sans fuite est une propriété locale, que vous pouvez vérifier bord par bord. Sous tension ne l'est pas : qu'une tuile soit allumée dépend d'une chaîne ininterrompue de jonctions remontant jusqu'à la source, éventuellement à travers tout le plateau. 3 Une modification faite dans un coin peut plonger une région lointaine dans le noir en rompant l'unique chemin qui l'alimentait. Ce couplage, où le sort de chaque tuile tient potentiellement à un trajet traversant toute la grille, est ce qui empêche un casse-tête de rotation de se réduire à une simple comptabilité, et c'est pourquoi les solveurs de la famille Net/Pipes au sens large s'appuient sur la propagation de contraintes et la recherche plutôt que sur un simple balayage de gauche à droite. 5
Malgré l'immensité de l'espace d'états, la quantité sur laquelle Conduit vous note est minuscule et humaine : le nombre de fois où vous avez touché l'écran. Le score vaut 1000 − 4 × coups − 2 × secondes, avec un plancher à zéro. 3 Il existe un nombre minimal théorique de rotations pour un plateau donné, la somme, sur toutes les tuiles, du plus petit nombre de quarts de tour nécessaires pour atteindre une orientation résolue, et chaque tour gaspillé au-delà vous coûte quatre points, chaque seconde d'inaction deux.
Le vrai jeu se tient donc entre deux faits énormes et un petit. La botte de foin fait 449 orientations de large ; les aiguilles sont les nombreux arbres couvrants de la grille ; et votre travail consiste à aller de l'une aux autres en répétant le seul coup légal aussi peu de fois que possible. La combinatoire garantit qu'une réponse s'y trouve. Le barème vous met discrètement au défi de la trouver sans errer. 4