Os quebra-cabeças “Flow Free” são difíceis de usar?

Um quebra-cabeça "Flow Free" consiste em um número inteiro positivo e um conjunto de pares (não ordenados) de vértices distintos no gráfico da grade modo que cada vértice esteja no máximo em um par. Uma solução para esse quebra-cabeça é um conjunto de caminhos não direcionados no gráfico, de modo que cada vértice esteja exatamente em um caminho e o conjunto de extremidades de cada caminho seja um dos pares de vértices do quebra-cabeça. Esta imagem é um exemplo de quebra-cabeça Flow Free e esta imagem é um exemplo de solução para um quebra-cabeça Flow Free diferente.$n$$n \times n$

O problema "Existe uma solução para esse quebra-cabeça do Flow Free?" NP-difícil? Importa se é dado em unário ou binário?$n$

Na terminologia do Nikoli Puzzles, isso é conhecido como "Nanbarinku" ou "Numberlink". A descrição nem sempre menciona explicitamente que todos os quadrados devem ser cobertos, mas esse é realmente o caso em todas as soluções que verifiquei.

Segundo a Wikipedia Numberlink, o problema é NP completo, com referência: Kotsuma, Kouichi; Takenaga, Yasuhiko (março de 2010), NP-Completeness and Enumeration of Number Link Puzzle, relatório técnico do IEICE. Fundamentos teóricos da computação 109 (465): 1–7

Não verifiquei as letras miúdas.

Adicionado. Após um comentário da domotorp , o Numberlink geralmente possui uma restrição adicional. De fato, citando Adcock et al:

Nosso resultado de dureza pode ser comparado a duas provas anteriores de dureza NP: a prova de Lynch de 1975 sem a restrição "cobrir todos os vértices" e a prova de Kotsuma e Takenaga de 2010, quando os caminhos são restritos para ter o menor número possível de curvas em sua classe de homotopia.

Adcock et al. Zig-Zag Numberlink é NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi: 10.2197 / ipsjjip.23.239