Kod sudoku

Kody sudoku to nieliniowe kody korygujące błędy w przód , zgodne z zasadami łamigłówek sudoku zaprojektowanych dla kanału kasowania . W oparciu o ten model nadajnik wysyła sekwencję wszystkich symboli rozwiązanego sudoku. Odbiorca albo odbiera symbol poprawnie, albo symbol kasowania wskazujący, że symbol nie został odebrany. Dekoder otrzymuje macierz z brakującymi wpisami i wykorzystuje ograniczenia łamigłówek sudoku do odtworzenia ograniczonej liczby wymazanych symboli.

Kody Sudoku nie nadają się do praktycznego zastosowania, ale są przedmiotem badań. Pytania takie jak wskaźnik i wydajność błędów są nadal nieznane dla wymiarów ogólnych.

W sudoku można znaleźć brakujące informacje, używając różnych technik w celu odtworzenia całej układanki. Ta metoda może być postrzegana jako dekodowanie zakodowanej wiadomości sudoku, która jest wysyłana kanałem kasowania, w którym niektóre symbole zostały wymazane. Korzystając z reguł sudoku, dekoder może odzyskać brakujące informacje. Sudokus można modelować jako probabilistyczny model graficzny , a zatem można zastosować metody dekodowania kodów kontroli parzystości o niskiej gęstości, takie jak propagacja przekonań .

Wyczyść model kanału

wymazywania

sudoku

z odwzorowaniem z wejścia

{\ displaystyle?}

wyjście kanału z symbolem wymazania i prawdopodobieństwo wymazania

{\ displaystyle p_ {e}}

.

W modelu kanału wymazywania symbol jest przesyłany poprawnie z prawdopodobieństwem $\$ usuwany z prawdopodobieństwem $Rysunek$ fig: Sudoku3x3kanał}). Kanał nie wprowadza błędów, tzn. żadne wejście kanału nie jest zmieniane na inny symbol. Przykład na rysunku \ref {fig: Sudoku3x3BSC} pokazuje transmisję ${\ Displaystyle 3 \ razy 3}$ Kod sudoku. 5 z 9 symboli zostało usuniętych przez kanał. Dekoder wciąż jest w stanie zrekonstruować wiadomość, czyli całą układankę.

Schemat transmisji sudoku w modelu kanału wymazywania

