Skuteczne kodowanie łamigłówek sudoku

Określenie dowolnej dowolnej siatki 9x9 wymaga podania pozycji i wartości każdego kwadratu. Naiwne kodowanie tego może dać 81 (x, y, wartość) trypletów, wymagając 4 bitów dla każdego x, y i wartości (1-9 = 9 wartości = 4 bity) w sumie 81x4x3 = 972 bitów. Numerując każdy kwadrat, można zmniejszyć informację o położeniu do 7 bitów, upuszczając nieco bit dla każdego kwadratu i łącznie 891 bitów. Określając z góry ustaloną kolejność, można drastycznie zredukować ją do zaledwie 4 bitów dla każdej wartości, co daje w sumie 324 bity. Jednak w sudoku może brakować liczb. Daje to możliwość zmniejszenia liczby liczb, które należy podać, ale może wymagać dodatkowych bitów do wskazywania pozycji. Używając naszego 11-bitowego kodowania (pozycja, wartość), możemy określić układankę z wskazówkami z$n$$11n$ bitów, np. Minimalna (17) łamigłówka wymaga 187 bitów. Najlepszym kodowaniem, o jakim do tej pory myślałem, jest użycie jednego bitu dla każdego miejsca, aby wskazać, czy jest ono wypełnione, a jeśli tak, to kolejne 4 bity kodują liczbę. Wymaga to bitów, 149 dla minimalnej układanki ( ). Czy istnieje bardziej wydajne kodowanie, najlepiej bez bazy danych każdej prawidłowej konfiguracji sudoku? (Punkty za adresowanie ogólny z logiczne)$81+4n$$n=17$$n$$N \times N$

Właśnie przyszło mi do głowy, że wiele łamigłówek będzie rotacją kolejnej lub będzie miało zwykłą kombinację cyfr. Być może może to pomóc w zmniejszeniu wymaganych bitów.

Według Wikipedii ,

Liczba klasycznych siatek rozwiązań 9 × 9 wynosi 66 690 903 752 021,072,936,960 (sekwencja A107739 w OEIS) lub około .$6.67×10^{21}$

Jeśli poprawnie wykonałem matematykę ( ), uzyskam 73 (72.498) bitów informacji dla tabeli odnośników.$\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$

Ale:

Wykazano, że liczba zasadniczo różnych rozwiązań, biorąc pod uwagę symetrie, takie jak obrót, odbicie, permutacja i znakowanie, wynosi zaledwie 5 472 730 538 [15] (sekwencja A109741 w OEIS).

Daje to 33 (32,35) bitów, więc możliwe jest, że sprytna metoda wskazania, która permutacja może spaść poniżej pełnych 73 bitów.

Czy istnieje bardziej wydajne kodowanie, najlepiej bez bazy danych każdej prawidłowej konfiguracji sudoku?

Tak. Mogę wymyślić kodowanie poprawiające twoje 149-bitowe kodowanie minimalnej układanki w 6 lub 9 bitach, w zależności od warunków. To jest bez bazy danych lub rejestru innych rozwiązań lub częściowych płyt. Oto jest:$9\times 9$

Najpierw używasz bitów do zakodowania liczby m przy minimalnej liczbie wystąpień na planszy. Kolejne 4 bitów kodowania Rzeczywista £ -l od razy m pojawi. Następne 7 ℓ bitów koduje każdą pozycję, w której pojawia się m .$4$$m$$4$$\ell$$m$$7\ell$$m$

