Matematyka Sudoku

Automorficzne Sudoku z 24 wskazówkami i symetrią translacyjną

Matematyka Sudoku odnosi się do wykorzystania matematyki do studiowania łamigłówek Sudoku w celu uzyskania odpowiedzi na pytania takie jak „Ile jest wypełnionych siatek Sudoku?” , „ Jaka jest minimalna liczba wskazówek w prawidłowej układance? ” oraz „W jaki sposób siatki Sudoku mogą być symetryczne?” za pomocą kombinatoryki i teorii grup .

Analiza upadków Sudoku jest zasadniczo podzielona na analizę właściwości nierozwiązanych łamigłówek (takich jak minimalna możliwa liczba podanych wskazówek) i analizę właściwości rozwiązanych łamigłówek. Wstępna analiza była w dużej mierze skupiona na wyliczaniu rozwiązań, a wyniki pojawiły się po raz pierwszy w 2004 roku.

W przypadku klasycznego Sudoku liczba wypełnionych siatek wynosi 6 670 903 752 021 072 936 960 ( 6,67 × 10 ²¹ ), co zmniejsza się do 5 472 730 538 zasadniczo różnych rozwiązań w ramach przekształceń zachowujących ważność. Istnieje 26 możliwych typów symetrii , ale można je znaleźć tylko w około 0,005% wszystkich wypełnionych siatek. Zwykła łamigłówka z unikalnym rozwiązaniem musi mieć co najmniej 17 wskazówek, ale nie jest to udowodnione matematycznie. Istnieje układanka do rozwiązania z maksymalnie 21 wskazówkami dla każdej rozwiązanej siatki, przy czym największa dotychczas znaleziona minimalna łamigłówka ma 40 wskazówek w 81 komórkach.

Podobne wyniki znane są dla wariantów i mniejszych siatek. Nie są znane żadne dokładne wyniki dla Sudoku większego niż klasyczna siatka 9 × 9, chociaż istnieją szacunki, które uważa się za dość dokładne.

Puzzle

Minimalna liczba podanych

Zwykłe Sudoku ( właściwe łamigłówki) mają unikalne rozwiązanie. Minimalne Sudoku to Sudoku, z którego nie można usunąć żadnej wskazówki, pozostawiając właściwe Sudoku . Różne minimalne Sudoku mogą mieć różną liczbę wskazówek. W tej sekcji omówiono minimalną liczbę podanych dla odpowiednich łamigłówek.

Zwykłe sudoku

Sudoku z 17 wskazówkami.

Sudoku z 17 wskazówkami i symetrią po przekątnej.

Sudoku z 18 wskazówkami i ortogonalną symetrią.

Automorficzne Sudoku z 24 wskazówkami i pełną geometryczną symetrią .

Sudoku z 19 wskazówkami i dwukierunkową ortogonalną symetrią.

Wiele Sudoku zostało znalezionych z 17 wskazówkami, chociaż znalezienie ich nie jest trywialnym zadaniem. Artykuł Gary'ego McGuire'a, Bastiana Tugemanna i Gillesa Civario, opublikowany 1 stycznia 2012 r., Wyjaśnia, w jaki sposób zostało udowodnione poprzez wyczerpujące wyszukiwanie komputerowe, że minimalna liczba wskazówek w każdym właściwym Sudoku wynosi 17.

Symetryczne sudoku

Uważa się, że najmniej wskazówek w Sudoku z dwukierunkową symetrią ukośną (symetria obrotowa 180 °) wynosi 18, aw co najmniej jednym przypadku takie Sudoku również wykazuje automorfizm . Wiadomo, że istnieje Sudoku z 24 wskazówkami, symetrią dwuścienną (symetria obrotowa 90 °, która obejmuje również symetrię na obu osiach ortogonalnych, symetrię obrotową 180 ° i symetrię ukośną), ale nie wiadomo, czy ta liczba wskazówek jest minimalne dla tej klasy Sudoku.

Sudoku w innych rozmiarach

6×6(2×3) Sudoku: Najmniej wskazówek to 8.
8×8(2×4) Sudoku: Najmniej wskazówek to 14.

Całkowita liczba minimalnych łamigłówek

Liczba minimalnych Sudoku (Sudoku, w których nie można usunąć żadnej wskazówki bez utraty unikalności rozwiązania) nie jest dokładnie znana. Jednak techniki statystyczne w połączeniu z generatorem ( „Bezstronne statystyki CSP – A Controlled-Bias Generator” ) pokazują, że istnieje w przybliżeniu (z błędem względnym 0,065%):

