problème de comptage: tables possibles de sudoku?

Question

Je travaille sur un solveur sudoko (python). ma méthode utilise un arbre de jeu et d'explorer les permutations possibles pour chaque ensemble de chiffres par DFS algorithme.

pour analyser problème, je veux savoir quel est le nombre de possibles valides et non valides Tables sudoko?

-.> Une table 9 * 9 qui ont 9 un, deux 9, ..., 9 neuf

(ce n'est pas double exact cette question )

ma solution est:

1- Sélectionnez d'abord 9 cellules pour 1s: (*)

2- et analogues (1) pour les autres chiffres (à chaque fois, 9 cellules seront supprimées de cellules restant disponibles): C (81-9,9), C (81-9 * 2,9) .... =
< br> 3- multiplier enfin le résultat par 9! (Permutation de 1s-2s-3 ...- 9s en (*))

ce n'est pas égal à réponse acceptée de cette question mais les problèmes sont équivalents. qu'est-ce que je fait de mal?

Answer 1

Le nombre de grilles de solution Sudoku valides pour la grille standard de 9 x 9 a été calculé par Bertram Felgenhauer et Frazer Jarvis en 2005 pour être 6.670.903.752.021.072.936.960.

Mathématiques de Sudoku | source

Je pense que votre problème avec la solution est que la suppression de 9 cellules à chaque fois à partir de cellules disponibles ne crée pas nécessairement une grille valide. Ce que je veux dire est que la suppression de 9 cellules ne suffira pas.

C'est pourquoi 81! / (9!) ^ 9 est beaucoup plus grand que nombre des solutions valables réelles.

EDIT:

Permutations avec des éléments répétés

Vos solutions est presque correct si vous voulez que toutes les tables non seulement des tables valides sudoku.

Il existe une formule:

(a + b + c + ...)! / [une! b! c! ....]

Supposons qu'il y ait 5 garçons et 3 filles et nous avons 8 sièges alors nombre de différentes façons dont ils peuvent le siège est

(5 + 3)! / (5! 3!)

Votre problème est analogue à celui-ci.

Il y a 9 1s, 9 2s ... 9 9s. et 81 places

réponse devrait être (9 + 9 + ...)! / (9!) ^ 9

Maintenant, si vous multipliez par 9 à nouveau! alors cela va ajouter des arrangements en double du nombre en les mélangeant.

Answer 2

Selon cet article de Wikipedia (ou cette séquence OEIS ), il y a à peu près 6,6 * 10 ^ 21 différents carrés de sudoku.

Answer 3

Ce que vous avez mal était la dernière étape: vous ne devriez pas multiplier la réponse par 9!. Vous avez déjà compté toutes les cases possibles.

Cela ne vous aide pas beaucoup lorsque l'on compte les possibles Sudoku-tables. Une autre chose que vous pouvez faire est de compter les tables où la « ligne-condition » est vérifiée:. Qui est juste (9!)^9, parce que vous choisissez simplement une permutation de 1..9 pour chaque ligne

Encore plus proche de la Sudoku problème est carrés latins . carré latin doit satisfaire à la fois la « ligne condition » et « état de colonne ». C'est déjà un problème difficile et aucune formule de forme fermée est connue. Sudoku est un carré latin avec le plus "sous-carré condition".