Effiziente Kodierung von Sudoku-Rätseln

16

Wenn Sie ein beliebiges 9x9-Raster angeben möchten, müssen Sie die Position und den Wert jedes Quadrats angeben. Eine naive Codierung könnte dazu 81 (x, y, value) Triplets ergeben, die 4 Bits für jedes x, y und einen Wert (1-9 = 9 Werte = 4 Bits) für insgesamt 81x4x3 = 972 Bits erfordern. Durch Nummerieren jedes Quadrats kann die Positionsinformation auf 7 Bits reduziert werden, wobei für jedes Quadrat ein Bit und insgesamt 891 Bits verworfen werden. Durch Angabe einer vorgegebenen Reihenfolge kann diese drastischer auf nur die 4 Bits für jeden Wert von insgesamt 324 Bits reduziert werden. In einem Sudoku können jedoch Zahlen fehlen. Dies bietet die Möglichkeit, die Anzahl der Nummern zu verringern, die angegeben werden müssen, erfordert jedoch möglicherweise zusätzliche Bits zum Anzeigen von Positionen. Mit unserer 11-Bit-Codierung von (Position, Wert) können wir ein Puzzle mit Hinweisen mit angebenn11n Bits, zB ein minimales (17) Puzzle benötigt 187 Bits. Die beste Kodierung, an die ich bisher gedacht habe, ist die Verwendung eines Bits für jedes Leerzeichen, um anzuzeigen, ob es gefüllt ist, und, falls ja, die folgenden 4 Bits, um die Zahl zu kodieren. Dies erfordert Bits, 149 für ein minimales Puzzle ( ). Gibt es eine effizientere Codierung, vorzugsweise ohne eine Datenbank für jedes gültige Sudoku-Setup? (Bonuspunkte für das Adressieren eines allgemeinen aus Rätseln)81+4nn=17nN×N

Mir ist gerade eingefallen, dass viele Puzzles eine Rotation einer anderen sein oder eine einfache Permutation von Ziffern haben. Vielleicht könnte das helfen, die benötigten Bits zu reduzieren.

Laut Wikipedia ,

Die Anzahl der klassischen 9 × 9-Sudoku-Lösungsgitter beträgt 6.670.903.752.021.072.936.960 (Sequenz A107739 in OEIS) oder ungefähr .6,67×1021

Wenn ich meine Rechnung richtig gemacht habe ( ), ergibt das 73 (72,498) Bits an Informationen für eine Nachschlagetabelle.ln(6,670,903,752,021,072,936,960)ln(2)

Aber:

Die Anzahl der wesentlich unterschiedlichen Lösungen unter Berücksichtigung von Symmetrien wie Rotation, Reflexion, Permutation und Relabelling betrug lediglich 5.472.730.538 [15] (Sequenz A109741 in OEIS).

Das ergibt 33 (32,35) Bits, so dass es möglich ist, dass eine clevere Methode zum Anzeigen der zu verwendenden Permutation unter die vollen 73 Bits fällt.

Kevin
quelle
1
Ha, ich habe anfangs ein paar Sachen gepostet, ohne über das Problem gründlich genug nachzudenken. Ich habe es gelöscht. Gute Frage!
Patrick87
Können Sie uns daran erinnern, wie viele Sudoku-Rätsel es gibt, damit wir wissen, wie weit die Lücke zwischen diesen leicht dekodierbaren Kodierungen und einer Brute-Force-Aufzählung ist?
Gilles 'SO- hör auf böse zu sein'
Sie müssen in der Lage sein, alle Raster von zu codieren , daher benötigen Sie 73 Bit (unter der Annahme einer Codierung mit fester Länge). Dabei hilft Ihnen keine „clevere Methode zur Angabe der zu verwendenden Permutation“. 6.67×1021
Svick
Aus informationstheoretischer Sicht denke ich, dass Sie Recht haben müssen, aber ich kann nicht herausfinden, woher die zusätzlichen Bits kommen. Es gibt Permutationen, die 19 Bit plus 3 für Spiegeln und Drehen sind, also 22 plus 33 für einzigartige Rätsel, ergeben 55; Woher kommen die anderen 18? 9!
Kevin

