Wie viele Bits sind mindestens erforderlich, um ein Sudoku-Puzzle zu speichern?

28

Hinweis: Hierbei handelt es sich um das Standard-9x9-Sudoku-Puzzle. Die Lösung muss nur gelöste, rechtliche Rätsel unterstützen . Eine Lösung muss also keine leeren Zellen unterstützen und kann sich auf die Eigenschaften eines gelösten Sudoku-Puzzles verlassen.

Ich fragte mich, aber mir fiel keine Antwort ein, mit der ich zufrieden war. Eine naive Lösung würde ein Byte für jede Zelle (81 Zellen) verwenden, was insgesamt 648 Bits entspricht. Eine komplexere Lösung würde das gesamte Sudoku-Puzzle in einer Zahl zur Basis 9 (eine Ziffer pro Zelle) und log 2 ( 9 81 ) ) ) = 257log2(981))=257 Bits erfordern .

Es kann jedoch noch verbessert werden. Wenn Sie beispielsweise 8 der 9 Zahlen in einem 3x3-Subgrid kennen, können Sie trivial auf die 9. schließen. Sie können diese Überlegungen bis zu dem Punkt fortsetzen, an dem diese Frage auf die Anzahl der eindeutigen gelösten Sudokus hinausläuft. Jetzt können Sie eine große Nachschlagetabelle verwenden, die jede Binärzahl einem Sudoku-Puzzle zuordnet, aber das wäre keine brauchbare Lösung.

Also meine Frage:

Was ist ohne Verwendung einer Nachschlagetabelle die Mindestanzahl von Bits, die zum Speichern eines Sudoku-Puzzles erforderlich sind, und mit welchem ​​Algorithmus?

orlp
quelle
3
Gibt es wirklich einen qualitativen Unterschied zwischen dem Weglassen der neunten Zahl in einer 3x3-Zeile oder Spalte und dem Speichern des minimalen Sudoku mit Leerzeichen, das diese einzigartige Lösung bietet? "Leere Zellen müssen nicht unterstützt werden" ist ein bisschen wie ein roter Hering, wenn die optimale Lösung dies unbedingt tun muss.
Wooble
19
Da es 6,67 × 10 ^ 21 gelöste Sudoku („QSCGZ“ 2003; Felgenhauer und Jarvis 2005) und log_2 (6,67 × 10 ^ 21) = 72,4… gibt, beträgt die Untergrenze 73 Bit (auch wenn Sie die große Tabellensuche verwenden). . Wenn Sie hinsichtlich der Symmetrie keine im Wesentlichen identischen Lösungen unterscheiden müssen, gilt diese Untergrenze nicht.
Tsuyoshi Ito
9
Diese Frage wäre ein guter Programmierwettbewerb.
Peter Shor
1
Die analoge Untergrenze für im Wesentlichen identische Lösungen beträgt 33 Bit.
Charles
3
Warum brauchen Sie einen Nachschlagetisch? Sie können Sudoku-Lösungen einfach einzeln aufzählen, bis die gewünschte Anzahl erreicht ist.
Zirui Wang

Antworten:

19

Entspricht der Antwort von Ratchet Freak, wenn Sie die nicht mit einem Stern versehenen Zellen in der folgenden Matrix jeweils in einem 3x3-Feld ausfüllen und immer das nächste Feld auswählen, das Zeilen oder Spalten mit einem Feld teilt, in dem Sie sich befinden Haben Sie bereits ausgefüllt, erhalten Sie ein Muster wie das folgende für die Anzahl der Auswahlmöglichkeiten pro Schritt (Füllen Sie zuerst das obere mittlere Feld, dann das obere rechte Feld usw.).

In jedem 3x3-Feld nach dem ersten werden drei der verbleibenden sechs Ziffern in einer einzelnen Zeile lokalisiert, sobald Sie eine Zeile oder Spalte des Felds ausgefüllt haben. Wählen Sie zuerst ihre Positionen aus und füllen Sie dann die verbleibenden drei Zellen aus. (Die tatsächliche Reihenfolge der auszufüllenden Zellen hängt davon ab, was Sie bereits wissen. Die Anzahl der Auswahlmöglichkeiten ist jedoch nie größer als die von mir angegebene.)

Nachdem Sie diese Felder ausgefüllt haben, werden alle Sterne bestimmt.

* * * 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 * * *

