Quel est le nombre minimum de bits requis pour stocker un puzzle sudoku?

Remarque: il s'agit du puzzle sudoku 9x9 standard. La solution ne doit prendre en charge que des énigmes juridiques résolues . Ainsi, une solution n'a pas besoin de prendre en charge les cellules vides et peut s'appuyer sur les propriétés d'un puzzle sudoku résolu.

Je me posais la question, mais je ne pouvais pas penser à une réponse dont j'étais satisfait. Une solution naïve utiliserait un octet pour chaque cellule (81 cellules), totalisant 648 bits. Une solution plus sophistiquée stockerait l'intégralité du puzzle sudoku dans un nombre de base 9 (un chiffre par cellule) et nécessiterait bits.$\lceil\log_2(9^{81}))\rceil = 257$

Mais il peut encore être amélioré, par exemple, si vous connaissez 8 des 9 nombres dans une sous-grille 3x3, vous pouvez en déduire trivialement le 9. Vous pouvez continuer ces pensées au point où cette question se résume à Quelle est la quantité de sudokus résolus uniques? Vous pouvez maintenant utiliser une énorme table de recherche qui mappe chaque nombre binaire sur un puzzle sudoku, mais ce ne serait pas une solution utilisable.

Donc, ma question:

Sans utiliser une table de recherche, quel est le nombre minimum de bits requis pour stocker un puzzle sudoku et avec quel algorithme?

Dans le même sens que la réponse de Ratchet Freak, si vous remplissez les cellules non suivies dans la matrice suivante, une case 3x3 à la fois, en choisissant toujours la case suivante à remplir pour être celle qui partage des lignes ou des colonnes avec une case que vous 'avez déjà rempli, vous obtenez un modèle comme le suivant pour le nombre de choix par étape (en remplissant d'abord la case du milieu en haut, la case en haut à droite ensuite, etc.).

Dans chaque case 3x3 après la première, une fois que vous avez rempli une ligne ou une colonne de la case, trois des six chiffres restants sont localisés sur une seule ligne. Choisissez d'abord leur emplacement, puis remplissez les trois cellules restantes. (Ainsi, l'ordre réel des cellules à remplir peut varier en fonction de ce que vous savez déjà, mais le nombre de choix n'est jamais supérieur à ce que j'ai montré.)

Après avoir rempli ces cellules, les étoiles sont toutes déterminées.

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

Si j'ai calculé correctement, cela donne 87 bits. Il y a des économies supplémentaires à réaliser dans le dernier bloc 3x3, selon le commentaire de Peter Shor: chaque valeur est localisée dans l'une des quatre cellules, et chaque ligne contient au moins une cellule avec seulement quatre valeurs possibles, donc certainement les facteurs dans cela le bloc devrait commencer par 4 et non 6, mais je ne comprends pas les autres facteurs dans la réponse de Shor.

en cours avec la réponse de @ peter, voici une liste des possibilités les plus défavorables pour chaque cellule pendant que vous la remplissez à partir du coin supérieur gauche

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

cela donne 4 24559E + 29 possibilités ou 99 bits

edit: oublié que le dernier carré est entièrement déterminé par tous les autres

Vous n'avez pas besoin d'une table de consultation complète pour obtenir une compressibilité optimale. Je crois que les ordinateurs modernes utilisant une table de consultation très raisonnable sont capables de compter le nombre de Sudokus contraints , qui sont des Sudokus avec quelques chiffres déjà en place. En utilisant ceci, voici comment vous encodez (le décodage est similaire).

Correction d'un ordre des carrés. Supposons que le nombre sur le premier carré soit . Mettez comme le nombre de Sudokus dont le premier carré est inférieur à . Soit maintenant le numéro du deuxième carré. Mettez pour être le nombre de Sudokus dont le premier carré est et dont le deuxième carré est inférieur à . Etc. Le nombre codé est .N 1 d 1 d 2 N 2 d 1 d 2 N = ∑ i N $d_1$$N_1$$d_1$$d_2$$N_2$$d_1$$d_2$$N = \sum_i N_i$