3,10 × 10 ³⁷ różnych minimalnych puzzli,
2,55 × 10 ²⁵ minimalnych łamigłówek, które nie są pseudo-równoważne (tj. ten sam układ, w którym wszystkie wystąpienia jednej cyfry są zamienione na inną cyfrę).

Warianty

Istnieje wiele wariantów Sudoku , częściowo charakteryzujących się rozmiarem ( N ) i kształtem ich regionów . O ile nie zaznaczono inaczej, dyskusja w tym artykule zakłada klasyczne Sudoku, czyli N = 9 (siatka 9×9 i regiony 3×3). Prostokątne Sudoku wykorzystuje prostokątne regiony o wymiarze wiersz-kolumna R × C . Inne warianty obejmują te z regionami o nieregularnych kształtach lub z dodatkowymi ograniczeniami ( hipersześcian ).

Regiony są również nazywane blokami lub pudełkami . Pasmo jest częścią siatki, która zawiera 3 rzędy i 3 ramki, a stos jest częścią siatki, która obejmuje 3 kolumny i 3 ramki . Łamigłówka to częściowo wypełniona siatka , a wartości początkowe to dane lub wskazówki . Właściwa łamigłówka ma unikalne rozwiązanie. Minimalna łamigłówka to właściwa łamigłówka, z której nie można usunąć żadnej wskazówki bez wprowadzenia dodatkowych rozwiązań . Widzieć Słowniczek Sudoku dla innej terminologii.

Rozwiązywanie Sudoku z punktu widzenia gracza zostało omówione w książce Denisa Berthiera „The Hidden Logic of Sudoku” (2007), która uwzględnia strategie takie jak „ukryte łańcuchy xy”.

Kontekst matematyczny

, że ogólny problem rozwiązywania łamigłówek Sudoku na siatkach n ² × n ^{2 złożonych z} n × n bloków jest NP-zupełny .

Zagadkę można wyrazić jako problem z kolorowaniem wykresu . Celem jest skonstruowanie 9-kolorowania określonego wykresu, biorąc pod uwagę częściowe 9-kolorowanie. Wykres Sudoku ma 81 wierzchołków, po jednym na każdą komórkę. Wierzchołki są oznaczone uporządkowanymi parami ( x , y ), gdzie x i y są liczbami całkowitymi od 1 do 9. W tym przypadku dwa różne wierzchołki oznaczone przez ( x , y ) i ( x ′, y ′) są połączone przez krawędź wtedy i tylko wtedy, gdy :

x = x ′ (ta sama kolumna) lub
y = y ′ (ten sam wiersz) lub
⌈ x /3 ⌉ = ⌈ x ′/3 ⌉ i ⌈ y /3 ⌉ = ⌈ y ′/3 ⌉ (ta sama komórka 3×3)

Układanka jest następnie uzupełniana przez przypisanie każdemu wierzchołkowi liczby całkowitej od 1 do 9 w taki sposób, że wierzchołki połączone krawędzią nie mają przypisanej tej samej liczby całkowitej.

Siatka rozwiązania Sudoku jest również kwadratem łacińskim . Jest znacznie mniej siatek Sudoku niż kwadratów łacińskich, ponieważ Sudoku nakłada dodatkowe ograniczenia regionalne.

Sudoku ze stołów grupowych

Podobnie jak w przypadku kwadratów łacińskich , tabliczki (dodawania lub) mnożenia ( tablice Cayleya ) grup skończonych można wykorzystać do konstruowania Sudoku i powiązanych tablic liczb. Mianowicie trzeba wziąć podgrupy i grupy ilorazowe :

$}$ na przykład par, dodając każdy składnik osobno modulo some $n$ . Pomijając jeden ze składników, nagle znajdujemy się w $.$ to odwzorowanie jest oczywiście zgodne z odpowiednimi dodatkami, tj. Jest to homomorfizm grupowy ) Mówi się również, że ta ostatnia jest grupą ilorazową pierwszego, ponieważ niektóre niegdyś różne elementy stają się równe w nowej grupie. Jest to jednak również podgrupa, ponieważ możemy po prostu wypełnić brakujący składnik ${\ Displaystyle 0}$ , aby wrócić do ${\ Displaystyle \ mathbb {Z} _ {n} \ oplus \ mathbb {Z} _{n}}$ .

