Jaka jest minimalna liczba bitów wymagana do przechowywania układanki sudoku?

Uwaga: chodzi o standardową łamigłówkę sudoku 9x9. Rozwiązanie musi obsługiwać tylko rozwiązane, legalne zagadki . Dlatego rozwiązanie nie musi obsługiwać pustych komórek i może polegać na właściwościach rozwiązanej łamigłówki sudoku.

Zastanawiałem się nad tym, ale nie mogłem wymyślić odpowiedzi, z której byłbym zadowolony. Naiwne rozwiązanie wykorzystywałoby jeden bajt na każdą komórkę (81 komórek), w sumie 648 bitów. Bardziej wyrafinowane rozwiązanie przechowałoby całą łamigłówkę sudoku w liczbie podstawowej 9 (jedna cyfra na komórkę) i wymagałoby bitów.$\lceil\log_2(9^{81}))\rceil = 257$

Ale nadal można go poprawić, na przykład, jeśli znasz 8 z 9 liczb w podsiatce 3x3, możesz w prosty sposób wydedukować 9. Możesz kontynuować te myśli do tego stopnia, że ​​pytanie sprowadza się do: Ile jest unikalnych rozwiązanych sudokusów? Teraz możesz użyć ogromnej tabeli odnośników, która odwzorowuje każdą liczbę binarną na łamigłówkę sudoku, ale nie byłoby to użytecznym rozwiązaniem.

Więc moje pytanie:

Jaka jest minimalna ilość bitów potrzebna do przechowywania układanki sudoku i bez algorytmu?

Wzdłuż tych samych wierszy, co odpowiedź maniaka zapadkowego, jeśli wypełnisz komórki bez gwiazdek w poniższej macierzy, pole 3x3 na raz, zawsze wybierając kolejne pole do wypełnienia, aby było tym, które dzieli wiersze lub kolumny z polem, które ty już wypełniono, otrzymujesz następujący wzór dla liczby wyborów na krok (najpierw wypełniając górne środkowe pole, następnie prawe górne pole itp.).

W każdym polu 3x3 po pierwszym, po wypełnieniu jednego wiersza lub kolumny pola, trzy z pozostałych sześciu cyfr są zlokalizowane w jednym rzędzie. Najpierw wybierz ich lokalizacje, a następnie wypełnij pozostałe trzy komórki. (Tak więc rzeczywista kolejność wypełniania komórek może się różnić w zależności od tego, co już wiesz, ale liczba opcji nigdy nie jest większa niż to, co pokazałem).

Po wypełnieniu tych komórek wszystkie gwiazdy są określone.

* * * 9 8 7 6 5 4
* * * 6 5 4 3 3 2
* * * 3 2 1 3 2 1

6 5 4 * * * 6 3 3
3 3 2 * * * 5 3 2
3 2 1 * * * 4 2 1

6 3 3 6 5 4 * * *
5 3 2 3 3 2 * * *
4 2 1 3 2 1 * * *

Jeśli poprawnie obliczyłem, daje to 87 bitów. Według komentarza Petera Shora w ostatnim bloku 3x3 można zaoszczędzić kilka dodatkowych: każda wartość jest zlokalizowana w jednej z czterech komórek, a każdy wiersz zawiera co najmniej jedną komórkę z tylko czterema możliwymi wartościami, więc na pewno czynniki w tym blok powinien zaczynać się od 4, a nie 6, ale nie rozumiem pozostałych czynników w odpowiedzi Shora.

kontynuując z odpowiedzią @ peter, oto lista najgorszych przypadków dla każdej komórki, gdy wypełniasz ją, zaczynając od lewego górnego rogu

9   8   7       6   5   4       3   2   1
6   5   4       6   5   4       3   2   1
3   2   1       3   2   1       3   2   1

6   6   3       6   5   4       3   2   1
5   5   2       5   5   3       3   2   1
4   4   1       4   2   1       3   2   1

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1

to daje 4,24559E + 29 możliwości lub 99 bitów

edycja: zapomniałem, że ostatni kwadrat jest w pełni określony przez wszystkie inne

