Les puzzles «Flow Free» sont-ils durs?

Question

Un puzzle "Flow Free" se compose d'un entier positif $ n $ et d'un ensemble de paires (non ordonnées) de sommets distincts dans le $ N Times N $ graphique de la grille de telle sorte que chaque sommet se trouve au plus une paire. Une solution à un tel puzzle est un ensemble de chemins Dans le graphique, de sorte que chaque sommet est exactement dans un seul chemin et que l'ensemble des extrémités de chaque chemin est l'une des paires de sommets du puzzle. Cette image est un exemple de puzzle sans flux, et cette image est un exemple d'une solution à un autre puzzle libre de flux.

Le problème "existe-t-il une solution à ce puzzle sans flux?" NP-dur? Est-ce important que $ n $ soit donné en unary ou en binaire?