Kolejne bitów to flagi wskazujące, czy pozostałe pozycje mają liczbę, czy nie (pomijasz pozycje, w których znajduje się m ). Ilekroć jest jeden z tych bitów , kolejne 3 bity wskazują, która to liczba (w uporządkowanym zbiorze { 1 , … , 9 } bez m ). Na przykład, jeśli m = 4, a 3 bity są , to liczba w odpowiedniej pozycji na planszy jest piątą (licząc od 0) w zestawie { 1 , 2 , 3 $81-\ell$$m$1$\{1,\ldots,9\}$$m$$m=4$101 , więc jest to 6 . Liczby j < m będą kodowane binarnie jako j - 1 , podczas gdy liczby j > m będą kodowane jako j - 2 . Ponieważ już napisaliśmy ℓ pozycji,zostaną dodanetylko 3 ( n - ℓ ) bity, aby zakodować resztę płytki w tym kroku.$\{1,2,3,5,6,7,8,9\}$$6$$j<m$$j-1$$j>m$$j-2$$\ell$$3(n-\ell)$

Zatem całkowita liczba bitów wymagana do zakodowania płytki przy użyciu tej procedury wynosi

Dla zauważamy, że ℓ może wynosić 0 lub 1 (ogólnie ℓ ≤ ⌊ n / 9 ⌋ ). Zatem B może wynosić 140 lub 143 w zależności od tego, czy na planszy nie ma numeru.$n=17$$\ell$$\ell\leq\lfloor n/9\rfloor$$B$

Warto zauważyć, że rozwiązanie Kevina jest znacznie lepsze w ogólnym przypadku. To kodowanie wykorzystuje maksymalnie 149 bitów tylko dla lub dla n = 20, pod warunkiem że ℓ = 0 . Przynajmniej pokazuje ogólny pomysł, jak wykorzystać fakt, że N = 9 jest bardzo zbliżone do 2 ⌊ log 2 N ⌋ (co oznacza, że ​​mamy tendencję do „utraty pamięci” przy użyciu 4 bitów na wartość, ponieważ 4 bity pozwalają nam również wyrazić N = 16 liczb.$n\in\{17,18,19\}$$n=20$$\ell=0$$N=9$$2^{\lfloor\log_2N\rfloor}$$N=16$

Przykład. Rozważ następującą tablicę z wskazówkami.$n=17$

.  .  .   .  .  .   .  1  .
4  .  .   .  .  .   .  .  .
.  2  .   .  .  .   .  .  .

.  .  .   .  5  .   4  .  7
.  .  8   .  .  .   3  .  .
.  .  1   .  9  .   .  .  .

3  .  .   4  .  .   2  .  .
.  5  .   1  .  .   .  .  .
.  .  .   8  .  6   .  .  .

Tutaj żadna liczba nie pojawia się na planszy, a liczby 6, 7 i 9 pojawiają się tylko raz. Przyjmujemy ( ) i ℓ = 1 ( ). Czytając pozycje od lewej do prawej, a następnie od góry do dołu, m pojawia się w pozycji 36 ( ). Zatem nasze kodowanie zaczyna się od .$m=7$0111$\ell=1$0001$m$$36$0100100011100010100100

Następnie potrzebujemy siedmiu 0s, jednego 1i 3-bitowego kodowania liczby , a następnie a i 3-bitowego kodowania 4 itd. ( ). Ostatecznie pomińmy pozycję, w której jest m = 7 , i zakodujemy 8 jako (szósta liczba od 0 na liście 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 ) i 9 jako . Pełne kodowanie wygląda następująco:$1$01$4$0000000100101100$m=7$110${1,2,3,4,5,6,8,9}$111

// m=7, l=1 and its position on the board.
011100010100100
// Numbers 1 and 4 at the beginning. Note that 1 is encoded 000, and 4 is 011.
0000000100001011
// Numbers 2 and 5.
0000000001001000000000001100
// Numbers 4 and 8. We skip the appearance of 7 and encode 8 as 110.
010110001110
// 3, 1 and 9. 9 is encoded as 111.
00010100000100001111
// 3, 4, 2, 5, 1, 8, 6 and the last empty cells.
0000101000101100100100011000100000000000111001101000

Kompletne kodowanie jest 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, a czytelnik może sprawdzić, czy długość tego ciągu jest rzeczywiście 143 :-)