Mi método combinatorio simple para enumerar todas las cuadrículas de soluciones de Sudoku

¿Cómo es posible que existan cuadrículas de soluciones de Sudoku? La respuesta correcta es:$6,670,903,752,021,072,936,960$o$6,671E21$como fue probado$12$¡hace años que! ¿O era?

Su prueba nunca enumeró realmente las soluciones e involucró una gran cantidad de tiempo de computadora central para calcular, lo que implicó una gran cantidad de casos de prueba reducidos para completar los cálculos en tiempo humano.

Cuando dijeron y leí que no era posible una respuesta combinatoria simple, inmediatamente pensé: "Bueno, ya conozco una".

Así que ejecuté los números en una calculadora pero NO obtuve su solución y no puedo ver una falla en la mía.

No puedo seguir la solución hasta el final ya que tengo que confiar en los resultados de su computadora. Le envié esto al autor pero no recibí respuesta, lo cual no es sorprendente ya que no hay lugar para probar que estoy equivocado. He esperado y revisado mi método el tiempo suficiente para mantener mi solución.

Dado que esto debe expresarse en forma de pregunta, "¿Qué tiene de malo mi solución?"

Entonces, aquí está lo que todos hemos estado esperando:

Mi forma combinatoria simple de enumerar cuadrículas de solución de Sudoku

Nota: El problema que estamos tratando de resolver aquí es para N0, que es el número máximo de cuadrículas de respuestas Sudoku correctas. Por lo tanto, no hay discusión sobre el intercambio para obtener soluciones equivalentes.

Hay tres bandas, filas$1$-$3$,$4$-$6$, y$7$-$9$y tres columnas de pilas$1$-$3$,$4$-$6$, y$7$-$9$en una cuadrícula de Sudoku. Comenzaremos con una discusión sobre la primera banda, que son las tres filas superiores.

Las tres bandas y pilas dividen la Cuadrícula de Sudoku en$9$Bloques, etiquetados$B_1$,$B_2$, y$B_3$en banda$1$,$B_4$,$B_5$, y$B_6$en banda$2$, y$B_7$,$B_8$, y$B_9$en banda$3$, que también significa$B_1$,$B_4$, y$B_7$en pila$1$,$B_2$,$B_5$, y$B_8$en pila$2$, y$B_3$,$B_6$, y$B_9$en pila$3$.

Sustitución de números por posiciones de símbolos

Sustituiremos el$9$números utilizados en la$81$cuadrados para salir$B_1$con la siguiente cuadrícula:

|1 2 3|
|4 5 6|     Note: 9! cases
|7 8 9|

Con esto ahora podemos pensar en los números no como números sino como posiciones de símbolos, donde$9!$diferentes soluciones usarán las mismas posiciones de símbolo para todos los$81$cuadrícula.

Descripción de restricciones de fila para una banda

Digamos que queremos completar Band1 y comenzamos en lo que yo llamo un patrón completamente normal para$B_1$Fila$1$, como sigue:

Row 1: |1 2 3|     |     |    Note: The symbol positions in B2 and
Row 2: |4 5 6|1 2 3|     |    B3 only describe the row they are in,
Row 3: |7 8 9|     |1 2 3|    not the column positions.

Dado esto como punto de partida, ¿cómo completamos las posiciones de los símbolos desde el$B_1$Fila2, en$B_2$? Si tratamos de ponerlos en la Fila1, tenemos un problema cuando llegamos a B3 porque necesitaríamos usar posiciones ya ocupadas. Entonces, tenemos que seguir el mismo patrón All-Normal que$B_1$Fila1, lo que da como resultado lo siguiente:

Row 1: |1 2 3|     |4 5 6|    Note: The symbol positions in B2 and
Row 2: |4 5 6|1 2 3|     |    B3 only describe the row they are in,
Row 3: |7 8 9|4 5 6|1 2 3|    not the column positions.

Entonces$B_1$Fila$3$sigue el patrón Todo-Normal para llenar los espacios en blanco.

Un símbolo normal se define como un símbolo que va hacia abajo hasta el segundo bloque y hacia abajo hasta el tercer bloque, donde si va por debajo de la parte inferior se envuelve en la parte superior de la banda.

Símbolo anormal se define como un símbolo que desciende dos hasta el segundo bloque y dos hasta el tercer bloque, con envoltura.

Un patrón totalmente normal es donde los nueve símbolos son normales.

Ahora veamos un caso con un símbolo anormal de$B_1$Fila$1$, elegiremos$3$:

Row 1: |1 2 3|     |     |    Note: The symbol positions in B2 and
Row 2: |4 5 6|1 2  |    3|    B3 only describe the row they are in,
Row 3: |7 8 9|    3|1 2  |    not the column positions.

Aquí tenemos el símbolo$3$bajando$2$, y abajo$2$con una envoltura, en lugar de abajo$1$y abajo$1$.