Cette méthode de codage est connue sous le nom de codage binomial dans la littérature. Il devrait vous permettre de calculer efficacement (dans un sens réel) l'indice d'un Sudoku donné, et vice versa. Vous n'aurez alors besoin que de bits, comme indiqué ci-dessus (cela signifie que vous pouvez en coder plusieurs avec ce nombre moyen de bits).$72.4$

Edit: La page Wikipedia sur les mathématiques du Sudoku nous aide à clarifier l'image. Un tableau compilé par Ed Russell est également utile .

Il s'avère que si vous ne considérez que les trois premières lignes, il n'y a essentiellement que 44 configurations différentes à considérer. Dans le tableau, vous pouvez trouver le nombre total de configurations équivalentes à l'une quelconque (en supposant que la ligne du haut est 123456789), et le nombre total de finitions de chacune. Étant donné un Sudoku, voici comment nous calculerions son nombre ordinal:

1. Normalisez la configuration de sorte que sa ligne supérieure soit 123456789.
2. Découvrez à laquelle des 44 configurations différentes il appartient. L'article de Wikipedia donne un algorithme pour cela. Le tableau répertorie le nombre de classes d'équivalence pour chaque configuration, ainsi que le nombre d'exécutions.
3. Déterminez le nombre ordinal de la configuration des trois premières lignes à l'intérieur de sa classe d'équivalence. Cela peut se faire de deux manières: soit en utilisant une liste de toutes les classes d'équivalence (il y en a 36288 au total dans toutes les classes d'équivalence), soit en trouvant un moyen de les énumérer rapidement toutes.
4. Normalisez les lignes restantes en triant les lignes 4-6 et 7-9 par leur première colonne, puis en triant ces deux blocs de lignes de manière arbitraire. Cela réduit le nombre de réalisations d'un facteur de 72.
5. Énumérer toutes les complétions ayant la même première colonne. Il y en a environ pour chaque classe d'équivalence, donc cela ne devrait pas prendre trop de temps. Certains compromis sont également possibles ici.$2^{20}$
6. Soit la classe d'équivalence, le nombre ordinal de la configuration des trois premières lignes de la classe d'équivalence, le nombre ordinal de l'achèvement. Il y a deux tableaux (qui peuvent être calculés à partir de la table d'Ed Russell) tels que est le nombre ordinal du Soduko jusqu'au symétries considérées. À partir de cela, vous pouvez calculer le nombre ordinal réel.j k C i , D i C i + j D i + k 9 ! ⋅ $i$$j$$k$$C_i,D_i$$C_i + jD_i + k$$9! \cdot 72$

Cette procédure est réversible et générera un Sudoku à partir d'un nombre ordinal. Notez que l'énumération Sudoku a été réduite à quelques minutes (en 2006; voir la page de discussion de l'article Wikipedia) ou moins, donc je m'attends à ce que sur un ordinateur moderne cette approche soit très pratique et prenne quelques secondes ou moins.

Voici un algorithme qui, je pense, produira un assez bon encodage. Vous avez le sudoku fini que vous souhaitez compresser, et disons que vous en avez déjà encodé certaines cellules, donc il y a un sudoku partiel (pas nécessairement avec une solution unique) avec quelques cellules remplies.

Utilisez un algorithme fixe pour compter le nombre de numéros pouvant être placés dans chaque cellule vide. Recherchez la première cellule lexicographiquement dans laquelle le plus petit nombre de nombres différents peut être placé, et codez lequel de ces nombres y va (donc si une cellule ne peut contenir qu'un 3, 7 ou 9, le 3 est codé par "0" ", le 7 par" 1 "et le 9 par" 2 "). Encodez la séquence résultante à l'aide d'un codage arithmétique (qui prend en compte le nombre de nombres possibles qu'une cellule peut contenir).

Je ne sais pas combien de temps la séquence binaire résultante sera, mais je pense qu'elle est assez courte, surtout si votre algorithme pour compter le nombre de nombres pouvant être placés dans une cellule est raisonnablement sophistiqué.

Si vous aviez un bon algorithme qui estimait la probabilité que chaque cellule contienne un nombre donné, vous pourriez faire encore mieux.

Tous commentaires et critiques sont les bienvenus

Une approche détection compressée semble fournir une plage de bits à bits:$69.96$$171.72$

1.) Le stockage du puzzle implique le stockage de la solution (informations théoriquement).

