Przeskocz do treści

Delta mi!

Loading

Dlaczego niektóre łamigłówki są tak trudne?

Łukasz Grządko

o artykule ...

  • Publikacja w Delcie: wrzesień 2017
  • Publikacja elektroniczna: 1 września 2017
  • Autor: Łukasz Grządko
    Afiliacja: pracownik firmy Nokia
  • Wersja do druku [application/pdf]: (397 KB)

Inspiracją do napisania tego artykułu jest znana, popularna i - do czego chcę Czytelnika przekonać - całkiem niełatwa łamigłówka zwana Sudoku. Problem polega na uzupełnieniu częściowo wypełnionej planszy 9 × 9 w taki sposób, żeby każdy wiersz i każda kolumna oraz każdy z 9 tzw. regionów |3× 3 zawierał wszystkie cyfry od 1 do 9. Czy nie przypomina to pewnego innego równie znanego problemu natury kombinatorycznej? Tak, to problem Uzupełniania Kwadratów Łacińskich, których wynalazcą był Leonhard Euler. Być może zainspirował innych, by w przyszłości stworzyli Sudoku...

obrazek

Zasady Uzupełniania (częściowo wypełnionych) Kwadratów Łacińskich są niemal identyczne jak w Sudoku, z tą drobną różnicą, że pomijamy wymaganie dotyczące regionów 3 ×3. Gwoli uzupełnienia rysu historycznego dodajmy, że Sudoku zostało wymyślone przez Howarda Garnsa. Po raz pierwszy zostało opublikowane w 1979 r. przez magazyn Dell Magazines, a siedem lat później dotarło w końcu do Japonii, gdzie zdobyło dużą popularność, jak i swoje prawdziwe imię. Nazwa bowiem wzięła się z japońskiego wyrażenia "Suji wa dokushin ni kagiru", co dosłownie znaczy "Liczby muszą być pojedyncze".

W wersji popularnej, w kontekście Sudoku, zawsze myślimy o planszy |9× 9. W wersji uogólnionej rozważamy siatkę złożoną z  2 2 n × n komórek, podzieloną na n ×n regionów, każdy rozmiaru |n× n. Niektóre komórki na starcie wypełnione są liczbami naturalnymi z przedziału od |1 do | 2 n . Celem jest wypełnienie pozostałych komórek tak, żeby każdy wiersz, każda kolumna oraz każdy region zawierał każdą z liczb z przedziału od |1 do |n2 dokładnie jeden raz. Podobnie możemy, oczywiście, rozważać problem Uzupełniania Kwadratów Łacińskich dla dowolnego | n.

Okazuje się, że zarówno Uzupełnianie Kwadratów Łacińskich, jak i gra Sudoku są problemami NP-zupełnymi, a więc wierzymy, że bardzo trudnymi obliczeniowo. Pozostała część artykułu to właśnie próba naszkicowania, jak w ogóle można takie fakty dowodzić.

Otóż, aby udowodnić, że jakiś problem jest NP-zupełny, wystarczy wziąć dowolny problem, o którym już wiemy, że jest NP-zupełny i pokazać, że daje się go zredukować do naszego problemu. (Gwoli ścisłości w ten sposób tak naprawdę pokazujemy, że ten problem jest co najmniej tak trudny jak inne problemy NP-zupełne. Należałoby jeszcze uzasadnić, że nie jest trudniejszy, co jest zwykle bardzo łatwe. Tutaj również, ale to pomijamy.) Zredukować, tzn. pokazać efektywną (wielomianową) konstrukcję, która przerabia dowolną instancję I1 pierwszego problemu na instancję |I2 drugiego problemu, oczywiście z zachowaniem poprawności odpowiedzi (tzn: problem I1 ma rozwiązanie wtedy i tylko wtedy, gdy I2 ma rozwiązanie). Dokładnie tę metodę zaprezentujemy za chwilę. Na start weźmiemy problem 3SAT, o którym wiadomo, że jest NP-zupełny, a następnie naszkicujemy ciąg redukcji:

3SAT TTP Uzupe łnianie Kwadrat ów Łacińskich Sudoku.

Do dzieła!

Redukcja: 3SAT | TTP.

obrazek

Rys. 1 Przykład sklejania dwóch grafów wzdłuż grafu H.

Rys. 1 Przykład sklejania dwóch grafów wzdłuż grafu H.

