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

28

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.log2(981))=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?

orlp
źródło
3
Czy naprawdę jest jakościowa różnica między pominięciem dziewiątej liczby w wierszu lub kolumnie 3x3 a po prostu przechowywaniem minimalnego sudoku z pustymi przestrzeniami, które ma to unikalne rozwiązanie? „nie musi obsługiwać pustych komórek” to trochę czerwony śledź, jeśli konieczne jest optymalne rozwiązanie.
Wooble,
19
Ponieważ istnieje rozwiązane sudoku 6,67 × 10 ^ 21 („QSCGZ” 2003; Felgenhauer i Jarvis 2005) oraz log_2 (6,67 × 10 ^ 21) = 72,4…, dolna granica to 73 bity (nawet jeśli używasz wyszukiwania wielkiej tabeli) . Jeśli nie musisz rozróżniać zasadniczo identycznych rozwiązań pod względem symetrii, ta dolna granica nie ma zastosowania.
Tsuyoshi Ito
9
To pytanie stanowiłoby dobry konkurs programowy.
Peter Shor,
1
Analogiczna dolna granica dla zasadniczo identycznych rozwiązań wynosi 33 bity.
Charles,
3
Dlaczego potrzebujesz stołu do wyszukiwania? Możesz po prostu wyliczyć rozwiązania Sudoku jeden po drugim, aż osiągniesz żądaną liczbę.
Zirui Wang,

Odpowiedzi:

19

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.

David Eppstein
źródło
4
Możesz również zmniejszyć liczbę wyborów, wypełniając szóste pole 3x3. To pole staje się 4,3,2 / 3,2,1 / 2,1,1, co daje w sumie 83 bity, jeśli poprawnie go obliczyłem.
Peter Shor,
@Peter - nie. 3 cyfry po prawej stronie mogą być takie same jak liczby powyżej. Nie wiesz, że wszystkie są różne. Najbardziej pewnymi unikalnymi liczbami są 3, więc pierwsze pudełko to wybór spośród sześciu przedmiotów. (Ta jedna lokalizacja jest przykładem. Dotyczy to również innych.)
Hogan,
@David - przechodząc do mojego komentarza do Piotra, nie sądzę, żeby twoje liczby były błędne. 6 5 4 4 3 2 3 2 1Uważam, że w drugim polu musi być 6 5 4 6 5 4 3 2 1w najgorszym przypadku.
Hogan,
Hogan, nie, zobacz część mojej odpowiedzi na temat: „po wypełnieniu jednego wiersza lub kolumny pola zawsze możesz wybrać następny wiersz lub kolumnę, aby wypełnić tę, w której są maksymalnie cztery możliwe wartości „
David Eppstein,
@David - Pozwala na oznaczenie 3 x 3s 1,1 1,2 1,3 od lewej do prawej od góry do dołu. Niech etykieta Kwadratów A - Idę od lewej do prawej od góry do dołu. Lokalizacja D w 1,3 zna 3 liczby w 3x3, w której jest (A, B, C) i zna 3 liczby w 1,2 (D, E, F), ale nie wie, że te 6 liczb jest różne. Mogą to być te same 3 liczby z pól 3,1 i 2,1, więc istnieje MAX 6 możliwości.
Hogan,
13

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

maniak zapadkowy
źródło
Bardzo dobrze!! Dodam, że nie jest dla mnie jasne, czy kiedykolwiek można osiągnąć te najgorsze możliwości dla prawdziwego rozwiązania Sudoku (szczególnie jeśli używasz zaawansowanego algorytmu, który wykorzystuje niektóre techniki Sudoku, aby zawęzić możliwości, dla których liczby mogą iść w komórce ).
Peter Shor,
@peter, ale musisz dodać te zawężające się w en i dekodowaniu, a ja zdałem sobie sprawę, że jeśli musisz wybrać jeden i nie naprawić kolejności (najłatwiejszy, ale nie optymalny sposób), musisz dodać to również do kodowania
maniak ratchet
Nie, jeśli użyjesz tego samego algorytmu do ustalenia najlepszej komórki w procedurze en- i dekodowania, da tę samą komórkę (ponieważ działa na tych samych danych), więc procedury en- i dekodowania zostaną zsynchronizowane, i nie musisz dodawać kolejności do kodowania. Ten pomysł powoduje również, że algorytm kompresji danych LZW działa.
Peter Shor,
Myślę, że minimalne bity wymagane do przechowywania prawidłowej łamigłówki sudoku nie są funkcją obliczalną (Kołmogorow). Jednak 103 bity autorstwa Petera / Ratcheta wydają się być dobre.
Marzio De Biasi,
2
@Vor: Technicznie, maszyna Turinga, która podaje poprawną liczbę bitów, gdy otrzymuje łamigłówkę sudoku, ponieważ dane wejściowe są skończone, ponieważ zbiór wejściowy jest skończony, więc „ile bitów potrzeba do opisania tej układanki” jest „trywialnie” obliczalny. Mówię, że moglibyśmy faktycznie znaleźć taką maszynę Turinga (w zasadzie obliczenia zajęłyby o wiele za dużo czasu), ponieważ nie może to być trudniejsze niż obliczenie skończonego prefiksu liczby Omega.
Aaron Sterling
5

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).

