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

28

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.log2(981))=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?

orlp
la source
3
Y a-t-il vraiment une différence qualitative entre omettre le 9e numéro dans une 3x3, une ligne ou une colonne et simplement stocker le sudoku minimal avec des espaces vides qui a cette solution unique? «n'a pas besoin de prendre en charge les cellules vides» est un peu un hareng rouge si la solution optimale en a nécessairement besoin.
Wooble
19
Parce qu'il y a 6,67 × 10 ^ 21 sudoku résolu («QSCGZ» 2003; Felgenhauer et Jarvis 2005) et log_2 (6,67 × 10 ^ 21) = 72,4…, une borne inférieure est de 73 bits (même si vous utilisez la recherche de table énorme) . Si vous n'avez pas à distinguer des solutions essentiellement identiques en termes de symétrie, cette borne inférieure ne s'applique pas.
Tsuyoshi Ito,
9
Cette question ferait un bon concours de programmation.
Peter Shor
1
La borne inférieure analogue pour des solutions essentiellement identiques est de 33 bits.
Charles
3
Pourquoi avez-vous besoin d'une table de consultation? Vous pouvez simplement énumérer les solutions Sudoku une par une jusqu'à atteindre le nombre souhaité.
Zirui Wang

Réponses:

19

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.

David Eppstein
la source
4
Vous pouvez également réduire le nombre de choix lorsque vous remplissez la sixième case 3x3. Cette case devient 4,3,2 / 3,2,1 / 2,1,1 pour un total de 83 bits, si je la calcule correctement.
Peter Shor
@Peter - non. Les 3 chiffres à droite pourraient être les mêmes que les chiffres ci-dessus. Vous ne savez pas que tous sont distincts. Les numéros uniques les plus assurés sont 3, donc la première case est un choix parmi six articles. (Cet endroit est un exemple. C'est vrai pour les autres aussi.)
Hogan
@ David - d'après mon commentaire à Peter, je ne pense pas que vos chiffres soient faux. Dans la deuxième case que vous avez, 6 5 4 4 3 2 3 2 1je pense que cela doit être 6 5 4 6 5 4 3 2 1pour le pire des cas.
Hogan
Hogan, non, voir la partie de ma réponse concernant "une fois que vous avez rempli une ligne ou une colonne de la boîte, vous pouvez toujours choisir la ligne ou la colonne suivante à remplir pour être celle dans laquelle il y a au plus quatre valeurs possibles "
David Eppstein
@David - Permet d'étiqueter les 3 x 3s 1,1 1,2 1,3 de gauche à droite de haut en bas. Étiquetons les carrés A - Je vais de gauche à droite de haut en bas. L'emplacement D dans 1,3 connaît 3 nombres dans le 3x3 dans lequel il se trouve (A, B, C) et il connaît 3 nombres dans 1,2 (D, E, F) mais il ne sait pas que ces 6 nombres sont différents. Il peut s'agir des mêmes 3 chiffres des cases 3,1 et 2,1, il y a donc MAX 6 choix.
Hogan
13

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

monstre à cliquet
la source
Très agréable!! Permettez-moi d'ajouter qu'il n'est pas clair pour moi que vous pourriez jamais atteindre ces pires possibilités pour une vraie solution de Sudoku (surtout si vous utilisez un algorithme sophistiqué qui utilise certaines techniques de Sudoku pour affiner les possibilités pour lesquelles les nombres peuvent aller dans une cellule ).
Peter Shor
@peter mais vous devez ajouter ceux qui se rétrécissent en fr et le décodage et j'ai réalisé que si vous devez en choisir un et ne pas fixer l'ordre (le plus simple mais pas vraiment optimal), vous devez également l'ajouter à l'encodage
ratchet freak
Non, si vous utilisez le même algorithme pour déterminer la meilleure cellule dans la procédure d'en- et de décodage, il donnera la même cellule (car il travaille sur les mêmes données), donc les procédures d'en- et de décodage seront synchronisées, et vous n'avez pas à ajouter la commande à l'encodage. Cette idée fait également fonctionner l'algorithme de compression de données LZW.
Peter Shor
Je pense que le minimum de bits requis pour stocker un puzzle sudoku valide n'est pas une fonction calculable (Kolmogorov). Cependant, les 103 bits de Peter / ratchet semblent une bonne limite.
Marzio De Biasi
2
@Vor: Techniquement, la machine Turing qui génère le nombre correct de bits quand un puzzle sudoku est donné en entrée est finie car l'ensemble d'entrée est fini, donc "combien de bits sont nécessaires pour décrire ce puzzle" est "trivialement" calculable. Je dis que nous pourrions réellement trouver une telle machine de Turing explicitement (en principe, les calculs prendraient beaucoup trop de temps), car cela ne peut pas être plus difficile que de calculer un préfixe fini d'un nombre Omega.
Aaron Sterling
5

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 id1N1d1d2N2d1d2N=iNi

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.220
  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 ! 72ijkCi,DiCi+jDi+k9!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.

Yuval Filmus
la source
2
Est-il possible de compter efficacement les solutions au sudoku contraint? Il est # P-complet si vous généralisez la taille et autorisez les blancs dans des endroits arbitraires.
Tsuyoshi Ito
2
Comme je l'ai mentionné dans ma réponse, le codage arithmétique atteindra une compression presque optimale pour ce scénario.
Peter Shor
1
Vous avez peut-être raison, mais votre affirmation implique que le nombre de grilles de sudoku (6,67 × 10 ^ 21) est facile à calculer sur un ordinateur moderne. Il est en effet possible de calculer, mais est-ce facile?
Tsuyoshi Ito du
2
J'ai eu cette impression d'un des articles décrivant comment faire le calcul. Vous pouvez même calculer certaines des données "plus lourdes" du prétraitement et les stocker dans une table de taille raisonnable - les gains de vitesse peuvent être spectaculaires. Pour autant que je m'en souvienne, cela ne leur a pris que quelques heures, et cela il y a quelques années. Supposons maintenant que vous utilisiez une table pour la rendre 1000 fois plus rapide. De plus, à chaque étape, le nombre diminue de façon exponentielle, donc la plupart du travail est probablement concentré au premier stade.
Yuval Filmus
1
@tsuyoshi Je crois qu'il existe une version / extension de BDD qui rend le calcul relativement simple - je devrais faire un peu de recherche pour cela, mais je sais qu'ils ont été utilisés pour des problèmes de comptage combinatoire assez compliqués.
Steven Stadnicki
4

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.

Peter Shor
la source
3

Tous commentaires et critiques sont les bienvenus

Une approche détection compressée semble fournir une plage de bits à bits:69.96171.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.htmt(α)α2t(α)αt(3) =2.444443

Par conséquent, nous avons un vecteur de longueur qui a au plus entrées non nulles.Pα4t(α)α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β×α4β2t(α)α22t(α)α2{0,±1}β=kt(α)α2k

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β|α2|M{0,±1}

5.) Le stockage de nécessite bits.Vβlogα2=2kt(α)α2logα