Problem 3SAT to problem, który jest opisany przez długą koniunkcję klauzul, z których każda jest alternatywą trzech literałów (np. |(x2∨ ¬x4 ∨¬ x5)∧ (x1∨ x2∨ x3)∧ (¬ x1∨ ¬x3∨ x5ϰ) ). Pytamy, oczywiście, o spełnialność wejściowej formuły. Natomiast problem TTP (Triangulate Tripartite Problem) to problem triangulacji grafów trójdzielnych. Zanim przejdziemy do właściwej redukcji, potrzebujemy szeregu definicji.

obrazek

Rys. 5 Przykład T-płatka.

Rys. 5 Przykład T-płatka.

obrazek

Rys. 6 Przykład F-płatka.

Rys. 6 Przykład F-płatka.

Graf trójdzielny to taki, którego wierzchołki można podzielić na trzy grupy w taki sposób, aby żadna krawędź nie łączyła wierzchołków z tej samej grupy. Triangulacja grafu to jego podział na rozłączne krawędziowo trójkąty. Rozważmy teraz dwa grafy G | 1 i G 2 i przypuśćmy, że oba mają wspólny podgraf H. Możemy skleić |G1 z G2 | wzdłuż |H. Zamiast definicji przedstawimy rysunek 1 Potrzebujemy jeszcze specjalnego grafu H3,n, który pokazany jest na rysunku 2, a który nie jest niczym innym jak tylko trójwymiarowym torusem zbudowanym z trójkątnej siatki.

Ten graf ma kilka interesujących własności. Przede wszystkim istnieją tylko dwie różne (dlaczego?) triangulacje grafu H3,n, obie zilustrowane są na rysunkach 3 i 4. Tę triangulację, w której używamy trójkątów z czubkiem do góry, nazywamy T-triangulacją, a tę drugą - F-triangulacją. Pierwsza będzie odpowiadała wartości logicznej "prawda", druga - "fałsz". Graf H 3,n jest grafem trójdzielnym, podobnie jak wszystkie rozważane sklejenia wielu jego kopii. Użytecznymi dla nas podgrafami grafu H3,n będą jeszcze F-płatek oraz T-płatek, zilustrowane na rysunkach 5 i 6.

Potrzebujemy jeszcze trzech lematów (ścisłe dowody pomijamy, ale pomocne będą rysunkach 7-12).

Lemat (o płatkach zgodnych). Przypuśćmy, że mamy dwa grafy H3,n sklejone F-płatkiem. Załóżmy, że znaleźliśmy triangulację wyniku tej operacji. Jest to możliwe wyłącznie wtedy, gdy albo oba grafy mają T-triangulację, albo jeden z nich ma T-triangulację, a drugi F-triangulację.

Lemat (o płatkach niezgodnych). Tym razem przypuśćmy, że mamy dwa grafy H3,n połączone przez sklejenie T-płatka pierwszego grafu z F-płatkiem drugiego grafu i znów całość została striangulowana. Jest to możliwe wyłącznie wtedy, gdy oba grafy mają każdą z trzech możliwych par konfiguracji triangulacji oprócz takiej, że pierwszy ma F-triangulację, a drugi T-triangulację.

Lemat (o wycięciu trójkąta). Przypuśćmy, że k grafów H 3,n jest sklejonych wzdłuż T-płatka oraz usuwamy środkowy trójkąt typu F z części wspólnej tych grafów. Jest to możliwe wyłącznie wtedy, gdy dokładnie jeden graf ma F-triangulację, a pozostałe mają T-triangulację.

Jesteśmy wreszcie gotowi na właściwą redukcję.

Rozważmy instancję problemu 3SAT, tj. zbiór klauzul |C oraz |s zmiennych |u1,u2,...,us, gdzie |Ci składa się z literałów |li,1,li,2,li,3. Wybieramy |n tak duże, aby co najmniej 3r płatków nie kolidowało ze sobą w grafie |H3,n. Niech teraz kopia |Ui grafu H3,n | reprezentuje zmienną u , i a kopie |C tego samego grafu reprezentują klauzulę |Ci. Wszystkie te kopie sklejamy w pewien szczególny sposób. Jeśli |li, j = uk, to sklejamy znaleziony wolny F-płatek w Ci,j z F-płatkiem w Uk. W przeciwnym przypadku jeśli li,j | = ¬ uk, wtedy sklejamy znaleziony wolny F-płatek w Ci,j z T-płatkiem w Uk. | Ponadto złączamy grafy |Ci,1, wzdłuż dowolnego wolnego F-płatka w każdym z grafów i usuwamy krawędzie centralnego trójkąta typu F. Efekt naszych działań oznaczmy jako |G3. Pokażemy, że istnieje triangulacja grafu G3 | wtedy i tylko wtedy, gdy wejściowa formuła C | jest spełnialna. To, oczywiście, zakończy dowód redukcji.

