Czy Hidoku NP jest kompletny?

15

Hidoku to siatka n×n z niektórymi wstępnie wypełnionymi liczbami całkowitymi od 1 do n2 . Celem jest znalezienie ścieżki kolejnych liczb całkowitych (od 1 do n2 ) w siatce. Bardziej konkretnie, każda komórka siatki musi zawierać inną liczbę całkowitą od 1 do n2 a każda komórka o wartości zn2 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 n2 , 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ę.zn²z+11,2,3,,n2)

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.

ipsec
źródło
1
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 . v 1 , v n O ( n 3 )1,,n2)v1,vnO(n3))
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.
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:

7

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) ).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 G, a Hidoku ma rozwiązanie wtedy i tylko wtedy, gdy oryginalny wykres siatki ma ścieżkę hamiltonowską.GG

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 ( 1 to pierwsza, 144 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×121144

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×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 N P -Complete.n2NP

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
1
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 do n 2 ) w siatce”? 1n2)
Pål GD
2

n×nΩ(n)nlgn mówiąc, że komórka o współrzędnych ( x i , y i )(xja,yja,wja):xja,yjan,wjan2)(xja,yja)wjalgn+lgn+lgn2)=4lgnO(lgn)Ω(n)o(n)

Ω(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
1
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