Antworten:

5

Gibt es eine effizientere Codierung, vorzugsweise ohne eine Datenbank für jedes gültige Sudoku-Setup?

Ja. Ich kann mir eine Codierung vorstellen, mit der Sie die 149-Bit-Codierung eines minimalen Puzzles in 6 oder 9 Bit verbessern können, je nach Bedingung. Dies ist ohne eine Datenbank oder ein Register anderer Lösungen oder Teilplatinen. Hier kommt's:9×9

Zuerst verwenden Sie Bits, um eine Zahl m mit einer minimalen Anzahl von Erscheinungen auf der Platine zu codieren . Die nächsten 4 Bits codieren die tatsächliche Häufigkeit, mit der m angezeigt wird. Die nächsten 7 Bits codieren jede der Positionen, an denen m erscheint.4m4m7m

Die folgenden Bits sind Flags, die angeben, ob die verbleibenden Positionen eine Nummer haben oder nicht (Sie überspringen einfach die Positionen, an denen m steht). Wann immer eines dieser Bits ist , geben die nächsten 3 Bits an, um welche Zahl es sich handelt (in der geordneten Menge { 1 , , 9 } ohne m ). Wenn zum Beispiel m = 4 und die 3 Bits sind , dann ist die Zahl an der entsprechenden Stelle auf der Karte die fünfte (von 0 beginnend) in der Menge { 1 , 2 , 3 ,81m1{1,,9}mm=4101 , also ist es 6 . Zahlen j < m werden als j - 1 binär codiert, Zahlen j > m als j - 2 . Da wir bereits Positionengeschriebenhatten, werdenin diesem Schrittnur 3 ( n - ) Bits hinzugefügt, um den Rest der Karte zu codieren.{1,2,3,5,6,7,8,9}6j<mj1j>mj23(n)

Somit ist die Gesamtzahl der Bits, die erforderlich sind, um eine Karte unter Verwendung dieser Prozedur zu codieren,

B=4+4+7+(81)+3(n)=89+3+3n.

Für ist zu beachten, dass 0 oder 1 sein kann (im Allgemeinen n / 9 ). Somit kann B 140 oder 143 sein, abhängig davon, ob eine Zahl nicht auf der Tafel erscheint.n=17n/9B

Es ist erwähnenswert, dass Kevins Lösung im allgemeinen Fall viel besser ist. Diese Codierung verwendet höchstens 149 Bits nur für oder für n = 20, vorausgesetzt, dass = 0 ist . Zumindest zeigt es eine allgemeine Idee, wie man die Tatsache ausnutzen kann, dass N = 9 sehr nahe an 2 log 2 N ⌋ liegt (was bedeutet, dass wir dazu neigen, "Speicher zu verlieren", indem wir 4 Bits pro Wert verwenden, da 4 Bits dies erlauben wir müssen auch N = 16 Zahlen ausdrücken .n{17,18,19}n=20=0N=92log2NN=16


Beispiel. Betrachten Sie die folgende Tafel mit Hinweisen.n=17

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

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

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

Hier ist keine Nummer nicht erscheint auf dem Brett, und Nummern 6, 7 und 9 nur einmal vorkommen. Wir nehmen ( ) und = 1 ( ). Wenn Sie die Positionen von links nach rechts und dann von oben nach unten ablesen, erscheint m in Position 36 ( ). So beginnt unsere Kodierung mit .m=70111=10001m360100100011100010100100

Als nächstes benötigen wir sieben 0s, eins 1und die 3-Bit-Codierung der Zahl , dann a, gefolgt von a und die 3-Bit-Codierung von 4 usw. ( ). Schließlich überspringen wir die Position, an der m = 7 ist, und codieren 8 als (die 6. Zahl, die von 0 in der Liste 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 zählt ) und 9 als . Die vollständige Codierung lautet wie folgt:10140000000100101100m=71101,2,3,4,5,6,8,9111

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

Die komplette Kodierung ist 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, und der Leser kann überprüfen, ob die Länge der Zeichenkette tatsächlich 143 ist :-)

Janoma
quelle