Przypuśćmy wpierw, że istnieje triangulacja grafu G3. | Z poprzednich obserwacji jasno wynika, że każda ze składowych grafów ma triangulację T lub F. Przypuśćmy, że l | = u i, j k i rozważmy złączenie grafów |Ci,j i Uk.| Twierdzimy, że krawędzie w sąsiedztwie złączenia mogą być triangulowane wtedy i tylko wtedy, gdy co najmniej jeden z grafów jest T-triangulowalny. Wynika to jednak wprost z lematu o płatku zgodnym. Podobnie jeśli l | = ¬u , i, j k wtedy z lematu o płatku niezgodnym nie może jednocześnie Ci,j być F-triangulowalny oraz Uk | T-triangulowalny. Teraz rozważmy złączenie pomiędzy grafami Ci,1, | Na podstawie lematu o wycięciu trójkąta wnioskujemy, że zbiór krawędzi w sąsiedztwie złączenia jest triangulowalny wtedy i tylko wtedy, gdy dokładnie jeden z grafów |Ci,1, jest F-triangulowalny. Stąd wynika, że jeśli G3 jest triangulowalny, to istnieje wartościowanie |u1,u2,...,us, które spełnia |C, mianowicie uk | ma wartość prawdziwą wtedy i tylko wtedy, gdy |U jest T-triangulowalny. W drugą stronę: jeśli C jest spełnialna, wtedy dzielimy G3 przez podzielenie Uk | względem wartości zmiennej |uk, wybierając dla każdej klauzuli takie li, j, które jest prawdziwe. Wtedy odpowiedni graf Ci,j dzielimy według F-triangulacji, a pozostałe dwa są T-triangulowalne.

Konkretny przykład tej (przyznajmy, dość zawiłej) redukcji znajduje się na tylnej okładce. Pozostałe redukcje tylko zarysujemy.

Redukcja: TTP | Uzupełnianie Kwadratów Łacińskich

Formalny opis redukcji i dowód (niestety, dość skomplikowany technicznie - potrzeba twierdzenia Halla o małżeństwach i algorytmu Hopcrofta-Karpa szukania maksymalnych skojarzeń w grafach dwudzielnych) Czytelnik Zainteresowany Szczegółami znajdzie w [1]. My pokażemy tylko poniższy przykład.

obrazek

Mam nadzieję, że widać, jak rozwiązanie zagadki z prawej strony przekłada się na rozwiązanie zagadki z lewej strony: jeśli liczbę S | wpiszemy do pustego miejsca w wierszu R w kolumnie C w zagadce prawej, to interpretujemy to jako zaznaczenie trójkąta o wierzchołkach: R | z lewej, C na górze i S z prawej, w zagadce lewej.

Redukcja: Uzupełnianie Kwadratów Łacińskich | Sudoku

Ponownie ograniczymy się do przykładu. Tym razem nie z powodu trudności technicznych, tylko dokładnie odwrotnie - wierzymy, że przykład wyjaśni wszystko. Wszystkie liczby są podane w systemie trójkowym, gdyż powinno to ułatwić zrozumienie redukcji. Problem Kwadratu jest tak "przerobiony", aby wymusić własność, że w rozwiązaniu Sudoku wszystkie nowo wpisane liczby mają zero na pozycji jedności. Bardziej znacząca cyfra bezpośrednio koduje liczbę z Kwadratu.

obrazek

Do czytania
[1]
Charles Colbourn, The Complexity of Completing Partial Latin Squares, Discrete Applied Mathematics 8 (1984).

Posłowie

Z natury rzeczy w tekście powyżej musiały się znaleźć pewne uproszczenia. Przede wszystkim, warto podkreślić, że samo pojęcie NP-zupełności nie może dotyczyć ani pojedynczego problemu, ani skończonej klasy problemów. Problemy NP-zupełne dotyczą zawsze pewnego nieskończonego ciągu problemów, które zwykle są coraz większe (stąd zresztą w tekście mowa o uogólnionym Sudoku czy o uogólnionym problemie Uzupełniania Kwadratów Łacińskich). Oznacza to, że powyższy szkic wcale nie tłumaczy wprost, dlaczego akurat łamigłówka Sudoku rozmiaru 9 9 jest trudna. Tak naprawdę możemy tylko powiedzieć, że łamigłówki Sudoku  2 2 n n asymptotycznie bardzo trudne (o ile, oczywiście, P |P x N ). Niemniej pozwala to przypuszczać, że również początkowe łamigłówki całego ciągu są trudne.

T. K.