Należy zauważyć, że symbole przesyłane kanałem nie są binarne. W przypadku kanału binarnego symbole (np. liczby całkowite $Model$ odwzorowane na podstawę 2. kanału wymazywania binarnego ma jednak usuwa tylko pojedyncze bity z pewnym prawdopodobieństwem, a nie symbole Sudoku. Jeśli symbole Sudoku są przesyłane w pakietach, kanał można opisać jako kanału kasowania pakietów .

Opis układanki

Sudoku to $na umieszczaniu$ . Jest ona wypełniona w taki sposób, że w każdej kolumnie, wierszu i podsiatce N różnych symboli występuje dokładnie raz. Typowy alfabet to zbiór liczb całkowitych ${\ Displaystyle \ {1, \ ldots, N \}}$ . Rozmiar podsiatek ogranicza rozmiar SUDOKU do ${\ Displaystyle N = n ^ {2}}$ z ${\ Displaystyle n \ w \ operatorname {N}}$ . Każde rozwiązane sudoku i każda jego podsiatka jest kwadratem łacińskim , co oznacza, że każdy symbol występuje dokładnie raz w każdym rzędzie i kolumnie. W punkcie startowym (w tym przypadku po wymazaniu kanału) zagadka jest tylko częściowo ułożona, ale ma tylko jedno unikalne rozwiązanie.

W przypadku kodów kanałów możliwe są również inne odmiany sudoku. Do badań wydajności można użyć regionów ukośnych zamiast kwadratowych podsiatek. Sudoku ukośne ma tę zaletę, że jego rozmiar można wybrać bardziej swobodnie. $na$ strukturę podsiatki normalne sudoku mogą mieć tylko rozmiar n², ukośne sudoku mają prawidłowe rozwiązania dla wszystkich .

Kody Sudoku są nieliniowe. W kodzie liniowym każda liniowa kombinacja słów kodowych daje nowe prawidłowe słowo kodowe, nie dotyczy to kodów sudoku. Symbole sudoku pochodzą ze skończonego alfabetu (np. Liczby całkowite ${\ Displaystyle \ {1, \ ldots, 9 \}} )$ . Ograniczenia kodów Sudoku są nieliniowe: wszystkie symbole w ramach ograniczenia (wiersz, linia, podsiatka) muszą różnić się od innych symboli w ramach tego ograniczenia. Dlatego w kodach Sudoku nie ma całkowicie zerowego słowa kodowego.

Kody Sudoku mogą być reprezentowane przez probabilistyczny model graficzny, w którym przybierają postać kodu sprawdzającego parzystość o niskiej gęstości .

Dekodowanie z propagacją przekonań

Wykres Tannera Sudoku

{\ displaystyle 9 \ razy 9}

.

{\ displaystyle S_ {n}}

oznacza wpisy Sudoku w kolejności skanowania wierszy.

{\ Displaystyle C_ {m}}

oznacza funkcje ograniczeń:

{\ Displaystyle m = 1, \ ldots, 9}

związane z wierszami,

{\ Displaystyle m = 10,\ldkropki ,18}

_

i związane

_

_

Istnieje kilka możliwych metod dekodowania kodów sudoku. Niektóre algorytmy są bardzo specyficznymi rozwinięciami dla kodów Sudoku. algorytmach rozwiązywania sudoku opisano kilka metod . Inną skuteczną metodą jest tańczenie linków .

Szczególnie interesujące są metody dekodowania, takie jak propagacja przekonań, które są również używane w przypadku kodów kontroli parzystości o niskiej gęstości . Analiza wydajności tych metod na kodach sudoku może pomóc lepiej zrozumieć problemy z dekodowaniem kodów kontroli parzystości o niskiej gęstości.

Modelując kody sudoku jako probabilistyczny model graficzny, propagacja przekonań może być wykorzystana do kodów Sudoku. Propagacja przekonań na wykresie Tannera lub wykresie czynników w celu dekodowania kodów Sudoku jest omówiona przez Sayira. i Moon Ta metoda została pierwotnie zaprojektowana dla kodów kontroli parzystości o niskiej gęstości. $Sudoku, ale$ na swoją ogólność propagowanie przekonań działa nie tylko w przypadku klasycznego w przypadku wielu innych. LDPC dekodowanie jest powszechnym przypadkiem użycia do propagowania przekonań, z niewielkimi modyfikacjami to podejście może być użyte do rozwiązywania kodów Sudoku.

Spełnienie ograniczeń za pomocą wykresu Tannera pokazano na rysunku po prawej stronie. ${\ displaystyle S_ {n}}$ oznacza wpisy sudoku w kolejności skanowania wierszy. ${\ Displaystyle C_ {m}}$ oznacza funkcje ograniczeń: ${\ Displaystyle m = 1, ..., 9}$ związane z rzędami, ${\ Displaystyle m = 10, ..., 18}$ związane z kolumnami i $m = 19, ..., 27}$ $z$ podsiatkami Sudoku. ${\ displaystyle C_ {m}}$ jest zdefiniowany jako

${\ Displaystyle C_ {m} (s_ {1}, s_ {2},....., s_ {9}) = {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} s_ {1} ,s_{2},...,s_{9}{\text{są różne}}\\0,&{\text{inaczej.}}\end{przypadki}}}$

każda komórka ${\ Displaystyle S_ {n}}$ jest powiązany z 3 ograniczeniami: wierszem, kolumną i podsiatką. Sayir sugeruje specyfikację ogólnego podejścia do propagowania przekonań: Początkowe prawdopodobieństwo otrzymania symbolu wynosi albo 1 dla obserwowanego symbolu i 0 dla wszystkich innych, albo równomiernie rozmieszczone w całym alfabecie, jeśli symbol zostanie usunięty. W przypadku algorytmu propagacji przekonań wystarczy przekazać tylko podzbiór możliwości zamiast rozkładów, ponieważ rozkład jest zawsze jednorodny w podzbiorze. Kandydaci na wymazane symbole zawężają się do podzbioru alfabetu, ponieważ symbole są wykluczane z powodu ograniczeń. Wszystkie wartości używane przez inną komórkę w ograniczeniu oraz pary, które są wspólne dla dwóch innych komórek itd., są eliminowane. Gracze Sudoku używają tej metody wykluczania logicznego do rozwiązywania większości łamigłówek sudoku.