Ahora bien, si tratamos de completar$B_1$Fila$2$y Fila$3$en$B_2$y$B_3$encontramos que tenemos un problema similar, a menos que hagamos lo mismo que Fila$1$y elija uno de los tres símbolos para que sea anormal. Lo mismo se puede decir acerca de tener dos anormales de Row$1$, necesitamos repetir esto para las otras dos Filas. Y finalmente tenemos el caso de los tres anormales. Para abreviar, dejaré que el lector valide esto o simplemente puede mirar cualquier cuadrícula de solución de Sudoku.

Patrón anormal se define como tener un símbolo anormal por fila en$B_1$.

Patrón normal se define como tener un símbolo normal por fila en$B_1$.

Patrón totalmente anormal se define como todo$27$los símbolos son anormales.

Los patrones normales y anormales necesitan mayor aclaración. Para el patrón normal, necesitamos saber cuál de las tres posiciones en cada fila en B1 contiene el símbolo normal. Para el patrón anormal necesitamos lo mismo para el símbolo anormal. Para cada fila hay$3$posiciones por un total de$3\times3\times3 = 27$.

Así que el número total de permutaciones de símbolos en filas en$B_2$y$B_3$para banda$1$es$1$para el Todo-Normal,$3\times3\times3$para los anormales,$3\times3\times3$para la normalidad y$1$para los patrones Todo-Anormales. Llamemos a esto$R$:

R = 1 + 3*3*3 + 3*3*3 + 1 = 56 permutations of 9 symbols in 3 rows.

se debe notar que$R$describe los tres bloques incluso si tuviera que intercambiarlos, es una restricción natural en cualquier bloque/pila y podemos usarla más tarde para describir todo$3$bloques y$3$pilas

El resto es trivial, pero resaltaré las partes importantes.

Descripción de restricciones de columna para$B_2$y$B_3$

Todavía necesitamos describir las posiciones de las columnas para los símbolos en$B_2$y$B_3$, que son solo las permutaciones de los tres números en cada subfila, que es$6$. Llamemos a esto$P$:

P = 6*6*6 * 6*6*6 = 6*6 * 6*6 * 6*6 = 46656 permutations of 3 symbols in 6 sub-rows.

Nota de implementación: Debido a que en los casos Normal y Anormal, un valor terminará en una fila diferente que los otros dos. Al hacer las permutaciones, solo permute dos símbolos,$A$y$B$, a través de tres posiciones:

|A B x|, |A x B|, |x A B|, |B A x|, |B x A|, |x B A|

Dónde$A$y$B$son:

|A B x|    For each row in B1 in the All-Normal and All-Abnormal patterns.

|x A B|    For each row in B1 where,
|A x B|    in the Abnormal pattern, x is the position of abnormal symbol and,
|A B x|    in the Normal pattern, x is the position normal symbol.

El carácter restante x encontrará su posición como la posición abierta en su fila asignada.

Entonces para la banda$1$el número total de soluciones que utilizan posiciones de símbolos es:

R * P = 56 * 46656 = 2612736

Nota: puedo usar un número entre$1$a través de$2612736$para calcular una permutación específica de estas soluciones o puedo usar una solución y usar la discusión anterior para asignar un número específico a esta permutación.

La restricción del resto de las bandas y pilas

Si quiero describir las posiciones iniciales para$B_4$y$B_7$Puedo usar$R$y$P$para pila$1$como lo hice para Band1 y conocer todas las permutaciones de$B_4$y$B_7$. Nota sin importancia: más tarde podría hacer algunas renumeraciones para$B_1$al describir Stack$1$para ganar simetría para las descripciones finales de fila y columna.

$R$se puede utilizar en la banda$2$y banda$3$para describir las posiciones de fila para$B_5$,$B_6$,$B_8$, y$B_9$.

$R$se puede utilizar en la pila$2$y pila$3$para describir las posiciones de las columnas para$B_5$,$B_6$,$B_8$, y$B_9$.

Si conozco las posiciones de fila y columna para cada símbolo para$B_5$,$B_6$,$B_8$, y$B_9$luego, completar cada permutación solo implica hacer coincidir la fila y la columna de cada símbolo para cada bloque.

Conclusión

Puedo describir Banda$1$y las posiciones de fila en Band$2$y banda$3$como:

Row Contribution = R * P * R * R = 8,193,540,096

Puedo describir Stack$1$y las posiciones de las columnas en Stack$2$y pila$3$como:

Column Contribution = R * P * R * R = 8,193,540,096

El total es simplemente multiplicar estos dos números y$9!$para sustituir números por posiciones de símbolos

Total = 9! * 8,193,540,096 * 8,193,540,096 = 2.436162195571x10^25

Como solo se trata de multiplicar dígitos, podría enumerar todos los dígitos, pero mi paquete de matemáticas no tiene tantos dígitos significativos.

Nota sin importancia: podría ser bueno cambiar el$P$s entre las dos contribuciones ya que el$P$en la contribución de la fila fija las posiciones de la columna y viceversa, o no.

Entonces, ahora tengo un total de soluciones numéricas y un diseño para una función que, dado un número en este rango, puedo derivar una solución específica o dada una solución, puedo derivar su número ordinal y sé cómo contar todo soluciones

Nota humorística:$8,193,540,096 \times 8,193,540,096 = 6.7134E19$

Así que de nuevo, ¿dónde está mi error?