d1N1d1d2N2d1d2N=iNi

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. 220
  6. ijkCi,DiCi+jDi+k9!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.

Yuval Filmus
źródło
2
Czy można skutecznie policzyć rozwiązania ograniczonego sudoku? Jest # P-complete, jeśli uogólnisz rozmiar i dopuścisz puste miejsca w dowolnych miejscach.
Tsuyoshi Ito,
2
Jak wspomniałem w mojej odpowiedzi, kodowanie arytmetyczne osiągnie prawie optymalną kompresję dla tego scenariusza.
Peter Shor,
1
Być może masz rację, ale twoje twierdzenie sugeruje, że liczba siatek sudoku (6,67 × 10 ^ 21) jest łatwa do obliczenia na nowoczesnym komputerze. Rzeczywiście można obliczyć, ale czy jest to łatwe?
Tsuyoshi Ito
2
Odniosłem to wrażenie w jednym z artykułów opisujących sposób wykonania obliczeń. Możesz nawet obliczyć niektóre „cięższe” dane w procesie wstępnego przetwarzania i przechowywać je w rozsądnej wielkości tabeli - wzrost prędkości może być dramatyczny. O ile pamiętam, zajęło im to tylko kilka godzin i to kilka lat temu. Załóżmy teraz, że używasz stołu, aby był 1000 razy szybszy. Co więcej, na każdym etapie liczby maleją wykładniczo, więc większość pracy prawdopodobnie koncentruje się na pierwszym etapie.
Yuval Filmus,
1
@ tsuyoshi Wierzę, że istnieje pewna wersja / rozszerzenie BDD, które sprawiają, że obliczenia są stosunkowo proste - musiałbym trochę popracować nad tym, ale wiem, że zostały one wykorzystane do dość skomplikowanych problemów liczenia kombinatorycznego.
Steven Stadnicki,
4

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.

Peter Shor
źródło
3

Wszelkie komentarze i krytyki są mile widziane

69.96171.72

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

t(α)α2t(α)αt(3) =2.444443

Pα4t(α)α2

Mβ×α4β2t(α)α22t(α)α2{0,±1}β=kt(α)α2k

V=MPβ|α2|M{0,±1}

Vβlogα2=2kt(α)α2logα

α=3t(α) =32kt(α)α2logα=69.96k85.86kk=2139.92171.72bits

MP

A.)k2t(α)1

B.)t(α)t(α)kt(α)α4Ct(α)α2α4(3α21)Ct(α)α23t(α)

t(α)α2

C.)k

D.) VVO((Vmax))=O(|α2|)2βlogα2=2kt(α)α2logα

2k2A.)B.)C.)D.)8973

vs
źródło
1

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)

jscott
źródło
1
FYI: Jeśli utworzyłeś dwa konta i chciałbyś je połączyć, zobacz cstheory.stackexchange.com/help/merging-accounts
DW
0

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×9=81

8×8

Chyba mógłbym to zredukować do:

b=log2(v)(n1)

gdzie

v

n

Edycja: Neo Style: znam lateks.

Alfa
źródło
-2

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.

Aaron Digulla
źródło
To chciwe podejście niekoniecznie osiąga minimum, być może trzeba starannie wybrać cyfrę, którą należy usunąć na każdym etapie.
Diego de Estrada,
To tylko przykład. Google dla „generatorów puzzli sudoku”, aby uzyskać bardziej wyrafinowane.
Aaron Digulla,
5
Naprawdę nie rozumiem, dlaczego miałbyś oczekiwać, że będzie to szczególnie dobre. To wydaje się raczej przeczuciem niż odpowiedzią.
Joe Fitzsimons,