Effiziente Kodierung von Sudoku-Rätseln

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 angeben $n$ $11n$ 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+4n$ $n=17$ $n$ $N \times 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×10^{21}$

Wenn ich meine Rechnung richtig gemacht habe ( ), ergibt das 73 (72,498) Bits an Informationen für eine Nachschlagetabelle. $\frac{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.

combinatorics modelling information-theory sudoku Kevin
quelle

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 \times 10^{21}

$6.67 \times 10^{21}$

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!

$9!$

Kevin

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

Kaveh

Antworten:

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\times 9$

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

Die folgenden Bits sind Flags, die angeben, ob die verbleibenden Positionen eine Nummer haben oder nicht (Sie überspringen einfach die Positionen, an denen steht). Wann immer eines dieser Bits ist , geben die nächsten 3 Bits an, um welche Zahl es sich handelt (in der geordneten Menge ohne ). Wenn zum Beispiel 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 $81-\ell$ $m$ 1 $\{1,\ldots,9\}$ $m$ $m=4$ 101 , also ist es . Zahlen werden als binär codiert, Zahlen als . Da wir bereits Positionengeschriebenhatten, werdenin diesem Schrittnur Bits hinzugefügt, um den Rest der Karte zu codieren. $\{1,2,3,5,6,7,8,9\}$ $6$ $j<m$ $j-1$ $j>m$ $j-2$ $\ell$ $3(n-\ell)$

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 ℓ + 3 n .

$B=4+4+7\ell+(81-\ell)+3(n-\ell)=89+3\ell+3n.$

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

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 vorausgesetzt, dass . Zumindest zeigt es eine allgemeine Idee, wie man die Tatsache ausnutzen kann, dass sehr nahe an (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 Zahlen ausdrücken . $n\in\{17,18,19\}$ $n=20$ $\ell=0$ $N=9$ $2^{\lfloor\log_2N\rfloor}$ $N=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 ( ). Wenn Sie die Positionen von links nach rechts und dann von oben nach unten ablesen, erscheint in Position ( ). So beginnt unsere Kodierung mit . $m=7$ 0111 $\ell=1$ 0001 $m$ $36$ 0100100011100010100100

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 usw. ( ). Schließlich überspringen wir die Position, an der ist, und codieren 8 als (die 6. Zahl, die von 0 in der Liste ) und 9 als . Die vollständige Codierung lautet wie folgt: $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

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

Janoma
quelle