Kodowanie

Celem kodów z korekcją błędów jest zakodowanie danych w taki sposób, aby były one bardziej odporne na błędy w procesie transmisji. Koder musi odwzorować dane $,$ z której można pobrać słowo kodowe, $np.$ kolejności skanowania wierszy

\ Displaystyle U = 00101 \ ldots {\ stackrel {\ text { Encoder}}{\longrightarrow }}{\begin{array}{|c|c|c|}\hline 1&2&3\\\hline 2&3&1\\\hline 3&1&2\\\hline \end{array}}\Rightarrow X= 1,2,3,1,2,1,3,1,2}

pokazuje niezbędne kroki.

Standardowe sudoku zawiera około $72,5$ bitów informacji, jak obliczono w Informacja po Shannon to stopień losowości w zbiorze danych. Na przykład idealny rzut monetą ma informację: ${\ Displaystyle I = \ log _ {2} 2 = 1}$ fragment. Aby przedstawić wynik 72 rzutów monetą, potrzebne są 72 bity. Jedno Sudoku zawiera mniej więcej te same informacje, co 72 rzuty monetą lub sekwencja 72 bitów. Sekwencja 81 losowych symboli $9$ = $\około 256,8}$ $81 \ log$ bity informacji. Jeden kod Sudoku może być postrzegany jako 72,5 bitów informacji i 184,3 bitów redundancji. Teoretycznie ciąg 72 bitów można odwzorować na jedno sudoku, które jest przesyłane przez kanał jako ciąg 81 symboli. Jednak nie ma funkcji liniowej, która odwzorowuje ciąg znaków na kod sudoku.

Sugerowane przez Sayira podejście do kodowania jest następujące:

Zacznij od pustej siatki
Wykonaj następujące czynności dla wszystkich wpisów po kolei
Użyj propagacji przekonań, aby określić wszystkie prawidłowe symbole wpisu
Jeśli liczność ważnych symboli wynosi k>1, przekształć losowość źródłową w symbol k-ary i użyj go w komórce

Przykład kodowania

Sudoku

informacjami i obliczaniem

Dla sudoku ${\ displaystyle 4 \ razy 4}$ pierwszy wpis można wypełnić źródłem liczności 4. W tym przykładzie jest to a 1. Przez resztę tego wiersza, kolumny i ${\ displaystyle 2 \times 2}$ podsiatka ta liczba jest wyłączona z możliwości dekodera propagacji przekonań. Dla drugiej komórki ważne są tylko liczby 2,3,4. Źródło musi zostać przekształcone w równomierny rozkład między trzema możliwościami i odwzorowane na prawidłowe liczby i tak dalej, aż siatka zostanie wypełniona.

Wydajność kodów sudoku

Obliczenie stawki kodów sudoku nie jest trywialne. $stawki$ przykładowe obliczenie sudoku Wypełniając wiersz po wierszu od lewego górnego rogu, tylko pierwszy wpis zawiera maksymalną informację ${\ displaystyle \ log _ {2} 4 = 2}$ bitów. Każdy następny wpis nie może być żadną z wcześniej użytych liczb, więc informacje ograniczają się do ${\ Displaystyle \ log _ {2} 3}$ , ${\ displaystyle \ log _ {2} 2}$ i ${\ displaystyle 0}$ dla następujących wpisów, ponieważ muszą one dotyczyć pozostałych lewych numerów. W drugich wierszach informacje są dodatkowo zmniejszane przez regułę obszaru: komórka w kolejności skanowania wierszy może być tylko $1}$ 3 $\ displaystyle 3}$ $lub$ $4}$ $displaystyle$ i są już $.$ w podsiatce Ostatni wiersz nie zawiera żadnych informacji. Dodając wszystkie informacje, otrzymujemy ${\ Displaystyle \ log (4 * 3 * 2 ^ {5}) \ około 8,58}$ bitów. Stawka w tym przykładzie wynosi

