Hidoku NP завершен?

15

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

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

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

Примером хидоку может быть 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 , где вы можете увидеть путь, на который я ссылался.

IPSec
источник
1
Интуитивно, не вдаваясь в долгие размышления, он кажется на первый взгляд многополосным. Что-то вроде динамического программирования для допустимых значений ( ) и вершин ( ). Звучит разрешимо во времени . v 11,,n2v1,vnO(n3)
Пол Г.Д.
Это можно смоделировать аналогично графу, соединяя узлы с ребрами, если они являются преемниками в . Затем вы ищете путь Гамильтона. В соответствии с путями Гамильтона в сеточных графах Itai et al. (1982) эта задача является NP-полной в сеточных графах. Это не сразу подходит к вашей проблеме, так как вы разрешаете диагональные соединения, но это плохо. N
Рафаэль
@ Рафаэль не построил граф DAG?
Пол Г.Д.
Я не понимаю, как это DAG. Насколько я понимаю, входной сигнал представляет собой (неориентированный) сеточный граф (содержащий также диагональные ребра), и цель состоит в том, чтобы найти гамильтонову траекторию, где задано положение некоторых узлов на пути.
Джордж
@ Джордж Окей, я интерпретировал вопрос как поиск максимального пути увеличения значений в сетке!
Пол Г.Д.

Ответы:

7

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

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

введите описание изображения здесь

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

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

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

введите описание изображения здесь

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

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

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

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

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

Таким образом, если мы отбросим ограничение уникального решения и укажем начальную доску со списком из целых чисел, игра будет -complete.N Pn2NP

Вор
источник
Разве это не DAG? Я полностью не понял вопрос?
Пол GD
@ PålGD: нет, я не думаю, что это DAG, это неориентированный граф сетки с диагональными ребрами. Игра начинается с частично заполненной доски, и игрок должен начать с ячейки 1 и дойти до последней, делая ортогональные или диагональные шаги (но, возможно, я не очень хорошо помню правила ... теперь я проверяю это)
Vor
1
Но там написано «найди путь последовательных целых чисел».
Пол GD
Возможно, это просто означает, что он не может посещать одну и ту же камеру дважды, и что все камеры должны быть посещены
Vor
1n2
2

n×nΩ(n)nlgn(xi,yi,wi):xi,yin,win2(xi,yi)wilgn+lgn+lgn2=4lgnO(lgn)Ω(n)o(n)

Ω(n)

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

Стивен Стадницки
источник
1
Не указание размера платы в одинарном формате кажется мне необоснованной интерпретацией.
Дэвид Эйзенстат
@DavidEisenstat Это не обязательно естественная интерпретация, но она кажется мне совершенно правильной.
Стивен Стадницки,
@ StevenStadnicki: Я согласен с вами, я сделал аналогичную заметку в доказательстве NP-полноты Binary Puzzle , которую недавно опубликовал на cstheory.stackexchange.com. Хотя неунарное представление действительно не очень разумно :-). Я добавлю примечание на мой ответ. И я должен решить проблему уникальности решения; потому что я думаю, что оригинальные правила говорят, что решение должно быть уникальным.
Вор