Скрытый путь в квадратных сетках

Я наткнулся на открытую проблему, поставленную Дэвидом Эппштейном, и меня интересует ее сложность. Он предположил, что он NP-завершен.

Ввод: по n матриц 0 и 1, последовательность n 2 0 и 1$n$$n$$n^2$

Вопрос: существует ли путь через соседние элементы матрицы, охватывающий каждую запись матрицы ровно один раз, значения которых соответствуют заданной последовательности?

Кто-нибудь доказывал, что проблема действительно сложная?

В феврале прошлого года я получил электронное письмо от испанского студента Нила Мамано с доказательством того, что эта проблема действительно NP-полная, путем сокращения от гамильтоновой траектории в сеточных графах. Я не знаю, что это было опубликовано где-либо еще. Сокращение заменяет каждую вершину графа сетки блоком 2x2 из 1, а каждый ребро, грань или отсутствующую вершину блоком 2x2 из 0. Входная последовательность чередуется между подпоследовательностями из четырех единиц и четырех нулей столько раз, сколько необходимо для охвата всех вершин, а затем заполняет остальную часть последовательности нулями. Чтобы соответствовать входной последовательности, путь через сетку должен выровнять подпоследовательности четырех 1 с 2x2 блоками 1 из сокращения, образуя гамильтоновый путь; если такой путь существует, то он