{\ Displaystyle {\ Frac {4 + 3 + 2*5} {16*4}} \ około 0,27}

.

Dokładna liczba możliwych siatek Sudoku według Matematyki Sudoku to ${\ Displaystyle 6 670 903 752 021 072 936 960}$ . Z całkowitą informacją o

{\ Displaystyle {\ rozpocząć {wyrównane} I_ {log_ {9}} & = \ log _{9}6,67*10^{21}\około 22,87\\I_{log_{2}}&=\log _{2}6,67*10^{21}\około 72,50\,{\text{bity} }\end{wyrównane}}}

średnia stawka standardowego Sudoku wynosi

I_ {9}/9 ^ {2} \ około 0,28

.

Średnia liczba możliwych wpisów dla komórki to ${\ Displaystyle {\ sqrt [{81}] {6,67 * 10 ^ {21}}} \ około 1,86}$ lub ${\ displaystyle \ log _ {2} {1,86} \ około 0,90 \, {\ text {bity}}}$ informacji na komórkę Sudoku. Należy pamiętać, że stawka może się różnić w zależności od słów kodowych.

Udowodniono, że minimalna liczba podanych wpisów, które dają unikalne rozwiązanie, wynosi 17. W najgorszym przypadku tylko cztery brakujące wpisy mogą prowadzić do niejednoznacznych rozwiązań. W przypadku kanału wymazywania jest bardzo mało prawdopodobne, aby 17 udanych transmisji wystarczyło do odtworzenia układanki. Istnieje tylko około 50 000 znanych rozwiązań z 17 podanymi wpisami.

Ewolucja gęstości

Ewolucja gęstości to algorytm analizy pojemności, pierwotnie opracowany dla kodów kontroli parzystości o niskiej gęstości w dekodowaniu propagacji przekonań. Ewolucję gęstości można również zastosować do ograniczeń typu Sudoku. Jednym z ważnych uproszczeń zastosowanych w ewolucji gęstości kodów LDPC jest wystarczająca analiza tylko jednego słowa kodowego. Jednak z ograniczeniami Sudoku nie jest to poprawne słowo kodowe. W przeciwieństwie do kodów liniowych właściwość równoważności wagi i odległości nie obowiązuje dla kodów nieliniowych. W związku z tym konieczne jest obliczenie rekurencji ewolucji gęstości dla każdej możliwej łamigłówki Sudoku, aby uzyskać precyzyjną analizę wydajności.