W tym widoku zapisujemy przykład Siatka 1 dla ${\ displaystyle n = 3}$ .

$wygląda$ tak samo na drugim komponencie (mianowicie jak podgrupa one dodawane niezależnie od pierwszego. Z drugiej strony, pierwsze składniki są równe w każdym bloku, a jeśli wyobrazimy sobie każdy blok jako jedną komórkę, te pierwsze składniki pokazują ten sam wzór (mianowicie grupa ilorazowa ${\ displaystyle \ mathbb {Z} _ {3} }$ ). Jak opisano w artykule o kwadratach łacińskich, jest to kwadrat łaciński $porządku$

Teraz, aby uzyskać Sudoku, przestawmy wiersze (lub równoważnie kolumny) w taki sposób, aby każdy blok był redystrybuowany dokładnie raz w każdym bloku - na przykład uporządkujmy je ${\ Displaystyle 1,4,7,2,5,8,3,6,9}$ . To oczywiście zachowuje właściwość kwadratu łacińskiego. $z$ ma odrębne wpisy za pośrednictwem drugiej składowej, ponieważ drugie składowe bloków pierwotnie tworzyły kwadrat łaciński rzędu ( podgrupy ${\ Displaystyle \ mathbb {Z} _ {3}}$ ). W ten sposób dochodzimy do Sudoku (zmień nazwy par na numery 1...9, jeśli chcesz). Z powyższym przykładem i permutacją wierszy dochodzimy do Grid 2 .

Siatka 1 - tabela dodawania w

{\ Displaystyle \ mathbb {Z} _ {3} \ oplus \ mathbb {Z} _ {3}}

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

Siatka 2 – Generowanie Sudoku

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)
(0,0)	(0,1)	(0,2)

(2,0)	(2,1)	(2,2)
(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)

(0,1)	(0,2)	(0,0)
(1,1)	(1,2)	(1,0)
(2,1)	(2,2)	(2,0)

(1,1)	(1,2)	(1,0)
(2,1)	(2,2)	(2,0)
(0,1)	(0,2)	(0,0)

(2,1)	(2,2)	(2,0)
(0,1)	(0,2)	(0,0)
(1,1)	(1,2)	(1,0)

(0,2)	(0,0)	(0,1)
(1,2)	(1,0)	(1,1)
(2,2)	(2,0)	(2,1)

(1,2)	(1,0)	(1,1)
(2,2)	(2,0)	(2,1)
(0,2)	(0,0)	(0,1)

(2,2)	(2,0)	(2,1)
(0,2)	(0,0)	(0,1)
(1,2)	(1,0)	(1,1)

Aby ta metoda działała, na ogół nie jest potrzebny iloczyn dwóch grup o równej wielkości. Tak zwana krótka dokładna sekwencja skończonych grup o odpowiedniej wielkości już spełnia swoje zadanie. Wypróbuj na przykład grupę z ilorazem i podgrupą ${2}$ ${\ displaystyle \ mathbb {Z}$ } Wydaje się jasne (już z wyliczeń), że nie wszystkie Sudoku można wygenerować w ten sposób.

Sudoku układanki

Sudoku, którego regiony nie są (koniecznie) kwadratowe lub prostokątne, jest znane jako Jigsaw Sudoku. W szczególności kwadrat N × N , w którym N jest liczbą pierwszą, może być wyłożony tylko nieregularnymi N -omino . Dla małych wartości N obliczono liczbę sposobów ułożenia kwadratu (z wyłączeniem symetrii) (sekwencja A172477 w OEIS ). Dla N ≥ 4 niektóre z tych nachyleń nie są kompatybilne z żadnym kwadratem łacińskim; tzn. wszystkie łamigłówki Sudoku na takim kafelku nie mają rozwiązania.

Rozwiązania

Odpowiedź na pytanie „Ile jest siatek Sudoku?” zależy od definicji, kiedy podobne rozwiązania są uważane za różne.

Zwykłe sudoku

Wszystkie rozwiązania

Aby wyliczyć wszystkie możliwe rozwiązania, dwa rozwiązania są uważane za różne, jeśli którakolwiek z odpowiadających im (81) wartości komórek jest różna. Relacje symetrii między podobnymi rozwiązaniami są ignorowane, np. obroty rozwiązania są uważane za różne. Symetrie odgrywają znaczącą rolę w strategii wyliczania, ale nie w liczbie wszystkich możliwych rozwiązań.

