Numberlink

L'objectif est de tracer un chemin entre toutes les paires de mêmes nombres sur une grille. Les chemins ne doivent pas se croiser. Les nombres doivent être aux extrémités des chemins (pas en plein milieu). Généralement, on demande que toutes les cases de la grille soient remplies.. La plus ancienne référence à un puzzle de type Numberlink remonte à 1897, dans une publication de Sam Loyd, un concepteur américain de casse-tête mathématiques et logiques. C’est cependant après la publication de ce jeu par l’éditeur Nikoli que ce type de puzzle gagne en popularité. Le problème Numberlink peut se réduire à une résolution du problème SAT. On peut alors utiliser un solveur SAT pour trouver une solution. Une autre approche possible est de chercher un plus court chemin entre l’état de départ (la grille non remplie) et un état final, c’est-à-dire lorsque le puzzle est résolu.