La respuesta a la pregunta depende de la definición de cuándo las soluciones similares se consideran diferentes.
Para la consideración de todas las soluciones posibles, dos soluciones se consideran distintas si alguno de sus valores de celda (81) correspondientes difiere. Las relaciones de simetría entre soluciones similares se ignoran, por ejemplo, las rotaciones de una solución se consideran distintas. Las simetrías juegan un papel importante en la estrategia de enumeración, pero no en el recuento de todas las soluciones posibles.
Considerando una cuadrícula de 9 × 9, el conjunto completo de combinaciones fue de 6.670.903.752.021.072.936.960 (6,67 × 1021) soluciones distintas. Este estudio fue realizado por Felgenhauer y Jarvis, quienes analizaron las permutaciones de la banda superior utilizada en soluciones válidas.
- ¿Por qué el algoritmo ikj es más rápido que el algoritmo ijk para la multiplicación de matrices?
- ¿Por qué el ensacado funciona tan bien para los árboles de decisión, pero no para los clasificadores lineales?
- ¿Cuál es el mejor curso para algoritmos y estructuras de datos?
- Dado un número N y un flujo continuo de enteros de entrada, ¿podría encontrar dos números en el flujo cuya suma fuera el primer número N?
- ¿Cuál es la importancia del algoritmo en informática?
Una vez que se identificaron las simetrías de Banda 1 y las clases de equivalencia para las soluciones de cuadrícula parcial, se construyeron las terminaciones de las dos bandas inferiores y se contaron para cada clase de equivalencia.
Sumar las terminaciones sobre las clases de equivalencia, ponderadas por el tamaño de la clase, da el número total de soluciones como 6.670.903.752.021.072.936.960 .
Dos cuadrículas válidas son esencialmente las mismas si una puede derivarse de la otra.
Las siguientes operaciones siempre traducen una cuadrícula de Sudoku válida en otra cuadrícula válida: (los valores representan permutaciones para el Sudoku clásico)
- Reetiquetado de símbolos (¡9!)
- Permutaciones de banda (3!)
- Permutaciones de fila dentro de una banda (3! 3)
- Permutaciones de pila (3!)
- Permutaciones de columna dentro de una pila (3! 3)
- Reflexión, transposición y rotación (2). (Dada cualquier transposición o rotación de un cuarto de vuelta en conjunción con las permutaciones anteriores, se puede producir cualquier combinación de reflexiones, transposiciones y rotaciones, por lo que estas operaciones solo contribuyen con un factor de 2.)
Estas operaciones definen una relación de simetría entre cuadrículas equivalentes. Excluyendo el reetiquetado, y con respecto a los 81 valores de celda de la cuadrícula, las operaciones forman un subgrupo del grupo simétrico S base 81, de orden 3! ^ 8 × 2 = 3,359,232.
Se ha demostrado que cualquier operación fija en los mosaicos que siempre traduce una cuadrícula Sudoku válida en otra cuadrícula válida puede generarse a partir de las operaciones enumeradas anteriormente (excluyendo el reetiquetado).
Para una solución, el conjunto de soluciones equivalentes a las que se puede llegar utilizando estas operaciones (excluyendo el reetiquetado), forman una órbita del grupo simétrico. Jarvis / Russell calculó el número de soluciones esencialmente diferentes (simétricamente distintas) como 5,472,730,538 .
Espero que esto ayude.
