Hidoku NP завершен?

Хидоку - это сетка с некоторыми предварительно заполненными целыми числами от 1 до . Цель состоит в том, чтобы найти путь последовательных целых чисел (от 1 до ) в сетке. Более конкретно, каждая ячейка сетки должна содержать различное целое число от 1 до и каждая ячейка со значением должна иметь соседнюю ячейку со значением (также может быть по диагонали).n 2 n 2 n 2 z ≠ n 2 z + $n \times n$$n^2$$n^2$$n^2$$z ≠ n^{2}$$z + 1$

Трудно ли NP решить, является ли данный Hidoku разрешимым? Какое сокращение можно использовать?

Изменить: согласно комментариям, я даю небольшое разъяснение. Дана сетка ячеек, некоторые из которых уже содержат значения (целые числа от 1 до n²). Мы должны заполнить все оставшиеся ячейки целыми числами от 1 до , чтобы две ячейки не имели одинаковое значение и чтобы каждая ячейка со значением имела соседа со значением . То есть после заполнения ячеек мы должны найти путь . В сетке, которая логически посещает каждую ячейку.$n^2$ z + $z ≠ n²$$z + 1$$1, 2, 3,\cdots, n^2$

Примером хидоку может быть http://www.janko.at/Raetsel/Hidoku/018.c.gif . Уже решенный Hidoku находится на http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , где вы можете увидеть путь, на который я ссылался.

Я думаю, что это -полный: как заметил Рафаэль, гамильтонов цикл на сеточных графах с проблемой дырок является NP-полным ( Алон Итай, Кристос Х. Пападимитриу, Джейм Луис Шварцфитер: Пути Гамильтона в сеточных графах. SIAM J Comput. 11 (4): 676-686 (1982) ).$\sf{NP}$

Таким образом, имея сеточный граф с отверстиями, вы можете легко построить эквивалентную игру Хидоку, где начальные фиксированные ячейки заполняют все четные диагонали; пустые нечетные диагонали образуют неориентированный граф, который эквивалентен исходному графу сетки и Hidoku имеет решение тогда и только тогда, когда исходный граф сетки имеет гамильтонову путь.$G$$G$

Рисунок 1: сетка с отверстиями и эквивалентной головоломкой Хидоку (синие ячейки представляют собой начальные фиксированные пронумерованные ячейки ( - первая, - последняя), белые ячейки - это ячейки, которые игрок должен заполнить, фиолетовый линия указывает последовательность начальных фиксированных пронумерованных ячеек).1 $12 \times 12$$1$$144$

Вспомогательные (заполненные) линии могут быть добавлены к нижней или правой стороне, чтобы сделать его квадратным.

Другой пример перехода от графика сетки к головоломке Хидоку: график сетки 6x4 встроен в большую сетку 13x13; четные диагонали заполнены фиксированными числами, а оставшиеся свободные ячейки эквивалентны исходному графу сетки.

Полную картину с трансформацией можно скачать здесь .

Некоторые дополнительные примечания для завершения ответа:

• проблема также известна как Hidato ; доска может иметь произвольную форму (но, как обобщение квадратного случая, она остается NP-трудной);

• как правильно показал Стивен Стадницкий в своем ответе, не очевидно, что проблема в NP, если начальная частично заполненная сетка не задана как массив целых чисел, а задана в некотором кратком представлении; однако ясно в NP, если начальная доска дана, используя разумный список представления целых чисел;$n \times n$

• Я думаю, что оригинальные правила игры говорят, что решение должно быть уникальным ; так что проблема в США (US-hard) и вряд ли в NP.

Таким образом, если мы отбросим ограничение уникального решения и укажем начальную доску со списком из целых чисел, игра будет -complete.N $n^2$$\sf{NP}$

$n\times n$$\Omega(n)$$n$$\lg n$$(x_i, y_i, w_i): x_i, y_i\leq n, w_i\leq n^2$$(x_i, y_i)$$w_i$$\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$$\Omega(n)$$o(n)$

$\Omega(n)$

(Для обсуждения подобных вопросов, см. Мой вопрос о сложности краткого Nurikabe на сайте cstheory.SE.)