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 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 W wersji uogólnionej rozważamy siatkę złożoną z komórek, podzieloną na regionów, każdy rozmiaru Niektóre komórki na starcie wypełnione są liczbami naturalnymi z przedziału od do 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 do dokładnie jeden raz. Podobnie możemy, oczywiście, rozważać problem Uzupełniania Kwadratów Łacińskich dla dowolnego

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ę pierwszego problemu na instancję drugiego problemu, oczywiście z zachowaniem poprawności odpowiedzi (tzn: problem ma rozwiązanie wtedy i tylko wtedy, gdy 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:

Do dzieła!

Redukcja: 3SAT TTP.

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

Problem 3SAT to problem, który jest opisany przez długą koniunkcję klauzul, z których każda jest alternatywą trzech literałów (np. ). 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.

Rys. 5 Przykład T-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 i i przypuśćmy, że oba mają wspólny podgraf Możemy skleić z wzdłuż Zamiast definicji przedstawimy rysunek 1 Potrzebujemy jeszcze specjalnego grafu 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 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 jest grafem trójdzielnym, podobnie jak wszystkie rozważane sklejenia wielu jego kopii. Użytecznymi dla nas podgrafami grafu 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).

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

Rozważmy instancję problemu 3SAT, tj. zbiór klauzul oraz zmiennych gdzie składa się z literałów Wybieramy tak duże, aby co najmniej płatków nie kolidowało ze sobą w grafie Niech teraz kopia grafu reprezentuje zmienną a kopie tego samego grafu reprezentują klauzulę Wszystkie te kopie sklejamy w pewien szczególny sposób. Jeśli to sklejamy znaleziony wolny F-płatek w z F-płatkiem w W przeciwnym przypadku jeśli wtedy sklejamy znaleziony wolny F-płatek w z T-płatkiem w Ponadto złączamy grafy 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 Pokażemy, że istnieje triangulacja grafu wtedy i tylko wtedy, gdy wejściowa formuła jest spełnialna. To, oczywiście, zakończy dowód redukcji.

Przypuśćmy wpierw, że istnieje triangulacja grafu Z poprzednich obserwacji jasno wynika, że każda ze składowych grafów ma triangulację T lub F. Przypuśćmy, że i rozważmy złączenie grafów i 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 wtedy z lematu o płatku niezgodnym nie może jednocześnie być F-triangulowalny oraz T-triangulowalny. Teraz rozważmy złączenie pomiędzy grafami 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 jest F-triangulowalny. Stąd wynika, że jeśli jest triangulowalny, to istnieje wartościowanie które spełnia mianowicie ma wartość prawdziwą wtedy i tylko wtedy, gdy jest T-triangulowalny. W drugą stronę: jeśli jest spełnialna, wtedy dzielimy przez podzielenie względem wartości zmiennej wybierając dla każdej klauzuli takie które jest prawdziwe. Wtedy odpowiedni graf 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.

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