Wenn ich richtig gerechnet habe, ergibt das 87 Bit. Laut Peter Shors Kommentar sind im letzten 3x3-Block einige zusätzliche Einsparungen zu verzeichnen: Jeder Wert ist in einer von vier Zellen lokalisiert, und jede Zeile enthält mindestens eine Zelle mit nur vier möglichen Werten, also mit Sicherheit die Faktoren dafür Block sollte mit 4, nicht mit 6 beginnen, aber ich verstehe die verbleibenden Faktoren in Shors Antwort nicht.

David Eppstein
quelle
4
Sie können die Anzahl der Auswahlmöglichkeiten auch verringern, wenn Sie das sechste 3x3-Feld ausfüllen. Diese Box wird 4,3,2 / 3,2,1 / 2,1,1 für insgesamt 83 Bits, wenn ich es richtig berechnet habe.
Peter Shor
@Peter - nein. Die 3 Zahlen auf der rechten Seite können mit den obigen Zahlen übereinstimmen. Sie wissen nicht, dass sie alle verschieden sind. Die sichersten eindeutigen Zahlen sind 3, sodass die erste Box eine Auswahl aus sechs Artikeln ist. (Dieser eine Ort ist ein Beispiel. Dies gilt auch für die anderen.)
Hogan
@David - Ich gehe von meinem Kommentar zu Peter aus und glaube nicht, dass deine Zahlen falsch sind. In der 2. Box muss es 6 5 4 4 3 2 3 2 1meiner Meinung nach 6 5 4 6 5 4 3 2 1für den schlimmsten Fall sein.
Hogan
Hogan, nein, siehe den Teil in meiner Antwort über "Sobald Sie eine Zeile oder Spalte des Kästchens ausgefüllt haben, können Sie immer die nächste Zeile oder Spalte auswählen, die ausgefüllt werden soll und in der es höchstens vier mögliche Werte gibt "
David Eppstein
@David - Lässt die 3 x 3s 1,1 1,2 1,3 von links nach rechts von oben nach unten beschriften. Lassen Sie die Quadrate A beschriften - ich gehe von links nach rechts von oben nach unten. Die Stelle D in 1,3 kennt 3 Zahlen in dem 3x3, in dem es sich befindet (A, B, C), und sie kennt 3 Zahlen in 1,2 (D, E, F), aber sie weiß nicht, dass diese 6 Zahlen unterschiedlich sind. Dies können die gleichen 3 Zahlen aus den Feldern 3,1 und 2,1 sein, es gibt also MAX 6 Möglichkeiten.
Hogan
13

Wenn Sie mit der Antwort von @ Peter fortfahren, finden Sie hier eine Liste der Worst-Case-Möglichkeiten für jede Zelle, während Sie sie von oben links ausfüllen

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

Dies ergibt 4.24559E + 29 Möglichkeiten oder 99 Bits

edit: habe vergessen, dass das letzte Quadrat vollständig von allen anderen bestimmt wird

Ratschenfreak
quelle
Sehr schön!! Lassen Sie mich hinzufügen, dass mir nicht klar ist, ob Sie diese Worst-Case-Möglichkeiten für eine echte Sudoku-Lösung jemals erreichen könnten (insbesondere wenn Sie einen ausgeklügelten Algorithmus verwenden, der einige Sudoku-Techniken verwendet, um die Möglichkeiten einzugrenzen, für die Zahlen in eine Zelle passen ).
Peter Shor
@ Peter, aber Sie müssen diese Verengungen in en und Decodierung hinzufügen, und mir wurde klar, dass Sie, wenn Sie eine auswählen und die Reihenfolge nicht festlegen müssen (einfachster Weg, aber nicht optimal), diese auch zur Codierung hinzufügen müssen
Ratschenfreak
Nein, wenn Sie den gleichen Algorithmus verwenden, um die beste Zelle in der En- und der Decodierungsprozedur herauszufinden, wird dieselbe Zelle angezeigt (da sie mit denselben Daten arbeitet), sodass die En- und Decodierungsprozeduren synchronisiert werden. und Sie müssen die Reihenfolge nicht zur Kodierung hinzufügen. Mit dieser Idee funktioniert auch der LZW-Datenkomprimierungsalgorithmus.
Peter Shor
Ich denke, dass die minimalen Bits, die zum Speichern eines gültigen Sudoku-Puzzles erforderlich sind, keine berechenbare Funktion sind (Kolmogorov). Die 103 Bits von Peter / Ratsche scheinen jedoch eine gute Grenze zu sein.
Marzio De Biasi
2
@Vor: Technisch gesehen ist die Turing-Maschine, die bei einem Sudoku-Puzzle als Eingabe die richtige Anzahl von Bits ausgibt, endlich, da die Eingabemenge endlich ist. "Wie viele Bits zur Beschreibung dieses Puzzles benötigt werden" ist also "trivial" berechenbar. Ich sage, wir könnten eine solche Turing-Maschine explizit finden (im Prinzip würden die Berechnungen viel zu lange dauern), weil es nicht schwieriger sein kann, als ein endliches Präfix einer Omega-Zahl zu berechnen.
Aaron Sterling
5

