Quelle est l'arithmétique derrière la grille vierge de Sudoku?

Question

Sudoku Blank Grid est utilisé dans la symétrie du Sudoku,il s'agit de rangées et de colonnes de 4×4,16×16 et plus avec des grilles petites et variantes.

Les puzzles de Sudoku peuvent être étudiés mathématiquement pour répondre à des questions telles que “Combien de grilles de Sudoku complètes?”, “Quel est le nombre minimum d'indices dans un vrai puzzle?” et “Comment les grilles de Sudoku peuvent-elles être symétriques?” en utilisant les théories combinatoires et de groupe.

Les principaux résultats sont ceux du Sudoku classique, le nombre de grilles remplies est 6,670,903,752,021,072,936,960 (6.67×1021), lequel, tout en conservant la validité de la transformation se réduit à 5,472,730,538 groupes sensiblement différents.

Il y a 26 types de symétrie, mais on ne les trouve que dans environ 0.005% de toutes les grilles remplies.

Un puzzle avec une solution unique doit avoir au moins 17 solutions, et pour chaque réseau résolu il n'y a pas plus de 21 solutions. Le plus grand puzzle minimum trouvé a 40 des indices.

Des résultats similaires sont connus pour des variantes et des grilles plus petites. Des résultats précis ne sont pas connus pour les Sudokus plus que la grille classique 9 × 9, bien qu'il existe des estimations considérées comme assez précises.

Solutions de calcul au Sudoku

Une question intéressante est, combien de façons un 9 par 9 La grille de Sudoku doit être remplie pour satisfaire la règle unique?

En d'autres termes, combien de solutions de Sudoku différentes existent? Nous décrivons la méthode utilisée par Bertram Felgenhauer et Fraser Jarvis au début 2006 pour calculer ce nombre.

Maintenir le niveau de notre langue, nous appelons trois rangées de blocs des bandes d'une grille et trois colonnes de piles de blocs. Une cellule de cette ligne et la colonne j sont considérées comme étant à (je,j).

Nous appelons le nombre de grilles individuelles Sudoku N. Premier, nous appelons les blocs de grille comme suit:

Combien y a-t-il de façons de remplir B1 de manière valide? Puisqu'il y a 9 caractères pouvant remplir B1, un dans chaque cellule, C'est 9 options pour la première cellule.

Pour chacun de ces 9 Options, il y a 8 options pour la deuxième cellule. Pour chacun de ces 8 Options, il y a 7 gauche pour la troisième cellule.

Fondamentalement, on calcule le nombre de permutations de 9 personnages: combien de façons pouvons-nous placer 9 personnages dans 9 des endroits, ou combien de façons nous pouvons commander 9 des choses.

Il y a 9 façons de remplir B1. Commencer avec un bloc B1 valide, nous pouvons obtenir n'importe quel autre bloc B1 valide en remarquant ou en réorganisant les numéros.

Alors, la première hypothèse simplificatrice que nous pouvons faire est que B1 est rempli de nombres 1, 2, 3, …, 9 en ordre, comme indiqué ci-dessous.

Maintenant, nous pouvons calculer combien de fins de grille réelles ce B1 particulier a: appelons-le N1. Le nombre total de grilles de Sudoku réelles est N1×9!, donc N1=N/9!…

Considérons les façons de remplir les premières lignes en B2 et B3. Puisque 1, 2 et 3 apparaissent dans la première ligne de B1, ces nombres ne peuvent pas apparaître dans les autres lignes.

Donc, seuls les chiffres 4, 5, 6, 7, 8 et 9 des deuxième et troisième rangées de B1 peuvent se rencontrer dans la première rangée de B2 et B3.

Énumérez toutes les manières possibles de remplir les premières lignes de B2 et B3, jusqu'à réorganiser les numéros dans chaque bloc. Pointe: Il y a dix façons de faire cela pour que l'échange de B2 et B3 ces dix façons vous ait donné dix autres façons, un total de vingt.

Nous appelons deux de ces possibilités pure top lines: quand les chiffres {4,5,6}, comme dans la deuxième rangée de B1, sont stockés ensemble dans B2, et des chiffres {7,8,9}, comme dans la troisième rangée de B1, sont stockés ensemble dans B3, et une version modifiée de ceci.

Les autres possibilités sont des top lines mixtes, pendant qu'ils mélangent les ensembles {4,5,6} et {7,8,9} lorsqu'il est utilisé pour remplir les premières lignes de B2 et B3.