Nie potrzebujesz pełnej tabeli przeglądowej, aby uzyskać optymalną ściśliwość. Uważam, że współczesne komputery korzystające z bardzo rozsądnej tabeli przeglądowej są w stanie policzyć liczbę ograniczonych Sudokusów, które są Sudokusami z niektórymi cyframi już na miejscu. Korzystając z tego, oto jak kodujesz (dekodowanie jest podobne).

$d_1$$N_1$$d_1$$d_2$$N_2$$d_1$$d_2$$N = \sum_i N_i$

$72.4$

Edycja: strona Wikipedii na temat matematyki Sudoku pomaga nam wyjaśnić obraz. Pomocna jest również tabela skompilowana przez Eda Russella .

Okazuje się, że jeśli weźmie się pod uwagę tylko trzy górne rzędy, wówczas zasadniczo należy wziąć pod uwagę tylko 44 różne konfiguracje. W tabeli można znaleźć całkowitą liczbę konfiguracji równoważną dowolnej z nich (zakładając, że górny wiersz to 123456789) oraz całkowitą liczbę ukończeń każdej z nich. Biorąc pod uwagę Sudoku, oto jak obliczymy jego liczbę porządkową:

1. Normalizuj konfigurację, tak aby jej górny wiersz to 123456789.
2. Dowiedz się, do której z 44 różnych konfiguracji należy. Artykuł w Wikipedii podaje algorytm do tego. Tabela zawiera liczbę klas równoważności dla każdej konfiguracji, a także liczbę zakończeń.
3. Określ liczbę porządkową konfiguracji trzech górnych wierszy w jej klasie równoważności. Można to zrobić na dwa sposoby: albo używając listy wszystkich klas równoważności (łącznie 36288 we wszystkich klasach równoważności), albo znajdując sposób szybkiego wyliczenia wszystkich z nich.
4. Znormalizuj pozostałe wiersze, sortując wiersze 4-6 i 7-9 według pierwszej kolumny, a następnie sortując te dwa bloki wierszy w dowolny arbitralny sposób. Zmniejsza to liczbę ukończeń 72 razy.
5. $2^{20}$
6. $i$$j$$k$$C_i,D_i$$C_i + jD_i + k$$9! \cdot 72$

Ta procedura jest odwracalna i wygeneruje Sudoku z liczby porządkowej. Zauważ, że wyliczenie Sudoku zostało zmniejszone do kilku minut (w 2006 r .; patrz strona dyskusji w artykule w Wikipedii) lub mniej, więc oczekuję, że na nowoczesnym komputerze takie podejście byłoby bardzo praktyczne i zajęłoby kilka sekund lub mniej.

Oto algorytm, który, jak podejrzewam, da całkiem dobre kodowanie. Masz gotowe sudoku, które chcesz skompresować, i powiedzmy, że już zakodowałeś niektóre jego komórki, więc jest częściowe sudoku (niekoniecznie z unikalnym rozwiązaniem) z wypełnionymi niektórymi komórkami.

Użyj ustalonego algorytmu, aby policzyć, ile liczb można umieścić w każdej pustej komórce. Znajdź leksykograficznie pierwszą komórkę, w której można umieścić najmniejszą liczbę różnych liczb, i zakoduj, która z tych liczb się w niej znajduje (więc jeśli komórka może zawierać tylko 3, 7 lub 9, cyfra 3 jest kodowana przez „0 ”, 7 przez„ 1 ”i 9 przez„ 2 ”). Zakoduj powstałą sekwencję, stosując kodowanie arytmetyczne (które uwzględnia liczbę możliwych liczb, które może zawierać komórka).

Nie wiem, jak długa będzie wynikowa sekwencja binarna, ale podejrzewam, że jest ona dość krótka, szczególnie jeśli Twój algorytm zliczania liczby liczb, które można umieścić w komórce, jest dość wyrafinowany.

Jeśli masz dobry algorytm, który ocenia prawdopodobieństwo każdej komórki zawierającej określoną liczbę, możesz zrobić jeszcze lepiej.

