¿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?
0 votos
¿Cómo garantiza tu método que, por ejemplo, no haya un 1 en la fila 2 columna 4 y también en la fila 6 columna 4?
0 votos
(Más concretamente, cuando se multiplica la "contribución de la fila" y la "contribución de la columna" juntas, en realidad se está hablando del número de configuraciones de dos cuadrículas de 9x9: una que satisface las restricciones de fila y otra que satisface las restricciones de columna).
0 votos
R para Stack2 confina las posiciones de columna para B5 y B7 lo que asegura que 1 no puede estar en la misma columna en la fila 2 y en la fila 6.
0 votos
"El problema que tratamos de resolver aquí es para N0, que es el número máximo de cuadrículas de respuestas correctas del Sudoku. Por lo tanto, no se habla de intercambiar para obtener soluciones equivalentes". No entiendo esto. ¿Quieres calcular el número de cuadrículas de sudoku válidas diferentes? Si es así, ¿de qué máximo estás hablando y qué significa la frase sobre el "intercambio"?
0 votos
Milagro173, Cuando leí estos documentos me resultó confuso lo que intentaban calcular y esperaba que estas dos frases lo aclararan. Podría preguntar a qué te refieres con diferente? ¿Piensa que eso puede confundir a algunos sobre lo que está preguntando? ¿Si sostengo una cuadrícula de Sudoku frente a un espejo es diferente? Para N0 la respuesta es sí, la imagen del espejo es sólo una permutación más en la enumeración de resultados.
0 votos
Miracle173, a tu segunda pregunta, quizás N0 debería llamarse Nmax. En su reducción de casos de prueba estaban intercambiando bloques y reetiquetando y era confuso. En mi segunda frase, "No se habla de swapping" significa que no hay swapping no que no quiera hablar de mi swapping. Así que "intercambio" no significa nada ya que no hay ninguno.
0 votos
Milagro173, somos dos personas separadas por un idioma común. Cuando dices "quieres calcular" y "sobre qué máximo", parece que piensas que aún tengo trabajo por hacer. Mi total 2,43E25 es la respuesta a la misma pregunta que ellos respondieron con 6,671E21 y yo digo que están equivocados.
0 votos
Debes anteponer al nombre de usuario en los comentarios una @ porque entonces el comentario se envía al usuario
0 votos
@Steven Stadnicki, me fijé en tu nombre en una respuesta a la sección de rompecabezas sobre el tipo que quiere saber sobre el Sudoku con 2 soluciones. Dijiste que podías crear uno con 3. ¿Lo documentaste en algún sitio? Además, no puedo poner una respuesta a esa pregunta porque está restringida y no tengo la reputación, pero todas las respuestas son tontas, como ¿debería tomar mi almuerzo o ir en autobús hoy?
0 votos
@miracle173, gracias por señalarlo.
0 votos
@miracle173, et al. Esta discusión es un ejemplo de guerra asimétrica en el sentido de que no podemos añadir fácilmente diagramas y estamos limitados en el número de caracteres en un comentario . Me he unido al Foro de Nuevos Jugadores de Sudoku y he añadido esto como tema, así que tal vez sería mejor si continuamos allí. [ forum.enjoysudoku.com/
0 votos
@miracle173, me pusieron un ejemplo concreto en el que lo que hacía no funcionaba y estoy seguro de que lo que dices es correcto. Por lo tanto, mi conclusión es que estoy equivocado. Gracias por tu tiempo, ahora ya no tengo eso metido en el cerebro.
0 votos
Mi contraejemplo estaba equivocado. Estoy reescribiendo mi post pero eso es muy tedioso. También quiero hacer un contraejemplo correcto. Pero creo que se puede demostrar que cada cosa que cuentas corresponde como máximo a un sudoku. Eso significa que tu número es un límite superior para el número de sudokus posibles.