Proponowanym uproszczeniem jest analiza rozkładu prawdopodobieństwa liczności komunikatów zamiast rozkładu prawdopodobieństwa komunikatu. Ewolucja gęstości jest obliczana na węzłach wejściowych i węzłach ograniczających (porównaj wykres Tannera powyżej). W węzłach wejściowych analizuje się liczności ograniczeń. Jeśli na przykład ograniczenia mają liczności, $wpis$ mieć tylko Jeśli ograniczenia mają liczności ${\ Displaystyle (2,2)}$ wtedy oba ograniczenia dopuszczają dwa różne symbole. Dla obu ograniczeń na pewno zawarty jest poprawny symbol, załóżmy, że poprawnym symbolem jest ${\ displaystyle 1}$ . Drugi symbol może być taki sam lub różny dla ograniczeń. Jeśli symbole są różne, określany jest właściwy symbol. Jeśli drugi symbol jest równy, załóżmy, że $}}$ wyjściowe mają liczność, tj. Symbole $} {\ Displaystyle \ lewo \$ ${ 1,2 \$ . W zależności od rozmiaru alfabetu ( $prawdopodobieństwo$ unikalnego wyniku dla liczebności wejściowych wynosi ${\ Displaystyle (2,2)}$

{\ Displaystyle {\ rozpocząć {wyrównane} p_ {1} ^ {(2,2)} = 1 - {\ Frac {1} {q-1}} \end{wyrównane}}}

i dla wyjścia liczności 2

{\ Displaystyle {\ rozpocząć {wyrównane} p_ {2} ^ {(2,2)} = {\ Frac {1} {q-1}}. \ koniec {wyrównane}}}

$}$ standardowego Sudoku daje to prawdopodobieństwo unikalnego rozwiązania wynoszące $displaystyle$ Obliczenia analogowe są wykonywane dla wszystkich kombinacji liczności. Na koniec z wyników sumuje się rozkład liczności wyjściowych. Zauważ, że kolejność liczności wejściowej jest wymienna. Obliczenie niemalejących kombinacji ograniczeń jest przy tym wystarczające.

$W przypadku węzłów ograniczeń$ nieco podobna i opisana w poniższym przykładzie opartym na standardowym Sudoku Wejścia do węzłów ograniczeń są możliwymi symbolami połączonych węzłów wejściowych. Liczność 1 oznacza, że symbol węzła źródłowego jest już określony. Ponownie analiza niemalejąca jest wystarczająca. Załóżmy, że prawdziwa wartość wyjściowa to 4, a dane wejściowe mają liczności ${\ Displaystyle (1,1,2)}$ z prawdziwymi symbolami 1-2-3. Wiadomości o liczności 1 to i ${\ displaystyle \ lewo \ {1 \ prawo \}}$ i ${\ displaystyle \ lewo \ {2 \ prawo \}}$ . Przesłaniem o liczności 2 może być ${\ Displaystyle \ lewo \ {1,3 \ prawo \}}$ , ${\ Displaystyle \ lewo \ {2,3 \ prawo \}}$ lub ${\ Displaystyle \ lewo \ {3,4 \ prawo \}}$ ponieważ prawdziwy symbol 3 musi być zawarty. W dwóch z trzech przypadków wynikiem jest poprawny symbol 4 z licznością 1: ${\ Displaystyle \ lewo \ {1 \ prawo \}}$ , { $\ Displaystyle \ lewo \ {2 \ prawo \}}$ ${\ Displaystyle \ lewo \ {1,3 \ prawo \}}$ i ${\ Displaystyle \ lewo \ {1 \ prawo \}}$ , ${\ Displaystyle \ lewo \ {2 \ prawo\}}$ , ${\ Displaystyle \ lewo \ {2,3 \ prawo \}}$ . W jednym z trzech przypadków liczność wyjściowa wynosi 2: ${\ Displaystyle \ lewo \ {1 \ prawo \}}$ , ${\ Displaystyle \ lewo \ {2 \ prawo \}}$ , ${\ Displaystyle \ lewo \ {3,4 \ prawo \}}$ . Symbole wyjściowe w tym przypadku to ${\ Displaystyle \ lewo \ {3,4 \ prawo \}}$ . Ostateczny rozkład mocy wyjściowej można wyrazić, sumując wszystkie możliwe kombinacje danych wejściowych. W przypadku $.$ nie

Jeśli liczność jest zbieżna do 1, dekodowanie jest wolne od błędów. Aby znaleźć próg, należy zwiększyć prawdopodobieństwo wymazania, aż błąd dekodowania pozostanie dodatni dla dowolnej liczby iteracji. Dzięki metodzie ewolucji gęstości Sayira rekurencje mogą być używane do obliczania progów również dla kodów Sudoku do rozmiaru alfabetu ${\ displaystyle q = 8}$ .

Zobacz też

Sudoku — główny artykuł Sudoku
Algorytmy rozwiązywania sudoku

^ ^a ^b ^c ^d ^e ^f ^g Sayir, Jossy; Atkins, Caroline (16 lipca 2014). „Ewolucja gęstości dla kodów SUDOKU na kanale wymazywania” . Turbo Codes and Iterative Information Processing (ISTC), 8. Międzynarodowe Sympozjum nt . . ar Xiv : 1407.4328 . Bibcode : 2014arXiv1407.4328A .
^ ^{ab Sayir,}^Jossy (21 października 2014). „Kody SUDOKU, klasa nieliniowych, iteracyjnie dekodowalnych kodów” (PDF) . Źródło 20 grudnia 2015 r .
^ ^a ^b Khan, Sheehan; Jabbari, Szahab; Jabbari, Shahin; Ghanbarinejad, Majid. „Rozwiązywanie sudoku przy użyciu probabilistycznych modeli graficznych” (PDF) . Źródło 20 grudnia 2015 r .
^ ^abc ^Księżyc ^, TK; Gunther, JH (2006-07-01). Spełnianie wielu ograniczeń przez propagację przekonań: przykład z użyciem Sudoku . 2006 IEEE Mountain Workshop na temat systemów adaptacyjnych i uczących się . s. 122–126. doi : 10.1109/SMCALS.2006.250702 . ISBN 978-1-4244-0166-6 .
^ ^a ^b Sayir, J .; Sarwar, J. (2015-06-01). Badanie nieliniowych kodów inspirowanych sudoku z lokalnymi ograniczeniami . 2015 Międzynarodowe Sympozjum IEEE na temat teorii informacji (ISIT) . s. 1921–1925. ar Xiv : 1504.03946 . doi : 10.1109/ISIT.2015.7282790 . ISBN 978-1-4673-7704-1 .
Bibliografia _ Tugemann, Bastian; Civario, Gilles (2012-01-01). „Nie ma Sudoku z 16 wskazówkami: rozwiązanie problemu Sudoku z minimalną liczbą wskazówek” . arXiv : 1201,0749 [ cs.DS ].
^ „Minimalne Sudoku” . staffhome.ecm.uwa.edu.au . Źródło 2015-12-20 .
^ Chung, Sae-Young; Richardson, TJ; Urbanke, RL (2001-02-01). „Analiza dekodowania iloczynu sumy kodów kontroli parzystości o niskiej gęstości przy użyciu przybliżenia Gaussa”. Transakcje IEEE dotyczące teorii informacji . 47 (2): 657–670. CiteSeerX 10.1.1.106.7729 . doi : 10.1109/18.910580 . ISSN 0018-9448 .

[:0-1] ^ ^a ^b ^c ^d ^e ^f ^g Sayir, Jossy; Atkins, Caroline (16 lipca 2014). „Ewolucja gęstości dla kodów SUDOKU na kanale wymazywania” . Turbo Codes and Iterative Information Processing (ISTC), 8. Międzynarodowe Sympozjum nt . . ar Xiv : 1407.4328 . Bibcode : 2014arXiv1407.4328A .

[:1-2] {ab Sayir,}^Jossy (21 października 2014). „Kody SUDOKU, klasa nieliniowych, iteracyjnie dekodowalnych kodów” (PDF) . Źródło 20 grudnia 2015 r .

[:2-3] Khan, Sheehan; Jabbari, Szahab; Jabbari, Shahin; Ghanbarinejad, Majid. „Rozwiązywanie sudoku przy użyciu probabilistycznych modeli graficznych” (PDF) . Źródło 20 grudnia 2015 r .

[:3-4] Księżyc ^, TK; Gunther, JH (2006-07-01). Spełnianie wielu ograniczeń przez propagację przekonań: przykład z użyciem Sudoku . 2006 IEEE Mountain Workshop na temat systemów adaptacyjnych i uczących się . s. 122–126. doi : 10.1109/SMCALS.2006.250702 . ISBN 978-1-4244-0166-6 .

[:4-5] Sayir, J .; Sarwar, J. (2015-06-01). Badanie nieliniowych kodów inspirowanych sudoku z lokalnymi ograniczeniami . 2015 Międzynarodowe Sympozjum IEEE na temat teorii informacji (ISIT) . s. 1921–1925. ar Xiv : 1504.03946 . doi : 10.1109/ISIT.2015.7282790 . ISBN 978-1-4673-7704-1 .

[6] Bibliografia _ Tugemann, Bastian; Civario, Gilles (2012-01-01). „Nie ma Sudoku z 16 wskazówkami: rozwiązanie problemu Sudoku z minimalną liczbą wskazówek” . arXiv : 1201,0749 [ cs.DS ].

[7] „Minimalne Sudoku” . staffhome.ecm.uwa.edu.au . Źródło 2015-12-20 .

[8] Chung, Sae-Young; Richardson, TJ; Urbanke, RL (2001-02-01). „Analiza dekodowania iloczynu sumy kodów kontroli parzystości o niskiej gęstości przy użyciu przybliżenia Gaussa”. Transakcje IEEE dotyczące teorii informacji . 47 (2): 657–670. CiteSeerX 10.1.1.106.7729 . doi : 10.1109/18.910580 . ISSN 0018-9448 .