Wszelkie komentarze i krytyki są mile widziane

$69.96$$171.72$

1.) Przechowywanie puzzli oznacza przechowywanie rozwiązania (informacje teoretycznie).

$t(\alpha)\alpha^{2}$$t(\alpha)$$\alpha$$t(3) ~= 2.44444$$3$

$P$$\alpha^{4}$$t(\alpha)\alpha^{2}$

$M$$\beta \times \alpha^{4}$$\beta \ge 2t(\alpha)\alpha^{2}$$2t(\alpha)\alpha^{2}$$\{0,\pm 1\}$$\beta = kt(\alpha)\alpha^{2}$$k$

$V = MP$$\beta$$|\alpha^{2}|$$M$$\{0,\pm 1\}$

$V$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

$\alpha = 3$$t(\alpha) ~= 3$$2kt(\alpha)\alpha^{2}\log{\alpha} = 69.96k$$85.86k$$k=2$$139.92$$171.72bits$

$MP$

$A.)$$k$$2$$t(\alpha)-1$

$B.)$$t(\alpha)$$t(\alpha)$$k$$t(\alpha)$${}^{\alpha^{4}}C_{t(\alpha)\alpha^{2}}$${}^{\alpha^{4}-(3\alpha^{2} - 1)}C_{t(\alpha)\alpha^{2}-3t(\alpha)}$

$t(\alpha)\alpha^{2}$

$C.)$$k$

$D.)$ $V$$V$$O(\sqrt(V_{max})) = O(\sqrt{|\alpha^{2}|})$$2$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

$2k$$2$$A.)$$B.)$$C.)$$D.)$$89$$73$

Ma to zgłosić implementację skompresowanego kompaktowego kodowania sudoku (podobnego do sugestii Zurui Wanga 9/14/11).

Dane wejściowe to górny rząd i pierwsze 3 cyfry drugiego rzędu. Te są zredukowane do 1-9! oraz 1-120 i połączone do <= 4,4x10 ^ 7. Są one używane jako dane do liczenia leksykograficznego wszystkich częściowych sukokusów o długości 30 cyfr aż do pasującej sekwencji. Następnie końcowe liczenie do wszystkich 81 cyfr odbywa się w ten sam sposób. Te 3 sekwencje są przechowywane jako 32-bitowe liczby całkowite o maksymalnej długości 26 bitów, dzięki czemu można je dalej kompresować. Cały proces zajmuje około 3 minut, przy czym pierwsze 30 cyfr zajmuje większość czasu. Dekodowanie jest podobne - z wyjątkiem dopasowywania liczby zamiast sudokus.

Wkrótce - Wersja zawiera pierwsze 3 cyfry drugiego wiersza w wyliczeniu 30 cyfr (2. 32-bitowy kod), porównania z wyliczeniem Jarvisa (Jscott, 3/1615)

Wybrałbym następującą prostą analizę:

Każda wartość może być przechowywana w 4 bitach (zakresy od 1 do 9, te trzy bity pozwalają nawet na 0-16)

$9 \times 9 = 81$

$8 \times 8$

Chyba mógłbym to zredukować do:

$b = \lceil \log_2(v) \rceil (n-1)$

gdzie

$v$

$n$

Edycja: Neo Style: znam lateks.

Ta liczba jest inna dla każdego Sudoku. Jedną z zasad dla Sudoku jest to, że ma dokładnie jedno rozwiązanie.

Jeśli spojrzysz na przykład, jest to minimalna ilość danych, którą musisz przechowywać.

Jeśli pracujesz po przeciwnej stronie, możesz usunąć cyfrę po cyfrze i uruchomić solver na wyniku, aby sprawdzić, czy nadal ma dokładnie jedno rozwiązanie. Jeśli tak, możesz usunąć kolejną cyfrę. Jeśli nie, musisz przywrócić tę cyfrę i wypróbować inną. Jeśli nie możesz, znalazłeś minimum.

Ponieważ większość zagadek zaczyna się w większości pustych, kodowanie długości przebiegu prawdopodobnie przyniesie dobre wyniki.