Encodage efficace des puzzles sudoku

Spécifier une grille arbitraire 9x9 nécessite de donner la position et la valeur de chaque carré. Un codage naïf pour cela pourrait donner 81 triplets (x, y, valeur), nécessitant 4 bits pour chaque x, y et valeur (1-9 = 9 valeurs = 4 bits) pour un total de 81x4x3 = 972 bits. En numérotant chaque carré, on peut réduire les informations de position à 7 bits, en laissant tomber un bit pour chaque carré et un total de 891 bits. En spécifiant un ordre prédéterminé, on peut le réduire de façon plus drastique à seulement 4 bits pour chaque valeur pour un total de 324 bits. Cependant, un sudoku peut avoir des numéros manquants. Cela permet de réduire le nombre de nombres qui doivent être spécifiés, mais peut nécessiter des bits supplémentaires pour indiquer les positions. En utilisant notre codage 11 bits de (position, valeur), nous pouvons spécifier un puzzle avec indices avec11 n 81 + 4 n n = 17 $n$$11n$ bits, par exemple un puzzle minimal (17) nécessite 187 bits. Le meilleur encodage auquel j'ai pensé jusqu'à présent est d'utiliser un bit pour chaque espace pour indiquer s'il est rempli et, si c'est le cas, les 4 bits suivants codent le nombre. Cela nécessite bits, 149 pour un puzzle minimal ( ). Existe-t-il un encodage plus efficace, de préférence sans base de données de chaque configuration sudoku valide? (Points bonus pour aborder un général de N × N puzzle)$81+4n$$n=17$$n$$N \times N$

Il m'est venu à l'esprit que de nombreux puzzles seront une rotation d'un autre, ou auront une simple permutation de chiffres. Cela pourrait peut-être aider à réduire les bits requis.

Selon Wikipedia ,

Le nombre de grilles de solution Sudoku 9 × 9 classiques est de 6 670 903 752 021 022 936 960 (séquence A107739 dans OEIS), soit environ .$6.67×10^{21}$

Si j'ai bien fait mes calculs ( ), ce qui donne 73 (72.498) bits d'information pour une table de correspondance.$\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$

Mais:

Le nombre de solutions essentiellement différentes, lorsque l'on tient compte des symétries telles que la rotation, la réflexion, la permutation et le réétiquetage, n'était que de 5 472 730 538 [15] (séquence A109741 dans OEIS).

Cela donne 33 (32,35) bits, il est donc possible qu'une méthode intelligente d'indiquer quelle permutation à utiliser puisse descendre en dessous des 73 bits.

Existe-t-il un encodage plus efficace, de préférence sans base de données de chaque configuration sudoku valide?

Oui. Je peux penser à un encodage améliorant votre encodage 149 bits d'un puzzle minimal en 6 ou 9 bits, selon une condition. Ceci est sans base de données ni registre d'autres solutions ou cartes partielles. Ça y est:$9\times 9$

Tout d'abord, vous utilisez bits pour coder un nombre $4$$m$ avec un nombre minimal d'apparitions dans la carte. Les bits suivants codent le nombre réel ℓ de fois où m apparaît. Les prochaines 7 ℓ bits de coder chacune des positions dans lesquelles m apparaît.$4$$\ell$$m$$7\ell$$m$

Les bits suivants sont des drapeaux indiquant si les positions restantes ont un nombre ou non (il suffit de sauter les positions dans lesquelles m est). Chaque fois que l'un de ces bits est , les 3 bits suivants indiquent de quel nombre il s'agit (dans l'ensemble ordonné { 1 , … , 9 } sans m ). Par exemple, si m = 4 et les 3 bits le sont , alors le nombre à la position correspondante sur la carte est le 5ème (à partir de 0) de l'ensemble { 1 , 2 , 3 $81-\ell$$m$1$\{1,\ldots,9\}$$m$$m=4$101 , il est donc 6 . Les nombres j < m seront encodés en binaire comme j - 1 , tandis que les nombres j > m seront encodés en j - 2 . Comme nous avions déjà écrit ℓ positions, seuls 3 ( n - ℓ ) bits seront ajoutés pour encoder le reste de la carte dans cette étape.$\{1,2,3,5,6,7,8,9\}$$6$$j<m$$j-1$$j>m$$j-2$$\ell$$3(n-\ell)$

Ainsi, le nombre total de bits requis pour coder une carte en utilisant cette procédure est

Pour , on note que ℓ peut être 0 ou 1 (en général, ℓ ≤ ⌊ n / 9 ⌋ ). Ainsi, B peut être 140 ou 143 selon qu'il n'y a pas de numéro sur le tableau.$n=17$$\ell$$\ell\leq\lfloor n/9\rfloor$$B$

Il convient de souligner que la solution de Kevin est bien meilleure dans le cas général. Ce codage utilise au plus 149 bits uniquement pour , ou pour n = 20 à condition que ℓ = 0 . Au moins, il montre une idée générale sur la façon de tirer parti du fait que N = $n\in\{17,18,19\}$$n=20$$\ell=0$$N=9$ est très proche de (ce qui signifie que nous avons tendance à "perdre de la mémoire" en utilisant 4 bits par valeur, car 4 bits permettent nous devons également exprimer N = 16 nombres.$2^{\lfloor\log_2N\rfloor}$$N=16$

$n=17$

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

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

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

$m=7$0111$\ell=1$0001$m$$36$0100100011100010100100

01$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

L'encodage complet est 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, et le lecteur peut vérifier que la longueur de cette chaîne est bien 143 :-)