Czy Hidoku NP jest kompletny?

Hidoku to siatka $n \times n$ z niektórymi wstępnie wypełnionymi liczbami całkowitymi od 1 do $n^2$ . Celem jest znalezienie ścieżki kolejnych liczb całkowitych (od 1 do $n^2$ ) w siatce. Bardziej konkretnie, każda komórka siatki musi zawierać inną liczbę całkowitą od 1 do $n^2$ a każda komórka o wartości $z ≠ n^{2}$ musi mieć sąsiednią komórkę o wartości $z + 1$ (może być również ukośna).

Czy trudno jest zdecydować, czy dane Hidoku jest możliwe do rozwiązania? Jakiej redukcji można użyć?

Edycja: zgodnie z komentarzami podam trochę wyjaśnienia. Podana jest siatka komórek, niektóre z nich już zawierają wartości (liczby całkowite od 1 do n²). Musimy wypełnić wszystkie pozostałe komórki liczbami całkowitymi od 1 do $n^2$ , tak aby żadne dwie komórki nie miały tej samej wartości i aby każda komórka o wartości miała sąsiada o wartości . Oznacza to, że po wypełnieniu komórek musimy znaleźć ścieżkę . W siatce, która logicznie odwiedza każdą komórkę. $z ≠ n²$ $z + 1$ $1, 2, 3,\cdots, n^2$

Przykładem Hidoku może być http://www.janko.at/Raetsel/Hidoku/018.c.gif . Rozwiązanym już Hidoku jest http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , gdzie można zobaczyć ścieżkę, o której mówiłem.

complexity-theory reductions np-hard

— ipsec
źródło

Intuicyjnie, bez zastanowienia, na pierwszy rzut oka wydaje się, że można go rozwiązać w czasie rzeczywistym. Coś jak programowanie dynamiczne na dozwolonych wartościach ( ) i wierzchołkach ( ). Brzmi do rozwiązania w czasie .

1, \dots, n^{2}

$1, \dots, n^2$

v_{1}, \dots v_{n}

$v_1, \dots v_n$

O (n^{3})

$O(n^3)$

— Pål GD

Można to modelować równorzędnie jako wykres, łącząc węzły z krawędziami, jeśli są one następcami w . Następnie szukasz ścieżki Hamiltona. Według ścieżek Hamiltona w grafach siatkowych Itai i in. (1982) ten problem jest NP-zupełny na wykresach siatkowych. Nie od razu pasuje to do twojego problemu, ponieważ pozwalasz na połączenia diagonalne, ale źle to wróży.

N

$\mathbb{N}$

— Raphael

@Raphael nie jest zbudowany wykres DAG?

— Pål GD

Nie rozumiem, jak to jest DAG. O ile rozumiem, dane wejściowe to (niekierowany) wykres siatki (zawierający również ukośne krawędzie), a celem jest znalezienie ścieżki hamiltonowskiej, w której podano położenie niektórych węzłów na ścieżce.

— George

@George Okey, zinterpretowałem pytanie jako znalezienie maksymalnej ścieżki wzrostu wartości w siatce!

— Pål GD

Odpowiedzi:

Myślę, że jest -Complete: jak zauważony przez Raphael, cykl Hamiltona na wykresach siatki z otworami problemu jest NP-zupełny ( Alon Itai, Christos Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Ścieżki w siatce Wykresy SIAM J. Comput.. 11 (4): 676–686 (1982) ). $\sf{NP}$

Biorąc pod uwagę wykres z dziurami, możesz łatwo zbudować równoważną grę Hidoku, w której początkowe ustalone komórki wypełniają wszystkie równe przekątne; puste nieparzyste przekątne tworzą niekierowany wykres, który jest równoważny z oryginalnym wykresem siatki a Hidoku ma rozwiązanie wtedy i tylko wtedy, gdy oryginalny wykres siatki ma ścieżkę hamiltonowską. $G$ $G$

wprowadź opis zdjęcia tutaj

