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