Dans votre cas, et et bits à bits. , le minimum requis fournit environ bits à bits à près comme limite inférieure pour le cas moyen.α=3t(α) =32kt(α)α2logα=69.96k85.86kk=2139.92171.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.k2t(α)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(α)t(α)kt(α)α4Ct(α)α2α4(3α21)Ct(α)α23t(α)

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(α)α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 .VO((Vmax))=O(|α2|)2βlogα2=2kt(α)α2logα

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.2k2A.)B.)C.)D.)8973

contre
la source
1

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)

jscott
la source
1
Pour info: si vous avez créé deux comptes et que vous souhaitez les fusionner, consultez cstheory.stackexchange.com/help/merging-accounts
DW
0

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

Je suppose que je pourrais le réduire à:

b=log2(v)(n1)

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

n = nombre de lignes / colonnes

Edit: Neo Style: Je connais le latex.

Alpha
la source
-2

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.

Aaron Digulla
la source
Cette approche gourmande n'atteint pas nécessairement le minimum, vous devrez peut-être sélectionner soigneusement le chiffre à supprimer à chaque étape.
Diego de Estrada
Ce n'est qu'un exemple. Google pour les "générateurs de puzzles sudoku" pour obtenir des générateurs plus sophistiqués.
Aaron Digulla
5
Je ne vois vraiment pas pourquoi vous vous attendriez à ce que cela fonctionne particulièrement bien. Cela semble être un sentiment instinctif plutôt qu'une réponse.
Joe Fitzsimons,