Problema de conteo:posibles tablas de sudoko?

Question

Estoy trabajando en un solucionador de sudoko (python).Mi método consiste en utilizar un árbol de juegos y explorar posibles permutaciones para cada conjunto de dígitos mediante el algoritmo DFS.

Para analizar el problema, quiero saber cuál es el recuento de posibles válido e inválido ¿Tablas de sudoko?

-> una mesa de 9*9 que tiene 9 uno, 9 dos, ..., 9 nueve.

(esto no es un duplicado exacto de esta pregunta)

mi solución es:

1- Primero seleccione 9 celdas por 1s:(*)

2- y como (1) para otros dígitos (cada vez, se eliminarán 9 celdas de las celdas disponibles restantes):C(81-9,9), C(81-9*2,9) ....=

3- ¡finalmente multiplica el resultado por 9!(permutación de 1s-2s-3s...-9s en (*))

esto no es igual a la respuesta aceptada de esta pregunta pero los problemas son equivalentes.¿qué hice mal?

Answer 1

El número de cuadrículas válidos solución sudoku para el estándar de rejilla 9 × 9 se calcula Bertram Felgenhauer y Frazer Jarvis en 2005 para ser 6.670.903.752.021.072.936.960.

de Matemáticas Sudoku | fuente

Creo que el problema con su solución es que la supresión de 9 celdas cada vez a partir de células disponibles no necesariamente crea una cuadrícula válido. Lo que quiero decir es simplemente la supresión de 9 celdas no será suficiente.

Esa es la razón por 81! / (9!) ^ 9 es el número mucho más grande de soluciones válidas reales.

EDIT:

permutaciones con elementos repetidos

Sus soluciones es casi correcta si desea que todas las mesas no sólo válida tablas de sudoku.

Hay una fórmula:

(a + b + c + ...)! / [¡una! ¡si! ¡do! ....]

Supongamos que hay 5 chicos y 3 chicas y tenemos 8 asientos luego de varias maneras diferentes en las que pueden asiento es

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

Su problema es análogo a éste.

Hay 9 1s, 2s ... 9 9 9s. y 81 lugares

Así que la respuesta debe ser (9 + 9 + ...)! / (9!) ^ 9

Ahora bien, si se multiplican de nuevo en un 9! entonces esto va a añadir los arreglos duplicados al número barajando ellos.

Answer 2

De acuerdo con este artículo Wikipedia (o este OEIS secuencia ), hay más o menos 6,6 * 10 ^ 21 plazas sudoku diferentes.

Answer 3

Lo que hizo mal fue el último paso: no se debe multiplicar el resultado por 9!. Usted ya ha contado todas las plazas posibles.

Esto no le ayuda mucho cuando se cuentan los posibles Sudoku-tables. Otra cosa que podría hacer es contar las mesas en las que la "fila de condición" se tiene:. Que es sólo (9!)^9, ya que acaba de elegir una permutación de 1..9 para cada fila

Todavía más cerca del Sudoku-problema está contando cuadrados latinos . cuadrado latino tiene que satisfacer tanto la "fila de condición" y "columna condición". Eso ya es un problema difícil y no se conoce ninguna fórmula forma cerrada. Sudoku es un cuadrado latino con el "subcuadrado condición" adicional.