Pierwsze znane rozwiązanie do pełnego wyliczenia zostało opublikowane przez QSCGZ (Guenter Stertenbrink) na grupie dyskusyjnej rec.puzzles w 2003 roku, uzyskując 6 670 903 752 021 072 936 960 ( 6,67 × 10 ²¹ ) różnych rozwiązań.

W badaniu z 2005 roku Felgenhauer i Jarvis przeanalizowali permutacje górnego pasma używane w ważnych rozwiązaniach. Po zidentyfikowaniu symetrii Pasma 1 i klas równoważności dla częściowych rozwiązań siatki, skonstruowano uzupełnienia dwóch dolnych pasm i policzono je dla każdej klasy równoważności. Sumowanie uzupełnień po klasach równoważności, ważonych według wielkości klas, daje łączną liczbę rozwiązań jako 6 670 903 752 021 072 936 960, co potwierdza wartość uzyskaną przez QSCGZ. Wartość została następnie wielokrotnie niezależnie potwierdzona. Później opracowano drugą technikę wyliczania opartą na generowaniu pasm, która jest znacznie mniej intensywna obliczeniowo. Ta późniejsza technika wymagała mniej więcej 1/97 liczby cykli obliczeniowych w porównaniu z oryginalnymi technikami, ale była znacznie bardziej skomplikowana w konfiguracji.

Zasadniczo różne rozwiązania

Grupa symetrii sudoku

Dokładną strukturę grupy symetrii sudoku można zwięźle wyrazić za pomocą iloczynu wieńca (≀). Możliwe permutacje wierszy (lub kolumn) tworzą grupę izomorficzną z S ₃ ≀ S ₃ rzędu 3! ⁴ = 1296. Cała grupa przegrupowania jest tworzona przez _{umożliwienie} operacji transpozycji (izomorficznej względem C2 ) działania na dwóch kopiach tej grupy, jednej dla permutacji wierszowych i jednej dla permutacji kolumnowych. _To jest S3 ≀ S3 _{_} ≀ C ₂ , grupa rzędu 1296 ² × 2 = 3 359 232. Wreszcie, operacje ponownego oznakowania dojeżdżają do pracy z operacjami przegrupowania, więc pełna grupa sudoku (VPT) to ( S ₃ ≀ S ₃ ≀ C ₂ ) × S ₉ rzędu 1 218 998 108 160.

Punkty stałe i lemat Burnside'a

Zbiór równoważnych siatek, które można osiągnąć za pomocą tych operacji (z wyłączeniem ponownego etykietowania), tworzy orbitę siatek pod działaniem grupy przegrupowania . Liczba zasadniczo różnych rozwiązań to liczba orbit, którą można obliczyć za pomocą lematu Burnside'a . Punkty stałe Burnside'a to siatki, które albo nie zmieniają się podczas operacji przegrupowania, albo różnią się jedynie zmianą etykiet. Aby uprościć obliczenia, elementy grupy przegrupowań są podzielone na klasy koniugacji , którego wszystkie elementy mają taką samą liczbę punktów stałych. Okazuje się, że tylko 27 z 275 klas koniugacji grupy przegrupowań ma punkty stałe; te klasy koniugacji reprezentują różne typy symetrii (samopodobieństwo lub automorfizm), które można znaleźć w ukończonych siatkach sudoku. Korzystając z tej techniki, Ed Russell i Frazer Jarvis jako pierwsi obliczyli liczbę zasadniczo różnych rozwiązań sudoku jako 5 472 730 538 .

Zobacz też

Eksplozja kombinatoryczna (z podsumowaniem liczby siatek Sudoku w porównaniu z kwadratami łacińskimi)
Linki taneczne
Słowniczek Sudoku
Sudoki
Kod sudoku

Dalsza lektura

Rosenhouse, Jason ; Taalman, Laura (2011). Sudoku na poważnie: matematyka kryjąca się za najpopularniejszą na świecie układanką ołówkową . Oxford University Press.

Linki zewnętrzne

Algorytm mapy różnic V. Elsera również rozwiązuje Sudoku
Sudoku — ćwiczenie z programowania z ograniczeniami i Visual Prolog 7 autorstwa Carstena Kehlera Holsta (w Visual Prolog )
Sudoku Squares and Chromatic Polynomials autorstwa Herzberga i Murty'ego traktuje łamigłówki Sudoku jako problemy z kolorowaniem wierzchołków w teorii grafów .