Étant donné ces vingt possibilités pour la première ligne de la grille (jusqu'à réorganiser les numéros dans chaque bloc), nous pouvons comprendre comment remplir la première ligne.

Réfléchissez à la façon dont vous pouvez compléter la première bande en commençant par la rangée supérieure pure 1,2,3;{4,5,6};{7,8,9}.

(Remarque: Nous écrivons un,b,c pour désigner un triplet ordonné de nombres et {une,b,c} pour les désigner dans n'importe quel ordre.)

Combien y a-t-il de possibilités totales, compter les différents ordres de nombres dans chaque ligne en B2 et B3? Ce nombre est-il le même que pour l'autre rangée supérieure pure, 1,2,3;{7,8,9};{4,5,6}?

Rappelles toi, nous voulons garder B1 fixe car nous avons déjà pris en compte le nombre de grilles qui peuvent être obtenues en réétiquetant les neuf chiffres qu'il contient.

Il s'avère qu'il y a (3!)6 façons de compléter la première bande en commençant par la pure rangée du haut 1,2,3;{4,5,6};{7,8,9}.

C'est parce que nous sommes obligés de mettre {7,8,9};{1,2,3} au deuxième rang en B2 et B3 et {1,2,3};{4,5,6} au troisième rang, puis nous pouvons réorganiser les trois chiffres dans chacune des six lignes de B2 et B3 pour obtenir toutes les configurations.

La réponse est la même pour l'autre rangée supérieure pure, puisque dans ce cas, tout ce que nous avons fait est d'échanger B2 avec B3.

Les cas des rangs supérieurs mixtes sont plus compliqués. Considérons la rangée du haut 1,2,3;{4,6,8};{5,7,9}. Ceci peut être complété jusqu'à la première bande comme dans l'image suivante, où un, b, et c sont les nombres 1, 2, 3 dans n'importe quel ordre.

Après avoir sélectionné un, b et c sont les deux nombres restants dans n'importe quel ordre, car ils sont dans la même ligne.

Puisqu'il y a trois options pour un, et trois chiffres dans chacun des six ensembles de B2 et B3 peuvent être ignorés pour obtenir différentes pages de couverture valides, le nombre total de configurations dans ce cas est 3×(3!)6.

Vous pouvez également travailler sur chacun des dix-sept cas restants au premier rang pour obtenir le même nombre.

Nous avons maintenant le nombre de pages de couverture possibles défini par B1: c'est 2×(3!)6+18×3×(3!)6=2612736, où la première partie de la somme est le nombre de premières pages complétées à partir des rangées supérieures nettes et la seconde est le nombre de premières pages complétées à partir des rangées supérieures mixtes.

Au lieu de calculer le nombre d'achèvements de première page de chacun de ces 2612736 fonctionnalités, Felgenhauer et Jarvis ont déterminé quelles pages de couverture avaient le même nombre de premières pages complétées à partir du blanc supérieur.

Cette analyse permet de réduire le nombre de pages de couverture à prendre en compte lors du calcul.

Voici quelques opérations qui laissent le nombre de terminaisons de la première grille de plage inchangé: remarquant les chiffres, écouter l'un des blocs de la première plage, écouter les colonnes dans n'importe quel bloc et écouter les trois lignes de la plage. Avec l'un de ces changements B1, nous pouvons re-marquer les chiffres pour restaurer sa forme standard.

Organiser B1, B2 et B3 conservent le nombre de fins de grille, parce que si nous commençons avec n'importe quelle grille de Sudoku, la seule façon de le garder réel est de marquer B4, B5, B6 et B7, B8, B9 respectivement pour que les piles restent les mêmes.

En d'autres termes, chaque terminaison de grille de première page réelle donne exactement une terminaison de grille de première page réelle, à savoir. n'importe quel B1, B2, Permutation B3.
Assurez-vous que lorsque vous changez B2 en B3 dans la prochaine grille de Sudoko, la seule façon de garder la grille valide est de changer B5 en B6 et B7 en B8. Cela gardera les piles identiques, bien que leur emplacement ait changé.

Si vous avez une grille de Sudoku valide et que vous sautez des colonnes dans l'un des B1, B2 et B3, qu'auriez-vous à faire avec les colonnes du reste de la grille de Sudoku pour qu'elle reste valide? Par exemple, si vous avez changé de colonne 1 et 2 de B2 sur la grille ci-dessus, comment répareriez-vous la grille résultante afin qu'elle satisfasse à la règle unique?

Le dernier exercice nous indique que chaque remplissage de la grille de première ligne donne un remplissage unique de la grille de première ligne avec des colonnes sautées à l'intérieur des blocs.

De telles considérations nous permettent de réduire le nombre de pages de couverture spécifiques à prendre en compte lors du comptage.

Après Felgenhauer et Jarvis, nous faisons défiler les colonnes B2 et B3 afin que les entrées de la rangée supérieure de chaque colonne soient dans l'ordre croissant, puis échangez B2 et B3 si nécessaire pour que la première entrée B2 soit plus petite que l'entrée B3.

C'est ce qu'on appelle l'abréviation lexicographique.

Étant donné que chacun des deux blocs a 6 réarrangements de colonnes et deux façons de réarranger les blocs, la sténographie lexicographique nous dit que, étant donné la première page, il y a 62×2=72 autres pages de couverture avec le même nombre de fins de grille.

Alors maintenant, nous n'avons que 2612736/72=36288 premières pages à considérer.

Pour chacune de ces possibilités, regardons les réarrangements des trois blocs supérieurs: il y a 6. Pour chacun d'eux, il y a 63 réarrangements de colonnes dans chaque bloc.

Après avoir effectué ces opérations, nous remarquons pour remettre B1 dans sa forme standard.

De même, nous pouvons remplacer les trois premières lignes du groupe et re-marquer pour ramener B1 à une forme standard. Ces opérations permettent d'économiser le nombre de remplissages de la grille de première ligne.

Felgenhauer et Jarvis ont utilisé un programme informatique pour déterminer que ces opérations réduisent le nombre de premières pages à considérer à partir de 36288 à seulement 416.

Considérons ce premier groupe.

Effectuez diverses opérations dessus qui enregistrent son nombre de fins de grille. Vous pouvez commencer par ce qui suit: Échangez la première et la deuxième rangée. Re-marquez-le pour que B1 soit dans sa forme standard. Réduire lexicographiquement cette grille.

L'essentiel est que le groupe avec lequel vous avez commencé et l'autre groupe avec lequel vous avez terminé aient le même nombre de complétions jusqu'à la grille de Sudoku complète.

Ainsi, au lieu de calculer le nombre de fins de grille pour chacun de ces groupes, nous ne pouvons le calculer que pour l'un d'entre eux.

Il y a plus d'étapes qui réduisent le nombre de grilles à considérer. Si nous avons une paire de chiffres {une,b} dans une colonne avec a dans une ième rangée et b dans une jième rangée, et la même paire dans une autre colonne avec b dans une ième rangée et a dans une jième rangée, chaque paire aura une bande avec le même nombre de fins de grille que l'original.

C'est parce que chaque paire se trouve dans la même colonne, et quand les deux sont changés en même temps, une seule règle est enregistrée, qui satisfait également les lignes impliquées.

Par exemple, regarde les chiffres 8 et 9 dans les sixième et neuvième colonnes de l'exemple ci-dessus. Considérez tous les cas possibles de cette gauche Felgenhauer et Jarvis avec 174 du premier 416 groupes pour continuer.

Ils ont également considéré d'autres configurations du même ensemble de nombres se trouvant dans deux colonnes ou lignes différentes, qui peuvent être omis à l'intérieur de leurs colonnes ou lignes, laissant le nombre de terminaisons de grille invariant.

Cela a réduit le nombre de premières pages à 71, et la recherche de chacun d'eux 71 cas leur ont fait comprendre qu'il n'y a en fait que 44 pages de garde dont le nombre de complétions de grille à retrouver.

Chacun de ces 44 les bandes ont le même nombre de fins que la grille complète.

Soit C l'un de ces 44 rayures. Ensuite, vous pouvez calculer le nombre de façons dont C peut compléter la grille complète du Sudoku: appelez ça nc.

Nous avons également besoin du nombre de pages d'accueil mC qui partagent ce nombre de terminaisons nC de la grille. ensuite, le nombre total de grilles de Sudoku est juste N=ΣCmCnC, ou la somme de mCnC pour tous 44 rayures.

Felgenhauer et Jarvis ont écrit un programme informatique pour effectuer les calculs finaux.

Ils ont calculé le nombre d'achèvements valides N1 avec B1 sous une forme standard, commençant par 44 voies. Puis ils ont multiplié ce nombre par 9! pour obtenir une réponse.

Ils ont constaté que le nombre de possibilités 9 par 9 Les grilles de Sudoku sont N=6670903752021072936960, qui est d'environ 6.671×1021.

 

Crédit d'article et d'image:

http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html

 

 

0
Ephraim Iyodo 2 années 0 Réponses 5238 vues 0

Laisser une réponse

Brillamment sûr et Centré sur l'étudiant Plateforme d'apprentissage 2021