Ryc. 1: wykres siatki z dziurami i odpowiednikiem układanki Hidoku (niebieskie komórki reprezentują początkowe komórki o ustalonym numerze ( to pierwsza, to ostatnia), białe komórki to komórki, które gracz musi wypełnić, fioletowa linia wskazuje sekwencję początkowych ustalonych komórek numerowanych). $12 \times 12$ $1$ $144$

Linie pomocnicze (wypełnione) można dodać do dolnej lub prawej strony, aby uzyskać kwadrat.

Kolejny przykład redukcji z wykresu siatki do układanki Hidoku: wykres siatki 6x4 jest osadzony na większej siatce 13x13; parzyste przekątne są wypełnione stałymi liczbami, a pozostałe wolne komórki są równoważne oryginalnemu wykresowi siatki.

wprowadź opis zdjęcia tutaj

Pełny obraz z transformacją można pobrać tutaj .

Kilka dodatkowych uwag do uzupełnienia odpowiedzi:

problem znany jest również jako Hidato ; plansza może mieć dowolny kształt (ale jako uogólnienie kwadratowej obudowy pozostaje twarda NP);
jak słusznie udowodnił Steven Stadnicki w swojej odpowiedzi, nie jest oczywiste, że problem tkwi w NP, jeśli początkowa częściowo wypełniona siatka nie jest podana jako tablica liczb całkowitych ale jest podana w zwięzłej reprezentacji; jednak wyraźnie widać w NP, czy tablica początkowa jest podana przy użyciu rozsądnej listy reprezentacji liczb całkowitych; $n \times n$
Myślę, że oryginalne zasady gry mówią, że rozwiązanie powinno być unikalne ; więc problem występuje w USA (trudny w USA ) i prawdopodobnie nie będzie w NP.

Podsumowując, jeśli upuść unique rozwiązanie i określić początkową płytę z listą liczb gra jest -Complete. $n^2$ $\sf{NP}$

— Vor
źródło

Czy to nie jest DAG? Czy całkowicie nie zrozumiałem pytania?

— Pål GD

@ PålGD: nie, nie sądzę, że jest to DAG, to nieukierowany wykres siatki z ukośnymi krawędziami. Gra rozpoczyna się od częściowo wypełnionej planszy, a gracz musi zacząć od komórki 1 i osiągnąć ostatni wykonując kroki ortogonalne lub ukośne (ale być może nie pamiętam zbyt dobrze zasad ... teraz sprawdzam)

— Vor

Ale mówi „znajdź ścieżkę kolejnych liczb całkowitych”.

— Pål GD

Być może oznacza to po prostu, że nie może odwiedzić tej samej celi dwa razy i że wszystkie komórki muszą zostać odwiedzone

— Vor

„Celem jest znalezienie ścieżki kolejnych liczb całkowitych (od

) w siatce”?

1

$1$

n^{2}

$n^2$

— Pål GD

$n\times n$ $\Omega(n)$ $n$ $\lg n$ mówiąc, że komórka o współrzędnych $(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)$

(Aby omówić podobne problemy, zobacz moje pytanie o złożoność zwięzłego Nurikabe na stronie cstheory.SE.)

— Steven Stadnicki
źródło

Nieokreślanie wielkości planszy jako jednoznacznej wydaje mi się nierozsądną interpretacją.

— David Eisenstat

@DavidEisenstat Niekoniecznie jest to naturalna interpretacja, ale wydaje mi się, że jest całkowicie poprawna.

— Steven Stadnicki

@StevenStadnicki: Zgadzam się z tobą, zrobiłem podobną notatkę w dowodzie kompletności NP Binary Puzzle, który niedawno opublikowałem na cstheory.stackexchange.com. Chociaż niejednorodna reprezentacja rzeczywiście nie jest tak rozsądna :-). Dodam notatkę do mojej odpowiedzi. Powinienem też rozwiązać problem wyjątkowości rozwiązania; ponieważ uważam, że oryginalne zasady mówią, że rozwiązanie powinno być unikalne.

— Vor