Sie benötigen keine vollständige Nachschlagetabelle, um eine optimale Komprimierbarkeit zu erzielen. Ich glaube, dass moderne Computer, die eine sehr vernünftige Nachschlagetabelle verwenden, in der Lage sind, die Anzahl der beschränkten Sudokus zu zählen, die Sudokus sind, bei denen einige Ziffern bereits vorhanden sind. Hier erfahren Sie, wie Sie kodieren (Dekodierung ist ähnlich).

Legen Sie eine Reihenfolge der Quadrate fest. Angenommen, die Zahl auf dem ersten Quadrat ist . Setzen Sie N 1 als Anzahl der Sudokus, deren erstes Quadrat kleiner als d 1 ist . Sei nun d 2 die Nummer des zweiten Quadrats. Setzen Sie N 2 als die Anzahl der Sudokus, deren erstes Quadrat d 1 und deren zweites Quadrat kleiner als d 2 ist . Und so weiter. Die codierte Zahl ist N = i N i .d1N1d1d2N2d1d2N=iNi

Diese Codierungsmethode ist in der Literatur als Binomialcodierung bekannt . Sie sollten es Ihnen ermöglichen, den Index eines gegebenen Sudoku effektiv (im realen Sinne) zu berechnen und umgekehrt. Sie benötigen dann , wie oben erwähnt, nur Bits (dies bedeutet, dass Sie mehrere davon mit dieser durchschnittlichen Anzahl von Bits codieren können).72,4

Bearbeiten: Die Wikipedia-Seite über die Mathematik von Sudoku hilft uns, das Bild zu klären. Hilfreich ist auch eine von Ed Russell zusammengestellte Tabelle .

Es stellt sich heraus, dass, wenn Sie nur die obersten drei Zeilen berücksichtigen, im Wesentlichen nur 44 verschiedene Konfigurationen zu berücksichtigen sind. In der Tabelle finden Sie die Gesamtzahl der Konfigurationen, die den jeweiligen Konfigurationen entsprechen (vorausgesetzt, die oberste Zeile ist 123456789), sowie die Gesamtzahl der Abschlüsse für jede Konfiguration. Bei einem Sudoku berechnen wir die Ordnungszahl wie folgt:

  1. Normalisieren Sie die Konfiguration so, dass die oberste Zeile 123456789 lautet.
  2. Finden Sie heraus, zu welcher der 44 verschiedenen Konfigurationen sie gehört. Der Wikipedia-Artikel gibt dafür einen Algorithmus an. In der Tabelle sind die Anzahl der Äquivalenzklassen für jede Konfiguration sowie die Anzahl der Abschlüsse aufgeführt.
  3. Bestimmen Sie die Ordnungszahl der Konfiguration der oberen drei Zeilen innerhalb der Äquivalenzklasse. Dies kann auf zwei Arten geschehen: entweder durch Verwendung einer Liste aller Äquivalenzklassen (es gibt insgesamt 36288 in allen Äquivalenzklassen) oder durch Auflisten aller Äquivalenzklassen.
  4. Normalisieren Sie die verbleibenden Zeilen, indem Sie die Zeilen 4-6 und 7-9 nach ihrer ersten Spalte sortieren und anschließend diese beiden Zeilenblöcke auf beliebige Weise sortieren. Dies reduziert die Anzahl der Abschlüsse um den Faktor 72.
  5. Zählen Sie alle Vervollständigungen mit derselben ersten Spalte auf. Es gibt ungefähr 220 von ihnen für jede Äquivalenzklasse, so dass das nicht zu lange dauern sollte. Auch hier sind einige Kompromisse möglich.
  6. Sei die Äquivalenzklasse, j die Ordnungszahl der Konfiguration der oberen drei Zeilen innerhalb der Äquivalenzklasse, k die Ordnungszahl der Vervollständigung. Es gibt zwei Arrays C i , D i (die aus Ed Russells Tabelle berechnet werden können), so dass C i + j D i + k die Ordnungszahl des Soduko bis zur 9 ist ! 72 Symmetrien berücksichtigt. Daraus können Sie die tatsächliche Ordnungszahl berechnen.ijkCi,DiCi+jDi+k9!72

