Chemin caché dans les grilles carrées

Je suis tombé sur un problème ouvert posé par David Eppstein et je m'intéresse à son état de complexité. Il a supposé qu'il était NP-complet.

Entrée: matrice par de 0 et 1, séquence de 0 et 1$n$$n$$n^2$

Question: Existe-t-il un chemin à travers les entrées de matrice adjacentes, couvrant chaque entrée de matrice exactement une fois, avec des valeurs correspondant à la séquence donnée?

Quelqu'un a-t-il prouvé que le problème est effectivement difficile?

J'ai reçu un courriel en février dernier d'un étudiant espagnol de premier cycle, Nil Mamano, avec une preuve que ce problème est en effet NP-complet, par réduction du chemin hamiltonien dans les graphiques en grille. Je ne sais pas s'il a été publié nulle part pour le moment. La réduction remplace chaque sommet du graphe par un bloc 2x2 de 1, et chaque arête, face ou sommet manquant par un bloc 2x2 de 0. La séquence d'entrée alterne entre les sous-séquences de quatre 1 et quatre 0 autant de fois que nécessaire pour couvrir tous les sommets, puis remplit le reste de la séquence avec des 0. Pour correspondre à la séquence d'entrée, un chemin à travers la grille doit aligner les sous-séquences de quatre 1 avec les blocs 2x2 de 1 de la réduction, formant un chemin hamiltonien; si un tel chemin existe, il '