2.) Le puzzle sudoku le plus difficile semble avoir entrées pour certains qui dépendent de (Par exemple, à ). http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm$t(\alpha)\alpha^{2}$$t(\alpha)$$\alpha$$t(3) ~= 2.44444$$3$

Par conséquent, nous avons un vecteur de longueur qui a au plus entrées non nulles.$P$$\alpha^{4}$$t(\alpha)\alpha^{2}$

3.) Prenez , une matrice avec et qui a des colonnes indépendant et avec des entrées dans . Cette matrice est fixe pour toutes les instances du puzzle. pour certains fixes suffit de UUP.$M$$\beta \times \alpha^{4}$$\beta \ge 2t(\alpha)\alpha^{2}$$2t(\alpha)\alpha^{2}$$\{0,\pm 1\}$$\beta = kt(\alpha)\alpha^{2}$$k$

4.) Trouvez . Celui-ci a entiers qui sont en moyenne délimités parcar les entrées de sont aléatoires avec des entrées dans .$V = MP$$\beta$$|\alpha^{2}|$$M$$\{0,\pm 1\}$

5.) Le stockage de nécessite bits.$V$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

Dans votre cas, et et bits à bits. , le minimum requis fournit environ bits à bits à près comme limite inférieure pour le cas moyen.$\alpha = 3$$t(\alpha) ~= 3$$2kt(\alpha)\alpha^{2}\log{\alpha} = 69.96k$$85.86k$$k=2$$139.92$$171.72bits$

Notez que j'ai renoncé à certaines hypothèses telles que la taille des entrées de et le nombre d'entrées que l'on a en moyenne dans le puzzle.$MP$

$A.)$ Bien sûr, il pourrait être possible de réduire de car dans sudoku la position des entrées clairsemées n'est pas si indépendante les unes des autres. Chaque entrée sur une moyenne entrées chacune dans sa ligne, sa colonne et sa sous-boîte. Cela étant donné, que certaines entrées sont présentes dans une sous-boîte ou une colonne ou une ligne, on peut trouver les chances que les entrées soient présentes dans la même ligne, colonne ou sous-boîte.$k$$2$$t(\alpha)-1$

$B.)$ Chaque ligne, colonne ou sous-boîte est supposée avoir en moyenne entrées non nulles avec un alphabet sans répétition. Cela signifie que certains types de vecteurs avec entrées non nulles ne se produiront jamais, réduisant ainsi l'espace de recherche des solutions. Cela pourrait également réduire . Par exemple, la correction des entrées dans une sous-boîte, une ligne et une colonne réduirait l'espace de recherche de à .$t(\alpha)$$t(\alpha)$$k$$t(\alpha)$${}^{\alpha^{4}}C_{t(\alpha)\alpha^{2}}$${}^{\alpha^{4}-(3\alpha^{2} - 1)}C_{t(\alpha)\alpha^{2}-3t(\alpha)}$

Un commentaire: un modèle Slepian-Wolf arbitrairement corrélé multi-utilisateurs aidera à rendre les entrées indépendantes tout en respectant au moins le critère entrées non nulles. Cependant, si l'on pouvait l'utiliser, il n'est pas nécessaire d'avoir suivi la voie de détection compressée. L'applicabilité de Slepian-Wolf pourrait donc être difficile.$t(\alpha)\alpha^{2}$