Dieser Vorgang ist reversibel und generiert ein Sudoku aus einer Ordnungszahl. Beachten Sie, dass die Sudoku-Aufzählung auf einige Minuten (im Jahr 2006; siehe Diskussionsseite des Wikipedia-Artikels) oder weniger reduziert wurde. Daher erwarte ich, dass dieser Ansatz auf einem modernen Computer sehr praktisch ist und einige Sekunden oder weniger dauert.

Yuval Filmus
quelle
2
Ist es möglich, die Lösungen für eingeschränktes Sudoku effizient zu zählen? Es ist # P-vollständig, wenn Sie die Größe verallgemeinern und Leerzeichen an beliebigen Stellen zulassen.
Tsuyoshi Ito
2
Wie ich in meiner Antwort angedeutet habe, wird die arithmetische Codierung für dieses Szenario eine nahezu optimale Komprimierung erzielen.
Peter Shor
1
Sie mögen Recht haben, aber Ihre Behauptung impliziert, dass die Anzahl der Sudoku-Gitter (6,67 × 10 ^ 21) auf einem modernen Computer einfach zu berechnen ist. Es ist zwar möglich zu berechnen, aber ist es einfach?
Tsuyoshi Ito
2
Ich habe diesen Eindruck von einem der Papiere bekommen, die beschreiben, wie man die Berechnung macht. Sie könnten sogar einige der "schwereren" Daten in der Vorverarbeitung berechnen und in einer Tabelle mit angemessener Größe speichern - die Geschwindigkeitsgewinne können dramatisch sein. Soweit ich mich erinnere, hat es nur ein paar Stunden gedauert, und das vor einigen Jahren. Angenommen, Sie verwenden eine Tabelle, um sie 1000-mal schneller zu machen. Darüber hinaus nimmt die Anzahl in jeder Phase exponentiell ab, sodass sich der größte Teil der Arbeit wahrscheinlich auf die erste Phase konzentriert.
Yuval Filmus
1
@tsuyoshi Ich glaube, dass es eine Version / Erweiterung von BDDs gibt, die die Berechnung relativ unkompliziert macht - ich müsste ein bisschen danach graben, aber ich weiß, dass sie für einige ziemlich komplizierte kombinatorische Zählprobleme verwendet wurden.
Steven Stadnicki
4

Hier ist ein Algorithmus, von dem ich vermute, dass er eine ziemlich gute Kodierung liefert. Sie haben das fertige Sudoku, das Sie komprimieren möchten, und nehmen an, Sie haben bereits einige Zellen davon codiert. Es gibt also ein partielles Sudoku (nicht unbedingt mit einer eindeutigen Lösung), in dem einige Zellen ausgefüllt sind.

Verwenden Sie einen festen Algorithmus, um zu zählen, wie viele Zahlen in jede leere Zelle eingefügt werden können. Suchen Sie die lexikografisch erste Zelle, in die die kleinste Anzahl verschiedener Zahlen eingefügt werden kann, und kodieren Sie, welche dieser Zahlen darin enthalten ist. Wenn eine Zelle also nur eine 3, 7 oder 9 enthalten kann, wird die 3 mit "0" kodiert ", die 7 von" 1 "und die 9 von" 2 "). Codieren Sie die resultierende Sequenz mit einer arithmetischen Codierung (die die Anzahl der möglichen Zahlen berücksichtigt, die eine Zelle enthalten kann).

Ich weiß nicht, wie lang die resultierende Binärsequenz sein wird, aber ich vermute, dass sie ziemlich kurz ist, besonders wenn Ihr Algorithmus zum Zählen, wie viele Zahlen in eine Zelle gesetzt werden können, einigermaßen ausgefeilt ist.

Wenn Sie einen guten Algorithmus hätten, mit dem die Wahrscheinlichkeit geschätzt wird, dass jede Zelle eine bestimmte Zahl enthält, könnten Sie noch bessere Ergebnisse erzielen.

Peter Shor
quelle
3

Kommentare und Kritik sind willkommen

69.96171.72

1.) Das Speichern des Puzzles impliziert das Speichern der Lösung (Information theoretisch).

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

Pα4t(α)α2 ungleich Null Einträgen.

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

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

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

