Mi sencillo método combinatorio para enumerar todas las cuadrículas de soluciones de sudoku

Question

¿Cuántas cuadrículas de solución de Sudoku posibles hay? La respuesta correcta es: $6,670,903,752,021,072,936,960$ o $6,671E21$ como se demostró $12$ ¡hace años! ¿O no?

Su prueba nunca enumeró realmente las soluciones e implicó mucho tiempo de computación en el ordenador central, lo que supuso reducir mucho los casos de prueba para que los cálculos se completaran en tiempo humano.

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

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

No puedo seguir su solución hasta el final ya que tengo que confiar en sus resultados informáticos. Envié esto al autor pero no me contestó, lo cual no es sorprendente ya que no es su lugar para demostrar que estoy equivocado. He esperado y revisado mi método lo suficiente como para mantener mi solución.

Ya que esto tiene que ser expresado en forma de pregunta: "¿Qué hay de malo en mi solución?"

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

Mi sencillo método combinatorio para enumerar las cuadrículas de soluciones de sudoku

Nota: El problema que tratamos de resolver aquí es para N0 que es el número máximo de cuadrículas de respuestas correctas de Sudoku. Por lo tanto, no se habla de intercambiar para obtener soluciones equivalentes.

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

Las tres bandas y pilas dividen la cuadrícula del sudoku en $9$ Bloques, etiquetados $B_1$ , $B_2$ y $B_3$ en la banda $1$ , $B_4$ , $B_5$ y $B_6$ en la banda $2$ y $B_7$ , $B_8$ y $B_9$ en la banda $3$ , lo 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 las posiciones de los símbolos por números

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

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

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

Descripción de las restricciones de fila para una banda

Digamos que queremos rellenar la Banda1 y empezamos en lo que yo llamo un Patrón Todo-Normal para $B_1$ Fila $1$ de la siguiente manera:

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.

Teniendo esto como punto de partida, ¿cómo rellenamos las posiciones de los símbolos del $B_1$ Fila2, en $B_2$ ? Si intentáramos ponerlas en la Fila1 tendríamos un problema al llegar a B3 porque tendríamos que utilizar posiciones ya ocupadas. Por lo tanto, tenemos que seguir el mismo patrón Todo-Normal que $B_1$ Fila1, resultando 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 All-Normal para rellenar los espacios en blanco.

Un Símbolo Normal se define como un símbolo que baja uno hasta el segundo bloque y baja uno hasta el tercer bloque, donde si va por debajo de la parte inferior se envuelve hasta la parte superior de la banda.

El símbolo anormal se define como un símbolo que baja dos al segundo bloque y baja dos al tercer bloque, con envoltura.

Un patrón normal es aquel en el que 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 hacia abajo $1$ y abajo $1$ .

Ahora bien, si intentamos rellenar $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 Row $1$ y elegir uno de los tres símbolos para ser anormal. Lo mismo puede decirse de tener dos anormales de la Fila $1$ , tenemos que repetirlo para las otras dos filas. Y finalmente tenemos el caso de los tres anormales. Para ser breve, dejaré que el lector valide esto o simplemente puede mirar cualquier cuadrícula de solución de Sudoku.

El patrón anormal se define como el que tiene un símbolo anormal por fila en $B_1$ .

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

Se define como patrón todo anormal a todos los $27$ símbolos que son anormales.

Los patrones normales y anormales necesitan una mayor aclaración. Para el patrón normal necesitamos saber cuál de las tres posiciones de cada fila de 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 para 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 la Banda $1$ es $1$ para el All-Normal, $3\times3\times3$ para los anormales, $3\times3\times3$ para la Normal, y $1$ para los patrones All-Abnormal. Llamemos a esto $R$ :

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

Hay que tener en cuenta que $R$ describe los tres bloques aunque los intercambie, es una restricción natural en cualquier bloque/pila y podemos usarla más tarde para describir todos los $3$ bloques y $3$ pilas.

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

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

Todavía tenemos que describir las posiciones de las columnas para los símbolos en $B_2$ y $B_3$ , que no es más que las permutaciones de los tres números de 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 a las otras dos, al hacer las permutaciones sólo 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.

Así que para la Banda $1$ el número total de soluciones que utilizan las posiciones de los símbolos es:

R * P = 56 * 46656 = 2612736

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

El Resto de Bandas y Pilas

Si quiero describir las posiciones iniciales de $B_4$ y $B_7$ Puedo usar $R$ y $P$ para Stack $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 una renumeración para $B_1$ al describir Stack $1$ para ganar simetría en las descripciones finales de filas y columnas.