$C.)$ À partir d'une analogie de correction d'erreurs, une réduction même significative peut être possible, car dans des dimensions plus élevées, il pourrait y avoir des écarts entre les rayons de la moitié de la distance minimale entravant les boules autour des points de code avec une possibilité de corriger des erreurs plus importantes. Cela devrait également conduire à une réduction de .$k$

$D.)$ $V$ lui-même peut être compressé par entropie. Si les entrées de sont de tailles assez similaires, alors pouvons-nous supposer que la différence entre deux des entrées est au plus ? Ensuite, si le codage des différences entre les entrées suffit, cela supprimera le facteur dans .$V$$O(\sqrt(V_{max})) = O(\sqrt{|\alpha^{2}|})$$2$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

Il serait intéressant de voir si peut être rendu égal ou inférieur à utilisant , , et . Ce serait mieux que bits (ce qui est le meilleur jusqu'à présent dans d'autres réponses) et dans le meilleur des cas mieux que le minimum absolu pour tous les puzzles qui est d'environ bits.$2k$$2$$A.)$$B.)$$C.)$$D.)$$89$$73$

Il s'agit de signaler une implémentation de l'encodage compact de sudoku terminé (similaire à la suggestion de Zurui Wang 14/09/11).

L'entrée est la ligne du haut et les 3 premiers chiffres de la 2e ligne. Ceux-ci sont réduits à 1-9! et 1-120 et combiné à <= 4,4x10 ^ 7. Ceux-ci sont utilisés comme données pour compter lexicographiquement tout le sukokus partiel de 30 chiffres jusqu'à la séquence correspondante. Ensuite, le décompte final jusqu'aux 81 chiffres se fait de la même manière. Ces 3 séquences sont stockées sous forme d'entiers 32 bits de 26 bits maximum, et peuvent donc être compressées davantage. L'ensemble du processus prend environ 3 minutes, les 30 premiers chiffres prenant la plupart du temps. Le décodage est similaire - sauf l'appariement des nombres au lieu des sudokus.

Prochainement - La révision inclut les 3 premiers chiffres de la 2ème ligne dans l'énumération des complétions à 30 chiffres (2ème code 32 bits), les comparaisons avec l'énumération Jarvis (Jscott, 3/1615)

J'irais avec l'analyse simple suivante:

Chaque valeur peut être stockée sur 4 bits (de 1 à 9, ces trois bits permettent même de 0 à 16)

Si nous avons envisagé de stocker la solution ENTIÈRE (non optimale), ayant valeurs. 3 bits chacun = 243 bits.$9 \times 9 = 81$

Cependant, comme les règles que le sudoku résolu doit suivre, le stockage de chaque bit est en fait redondant. Cependant, puisque l'ordre est important, vous devez stocker les 8 premières valeurs dans chaque ligne (déterminant ainsi la 9ème valeur), pour 8 lignes (déterminant ainsi la dernière ligne). Cela réduit le sudoku à pour 3 bits, 192 bits (24 octets).$8 \times 8$

Je suppose que je pourrais le réduire à:

$b = \lceil \log_2(v) \rceil (n-1)$

où

$v$ = plage de valeurs (j'ai souvent vu 0-5 sudokus)

$n$ = nombre de lignes / colonnes

Edit: Neo Style: Je connais le latex.

Ce nombre est différent pour chaque Sudoku. L'une des règles du Sudoku est qu'il a exactement une solution.

Donc, si vous regardez un exemple, c'est la quantité minimale de données que vous devez stocker.

Si vous travaillez du côté opposé, vous pouvez supprimer chiffre par chiffre et exécuter un solveur sur le résultat pour voir s'il a toujours exactement une solution. Si c'est le cas, vous pouvez supprimer un autre chiffre. Sinon, vous devez restaurer ce chiffre et en essayer un autre. Si vous ne pouvez pas, vous avez trouvé un minimum.

Étant donné que la plupart des puzzles commencent pour la plupart à vide, un encodage de la longueur d'exécution donnera probablement de bons résultats.