Comment fonctionne le numberlink
Thread Link est un casse-tête numberlink : des paires de nombres identiques sur une grille doivent être reliées par des chemins qui ne se croisent jamais. L’idée a plus d’un siècle, elle cache un problème que les ordinateurs trouvent difficile, et quelques habitudes simples rendent la résolution bien plus facile.
Les règles
La grille est un quadrillage carré portant quelques nombres, chacun exactement deux fois. Reliez chaque paire par un chemin qui passe d’une case à une case voisine, horizontalement ou verticalement. Les chemins peuvent tourner autant qu’ils veulent, mais deux chemins ne peuvent jamais partager une case : ils ne se croisent donc jamais, et un chemin ne peut pas passer sur un nombre qui n’est pas le sien. Dans Thread Link, comme dans la plupart des versions modernes, la grille n’est terminée que lorsque les chemins couvrent aussi toutes ses cases.
Un casse-tête à la longue histoire
Les casse-têtes de chemins de ce genre remontent au XIXe siècle : Sam Loyd en publia une version en 1897, et les Amusements in Mathematics de Henry Dudeney, parus en 1917, en proposent un où des automobilistes doivent rejoindre leur garage sans que leurs itinéraires se croisent. L’éditeur japonais Nikoli a popularisé la forme en grille sous le nom de Number Link, et sous celui d’Arukone avec des lettres au lieu des nombres. Le casse-tête est ensuite devenu un favori sur téléphone, où tracer un chemin du doigt est très naturel.
Pourquoi c’est difficile pour les ordinateurs
Relier des paires de points sur une grille sans croisement, c’est la tâche d’un ingénieur qui trace les pistes d’un circuit imprimé, et dans le cas général elle est NP-complète : aucune méthode connue ne résout rapidement tous les grands cas, alors que vérifier une réponse donnée est facile. Les petites grilles ne posent aucun problème à un ordinateur qui essaie des chemins et revient en arrière, mais le nombre de possibilités explose avec la taille de la grille. Les humains résolvent le numberlink avec des motifs et de la logique plutôt qu’en essayant tout.
Comment Thread Link crée ses grilles
Le jeu cherche d’abord un chemin aléatoire qui passe exactement une fois par chaque case, un chemin hamiltonien. Il part d’un simple chemin en serpentin et le remodèle des milliers de fois grâce à un mouvement appelé backbite. Il coupe ensuite le chemin en morceaux d’au moins trois cases, en rejetant les coupes où les deux extrémités d’un morceau se touchent, et place un nombre aux deux bouts de chaque morceau. Comme les morceaux couvrent toute la grille, chaque grille a une solution qui la remplit. Un générateur de nombres aléatoires initialisé par une graine associe chaque grille à sa taille et à son numéro.
Astuces de résolution
Commencez par les bords et les coins : une paire dont les nombres sont sur le même bord peut souvent le longer. Repérez les cases qui n’ont qu’une seule voisine libre, car un chemin devrait y entrer et en ressortir par le même côté, ce qui n’est possible que si un nombre s’y trouve. Ne laissez jamais une poche de cases vides qu’aucun chemin ne peut atteindre. Si les deux nombres d’une paire sont proches, reliez-les tôt et au plus court, pour qu’ils ne gênent pas les autres. Et quand la grille est pleine de paires reliées mais que quelques cases restent vides, un fil peut généralement faire un détour par elles.
Questions fréquemment posées
Le numberlink, est-ce la même chose que les points à relier ?
Non. Dans un jeu de points à relier, on relie des points numérotés dans l’ordre pour dessiner une image. Au numberlink, on relie des paires de nombres identiques, et la difficulté vient de ce que les chemins ne peuvent pas se croiser et doivent, dans la plupart des versions, remplir la grille.
Chaque grille n’a-t-elle qu’une seule solution ?
Les grilles des journaux et des livres sont généralement vérifiées pour n’en avoir qu’une. Thread Link crée ses grilles à la volée, si bien que certaines peuvent être remplies de plusieurs façons ; le jeu accepte toute solution valable.
Par quelle taille de grille commencer ?
5×5 ou 6×6 pour apprendre les gestes, 7×7 ou 8×8 pour une partie rapide, et 10×10 ou 12×12 si vous en voulez une plus longue. Les grandes grilles ont plus de paires et des chemins plus longs : elles demandent donc plus de réflexion.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Jouer à Thread Link