In your case, α=3 and t(α) =3 and 2kt(α)α2logα=69.96kbits to 85.86k bits. k=2, the minumum required provides roughly 139.92bits to 171.72bits roughly as a lower bound for the average case.

Note that I have hand-waived some assumptions such as sizes of entries of MP and number of entries one has on average in the puzzle.

A.)Of course, it mightbe possible to reduce k from 2 since in sudoku the position of the sparse entries are not that mutually independent. Each entry on an average t(α)1 entries each in its row, column and sub-box. That is given, that some entries are present in a sub-box or column or row, one can find the odds of entries being present in the same row, column or sub-box.

B.) Each row, column or sub-box is assumed to have on an average t(α) non-zero entries with no-repeating alphabet. This means some types of vectors with t(α) non-zero entries will never occur, thereby reducing the search space of solutions. This could also reduce k. For instance, fixing t(α) entries in a sub-box, a row and a column would reduce the search space from α4Ct(α)α2 to α4(3α21)Ct(α)α23t(α).

A comment: May be a multi-user arbitrarily correlated Slepian-Wolf model will help make the entries independent while still respecting the atmost t(α)α2 non-zero entries criterion. However, if one could use it, one need not have gone through the compressed sensing route. So applicability of Slepian-Wolf might be hard.

C.)From an error correction analogy, an even significant reduction may be possible, since in higher dimensions, there could be gaps between the half-the-minimum-distance radii hamming balls around code points with a possibility to correct greater errors. This also should lead to reduction of k.

D.) V itself can be entropy compressed. If the entries of V are quite similar in sizes, then can we assume that the difference between any two of the entries is atmost O((Vmax))=O(|α2|)? Then if encoding the differences between the entries suffices, this itself will remove the factor 2 in βlogα2=2kt(α)α2logα.

It would be interesting to see if 2k can be made equal or less than 2 using A.), B.), C.) and D.). This would be better than 89 bits (which is the best so far in other answers) and for the best case better than the absolute minimum for all puzzles which is around 73bits.

v s
quelle
1

This is to report an implementation of completed-sudoku compact encoding (similar to suggestion by Zurui Wang 9/14/11).

The input is the top row and 1st 3 digits of the 2nd row. These are reduced to 1-9! and 1-120 and combined to <= 4.4x10^7. These are used as givens to count lexicographically all the partial sukokus of 30 digits up to the matching sequence. Then the final count up to the entire 81 digits is done the same way. These 3 sequences are stored as 32-bit integers of max 26 bits, so can be compressed further. The entire process takes about 3 minutes, with the 1st 30 digits taking most of the time. The decoding is similar--except matching counts instead of sudokus.

Coming soon--Revision includes 1st 3 digits of 2nd row in enumeration of 30 digit completions (2nd 32-bit code), comparisons with Jarvis enumeration (Jscott, 3/1615)

jscott
quelle
1
FYI: If you created two accounts and would like to merge them, see cstheory.stackexchange.com/help/merging-accounts
D.W.
0

I would go with the following simple analysis:

Each value could be stored in 4 bits (ranges from 1-9, these three bits even allow for 0-16)

If we considered to store the WHOLE solution (not optimal), having 9×9=81 values. 3 bits each = 243 bits.

However, as the rules that the solved sudoku has to follow, storing every bit is in fact redundant. However, since the order is important, you need to store the first 8 values in each row (thus determining the 9th value), for 8 rows (thus determining the last row). This reduces the sudoku to 8×8 for 3 bits, 192 bits (24 bytes).

I guess I could reduce it to:

b=log2(v)(n1)

where

v = range of values (I've seen 0-5 sudokus a lot)

n = number of rows / columns

Edit: Neo Style: I know Latex.

Alpha
quelle
-2

That number is different for each Sudoku. One of the rules for Sudoku is that it has exactly one solution.

So if you look at an example, that's the minimum amount of data that you must store.

If you work from the opposite side, you can remove digit by digit and run a solver on the result to see if it still has exactly one solution. If so, you can delete another digit. If not, you must restore this digit and try another. If you can't, you have found a minimum.

Since most puzzles start mostly empty, a run length encoding will probably yield good results.

Aaron Digulla
quelle
This greedy approach not necessarily achieves the minimum, perhaps you need to select carefully which digit to remove in each step.
Diego de Estrada
Es ist nur ein Beispiel. Google für "Sudoku-Puzzle-Generatoren", um anspruchsvollere zu bekommen.
Aaron Digulla
5
I really don't see why you would expect this to perform particularly well. This just seems to be gut feeling rather than an answer.
Joe Fitzsimons