Encodage efficace des puzzles sudoku

16

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 nn11n 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+4nn=17nN×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×1021

Si j'ai bien fait mes calculs ( ), ce qui donne 73 (72.498) bits d'information pour une table de correspondance.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.

Kevin
la source
1
Ha, j'ai d'abord posté des trucs sans trop réfléchir au problème. Je l'ai supprimé. Grande question!
Patrick87
Pouvez-vous nous rappeler combien il y a de puzzles Sudoku, afin que nous sachions à quel point l'écart est entre ces encodages facilement décodables et une énumération par force brute?
Gilles 'SO- arrête d'être méchant'
Vous devez être en mesure de coder toutes les grilles de , vous avez donc besoin de 73 bits (en supposant un codage de longueur fixe). Aucune «méthode intelligente pour indiquer la permutation à utiliser» ne vous y aidera. 6.67×1021
svick
@sick Du point de vue de la théorie de l'information, je pense que vous devez avoir raison, mais je ne sais pas d'où viennent les bits supplémentaires. Il y en a permutations, qui est de 19 bits, plus 3 pour le miroir et la rotation, donc 22 plus les 33 pour les puzzles uniques, fait 55; D'où viennent les 18 autres? 9!
Kevin

Réponses:

5

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

Tout d'abord, vous utilisez bits pour coder un nombre m4m 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.4m7m

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 ,81m1{1,,9}mm=4101 , 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}6j<mj1j>mj23(n)

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

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

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=17n/9B

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 = 9n{17,18,19}n=20=0N=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.2log2NN=16


n=17

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

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

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

m=70111=10001m360100100011100010100100

0110140000000100101100m=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

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

Janoma
la source