$R$ puede utilizarse en Band $2$ y Banda $3$ para describir las posiciones de las filas de $B_5$ , $B_6$ , $B_8$ y $B_9$ .

$R$ puede utilizarse en Stack $2$ y Stack $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 de cada símbolo para $B_5$ , $B_6$ , $B_8$ y $B_9$ entonces la finalización de cada permutación sólo implica hacer coincidir la fila y la columna de cada símbolo para cada bloque.

Conclusión:

Puedo describir a Band $1$ y las posiciones de las filas en Band $2$ y Banda $3$ como:

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

Puedo describir a Stack $1$ y las posiciones de las columnas en Stack $2$ y Stack $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 las posiciones de los símbolos por números

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

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

Nota sin importancia: Podría ser bueno intercambiar 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.

Así que, ahora tengo un total de números soluciones 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 a través de todas las soluciones.

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

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

Answer 1

Tengo una denominación ligeramente diferente. Bloque $_{11}$ es la parte superior izquierda $3\times 3$ bloque.

Primero quiero describir su método para contar los sudokus. Luego quiero mostrar el error y el doy un ejemplo que muestra que su método no funciona. Intenta generar cada sudoku de la siguiente manera

1. definir el bloque $_{11}$ del sudoku hay 9! posibilidades

2. definir el bloque $_{12}$ y Block $_{13}$

   1. seleccione tres conjuntos: el primer conjunto contiene los números de la primera fila del bloque $_{12}$ , el segundo conjunto contiene los números de la segunda fila del bloque $_{12}$ , el tercer conjunto contiene los números de la tercera fila del bloque $_{12}$ . Estos conjuntos deben satisfacer las restricciones del sudoku con respecto al bloque $_{11}$ y Block $_{12}$ y debería permitir crear tres conjuntos con un significado similar para Block $_{13}$ . Ya has demostrado que hay como máximo 56 (=R) conjuntos triples posibles. Todos los demás triples de conjuntos llevarán a una contradicción con las restricciones del sudoku respecto a las tres primeras filas. De los conjuntos que has seleccionado puedes deducir tres conjuntos que son los números de la primera segunda y tercera fila del bloque $_{13}$
   2. en 2.1 has creado 6 conjuntos de longitud 3. Para cada conjunto selecciona una permutación de sus elementos. esta es entonces la fila real del sudoku. ya has mostrado allí $(3!)^6$ (=P)posibilidades para seleccionar 6 de estas permutaciones.

3. Definir el bloque $_{21}$ ad Block $_{31}$ de forma similar a Block $_{12}$ y Block $_{13}$ en 2. Pero ahora los conjuntos representan los números de las columnas de los bloques. De nuevo hay $R \cdot P$ posibilidades.

Ahora ha fijado los números de las celdas del bloque $_{11}$ , Block $_{12}$ , Block $_{13}$ , Block $_{21}$ y Block $_{31}$ .

4. 1. Definir conjuntos de columnas para el bloque $_{22}$ y los conjuntos deducidos para el bloque $_{32}$ . Hay R posibilidades
   2. Definir conjuntos de columnas para el bloque $_{23}$ y los conjuntos deducidos para el bloque $_{33}$ . Hay R posibilidades
   3. Definir conjuntos de filas para el bloque $_{22}$ y los conjuntos deducidos para el bloque $_{23}$ . Hay R posibilidades
   4. Definir conjuntos de filas para el bloque $_{32}$ y los conjuntos deducidos para el bloque $_{33}$ . Hay R posibilidades
5. Para cada celda de los cuatro bloques mencionados en el punto 4. construya el número definido de forma única que satisfaga el conjunto de columnas y filas dado

Utilizando los pasos 1 a 3 tienes $9!\times (R\times P)^2$ para asignar números a las celdas del bloque $_{11}$ , Block $_{12}$ , Block $_{13}$ , Block $_{21}$ , Block $_{31}$ consistentemente. Consistentemente significa que cada uno de estos Bloques, cada una de las 3 filas superiores y cada una de las 3 líneas de la izquierda contiene cada uno de los números del 1 al 9 exactamente una vez.

Entonces dices que tienes $R^4$ formas de seleccionar los conjuntos que contienen los números de las filas y columnas de Bloque $_{22},$ Bloque $_{23},$ Bloque $_{32}$ y Block $_{33}.$ Dichos conjuntos deben ser elegidos de forma similar a la 2. y 3. Tal selección de conjuntos consiste en el conjunto que contiene los números de la primera fila del bloque $_{22},$ el conjunto que contiene los números de la segunda fila del bloque $_{22}$ y el conjunto que contiene los números de la tercera fila del bloque $_{22}.$ Entonces tenemos tres conjuntos que contienen los números de la primera, segunda y tercera columna del bloque $_{22}.$ Así que en tenemos que elegir 6 conjuntos para el bloque $_{22}$ . Para el bloque $_{23},$ Bloque $_{32}$ y Block $_{33}$ tenemos que elegir seis conjuntos respectivamente, también. Así que cada uno de estos $R^4$ Las selecciones constan de 24 conjuntos con 3 elementos que resticen los valores del bloque $_{22},$ Bloque $_{23},$ Bloque $_{32}$ y Block $_{33}.$

Pero en el 5 afirmas que para cada una de esas selecciones de 24 conjuntos hay exactamente un número para cada celda que satisface las restricciones impuestas por los conjuntos.

Pero tampoco has demostrado que para cada selección de 24 conjuntos exista al menos una asignación a las celdas que satisfaga las restricciones impuestas por tales 24 conjuntos ni que haya a lo sumo una asignación que satisfaga estas restricciones.

Un ejemplo: Aquí tenemos un sudoku

6 7 8 | 4 5 3 | 2 9 1
5 9 4 | 8 2 1 | 7 3 6
1 3 2 | 6 9 7 | 5 4 8
------+-------+------
2 6 1 | 3 7 8 | 4 5 9
9 8 7 | 1 4 5 | 3 6 2
3 4 5 | 9 6 2 | 1 8 7
------+-------+------
7 5 9 | 2 3 6 | 8 1 4
8 2 6 | 5 1 4 | 9 7 3
4 1 3 | 7 8 9 | 6 2 5 

Suponga que ha ejecutado los pasos 1 a 4.3. (y que en el siguiente diagrama ha asignado números a las celdas del bloque $_{22}$ y Block $_{23}$ ) A las celdas del bloque $_{32}$ y Block $_{33}$ no teníamos valores asignados.

6 7 8 | 4 5 3 | 2 9 1
5 9 4 | 8 2 1 | 7 3 6
1 3 2 | 6 9 7 | 5 4 8
------+-------+------
2 6 1 | 3 7 8 | 4 5 9
9 8 7 | 1 4 5 | 3 6 2
3 4 5 | 9 6 2 | 1 8 7
------+-------+------
7 5 9 |       |      
8 2 6 |       |      
4 1 3 |       |      

Ahora asignamos los siguientes conjuntos a las filas y columnas de Block $_{32}$ y Block $_{33}$ .

      row sets (interchanged the row sets of 
      Block32 and Block33 of the original sudoku):
------+-------+------
      |       |      
      |       |      
      |       |      
------+-------+------
      |       |      
      |       |      
      |       |      
------+-------+------
      { 1 4 8 { 2 3 6 
      { 3 7 9 { 1 4 5
      { 2 5 6 { 7 8 9

      column sets (the same as for the original sudoku):
------+-------+------
      |       |      
      |       |      
      |       |      
------+~~~~~~~+~~~~~~
      | 1 4 2 | 1 5 2
      | 3 6 5 | 3 6 7
      | 9 7 8 | 4 8 9
------+~~~~~~~+~~~~~~
      | 2 1 4 | 6 1 3
      | 5 3 6 | 8 2 4
      | 7 8 9 | 9 7 5

El { y el ~ deben recordarle que las filas y columnas del bloque $_{23}$ y Block $_{33}$ no son realmente las filas y las columnas de estos dos bloques, sino los conjuntos asignados a estas filas y columnas.

Estos conjuntos se construyen según sus requisitos, pero ahora hay una asignación a las celdas del bloque $_{33}$ que puede satisfacer los requisitos. Pero Block $_33$ no puede satisfacer estos conjuntos.

      |       |       
      |       |       
      |       |       
------+-------+-------
      |       |       
      |       |       
      |       |       
------+-------+-------
      |       | 6 2 3      
      |       | ?     
      |       |       

No hay ningún número válido para la célula $_{87}$ . El número debe estar en {1, 4, 5} (conjunto de filas) y {6,8,9} (conjunto de columnas). Pero la intersección de estos conjuntos es el conjunto vacío.

Pero cuenta que en realidad hay R sudokus que satisfacen estas restricciones.

Nota: Tal vez quiera leer mi respuesta en stackoverflow donde cito el post de Kevin Kinfoil que intenta estimar el número de posibles Sudokus utilizando argumentos heurísticos similares. Llega a un número que sólo difiere en un 0,2% del valor real. Esta argumentación heurística se publicó antes de que se conociera el valor real.

Nota: El número de sudokus posibles se calculó primero por Jarvis y Felgenhauer .