.png/1280px-Sudoku_Puzzle_(automorphic_with_translational_symmetry).png)
Las matemáticas se pueden utilizar para estudiar los Sudoku y responder preguntas como "¿Cuántas cuadrículas de Sudoku llenas hay?", "¿Cuál es el número mínimo de pistas en un rompecabezas válido?" y "¿De qué manera pueden ser simétricas las cuadrículas de Sudoku?" mediante el uso de la combinatoria y la teoría de grupos .
El análisis del Sudoku generalmente se divide entre analizar las propiedades de los acertijos sin resolver (como el mínimo número posible de pistas dadas) y analizar las propiedades de los acertijos resueltos. El análisis inicial se centró en gran medida en enumerar soluciones, y los resultados aparecieron por primera vez en 2004. [1]
Para el Sudoku clásico, el número de cuadrículas llenas es 6.670.903.752.021.072.936.960 (6,671 × 10 21 ), lo que se reduce a 5.472.730.538 soluciones esencialmente diferentes bajo las transformaciones que preservan la validez. Hay 26 tipos posibles de simetría , pero sólo se pueden encontrar en aproximadamente el 0,005% de todas las cuadrículas rellenas. Un rompecabezas común y corriente con una solución única debe tener al menos 17 pistas. Hay un rompecabezas solucionable con como máximo 21 pistas por cada cuadrícula resuelta. El rompecabezas mínimo más grande encontrado hasta ahora tiene 40 pistas en las 81 celdas.
Los Sudokus ordinarios ( acertijos adecuados ) tienen una solución única. Un Sudoku mínimo es un Sudoku del que no se puede eliminar ninguna pista y lo convierte en un Sudoku adecuado. Diferentes Sudokus mínimos pueden tener un número diferente de pistas. Esta sección analiza el número mínimo de datos para acertijos adecuados.
Se han encontrado muchos Sudokus con 17 pistas, aunque encontrarlas no es una tarea baladí. [2] [3] Un artículo de 2014 de Gary McGuire, Bastian Tugemann y Gilles Civario demostró que el número mínimo de pistas en cualquier Sudoku adecuado es 17 a través de una búsqueda exhaustiva por computadora basada en la enumeración de conjuntos de aciertos . [4]
Se cree que la menor cantidad de pistas en un Sudoku con simetría diagonal bidireccional (una simetría rotacional de 180°) es 18, y en al menos un caso dicho Sudoku también exhibe automorfismo . Se sabe que existe un Sudoku con 24 pistas, simetría diédrica (una simetría rotacional de 90°, que también incluye una simetría en ambos ejes ortogonales, simetría rotacional de 180° y simetría diagonal), pero no se sabe si este número de pistas es mínimo para esta clase de Sudoku. [5]
No se conoce con precisión el número de Sudokus mínimos (Sudokus en los que no se puede eliminar ninguna pista sin perder la unicidad de la solución). Sin embargo, las técnicas estadísticas combinadas con un generador ( 'Estadísticas imparciales de un CSP – Un generador de sesgo controlado' ), [6] muestran que existen aproximadamente (con un error relativo del 0,065%):
Existen muchas variantes de Sudoku, caracterizadas parcialmente por el tamaño ( N ) y la forma de sus regiones . A menos que se indique lo contrario, la discusión en este artículo asume el Sudoku clásico, es decir, N =9 (una cuadrícula de 9×9 y regiones de 3×3). Un Sudoku rectangular utiliza regiones rectangulares de dimensión fila- columna R × C. Otras variantes incluyen aquellas con regiones de forma irregular o con restricciones adicionales (hipercubo).
Las regiones también se denominan bloques o cajas . Una banda es una parte de la cuadrícula que encapsula tres filas y tres cuadros, y una pila es una parte de la cuadrícula que encapsula tres columnas y tres cuadros. Un rompecabezas es una cuadrícula parcialmente completada y los valores iniciales son datos o pistas . Un rompecabezas adecuado tiene una solución única. Un rompecabezas mínimo es un rompecabezas adecuado del que no se puede eliminar ninguna pista sin introducir soluciones adicionales.
La resolución de Sudokus desde el punto de vista de un jugador se ha explorado en el libro de Denis Berthier "La lógica oculta del Sudoku" (2007) [7] , que considera estrategias como las "cadenas xy ocultas".
Se sabe que el problema general de resolver Sudoku en n 2 × n 2 cuadrículas de n × n bloques es NP-completo . [8]
Un rompecabezas se puede expresar como un problema de coloración de gráficos . [9] El objetivo es construir una coloración de 9 de un gráfico particular, dada una coloración de 9 parcial. El gráfico de Sudoku tiene 81 vértices, un vértice por cada celda. Los vértices están etiquetados con pares ordenados ( x , y ), donde x e y son números enteros entre 1 y 9. En este caso, dos vértices distintos etiquetados por ( x , y ) y ( x ′, y ′) están unidos por un borde si y sólo si :
Luego se completa el rompecabezas asignando un número entero entre 1 y 9 a cada vértice, de tal forma que los vértices que están unidos por una arista no tengan asignado el mismo número entero.
Una cuadrícula de solución de Sudoku también es un cuadrado latino . [9] Hay significativamente menos cuadrículas de Sudoku que cuadrados latinos porque el Sudoku impone restricciones regionales adicionales.
Como en el caso de los cuadrados latinos, las tablas de multiplicación (suma o) ( tablas de Cayley ) de grupos finitos se pueden utilizar para construir Sudokus y tablas de números relacionadas. Es decir, hay que tener en cuenta subgrupos y grupos de cocientes :
Tomemos, por ejemplo , el grupo de pares, agregando cada componente por separado módulo some . Al omitir uno de los componentes, de repente nos encontramos en (y este mapeo es obviamente compatible con las respectivas adiciones, es decir, es un homomorfismo de grupo ). También se dice que este último es un grupo cociente del primero, porque algunos elementos que alguna vez fueron diferentes se vuelven iguales en el nuevo grupo. Sin embargo, también es un subgrupo, porque simplemente podemos completar el componente que falta para volver a .
Bajo esta vista, escribimos el ejemplo, Cuadrícula 1 , para .
Cada región de Sudoku se ve igual en el segundo componente (es decir, como el subgrupo ), porque se agregan independientemente del primero. Por otro lado, los primeros componentes son iguales en cada bloque, y si imaginamos cada bloque como una celda, estos primeros componentes muestran el mismo patrón (es decir, el grupo cociente ). Como se describe en el artículo de cuadrados latinos, este es un cuadrado latino de orden .
Ahora, para obtener un Sudoku, permutemos las filas (o equivalentemente las columnas) de tal manera que cada bloque se redistribuya exactamente una vez en cada bloque; por ejemplo, ordénelos . Por supuesto, esto preserva la propiedad del cuadrado latino. Además, en cada bloque las líneas tienen un primer componente distinto por construcción y cada línea en un bloque tiene entradas distintas a través del segundo componente, porque los segundos componentes de los bloques originalmente formaban un cuadrado latino de orden (del subgrupo ). Así llegamos a un Sudoku (cambie el nombre de los pares a los números 1...9 si lo desea). Con el ejemplo y la permutación de filas anteriores, llegamos a la Cuadrícula 2 .
Para que este método funcione, generalmente no se necesita un producto de dos grupos del mismo tamaño. La llamada secuencia exacta corta de grupos finitos de tamaño apropiado ya hace el trabajo. Pruebe, por ejemplo, el grupo con cociente y subgrupo . Parece claro (ya por los argumentos de enumeración) que no todos los Sudokus se pueden generar de esta manera.
Un Sudoku cuyas regiones no son (necesariamente) cuadradas o rectangulares se conoce como Jigsaw Sudoku. En particular, un cuadrado N × N donde N es primo solo puede revestirse con N -ominós irregulares . Para valores pequeños de N, se ha calculado el número de formas de mosaico del cuadrado (excluyendo las simetrías) (secuencia A172477 en el OEIS ). [10] Para N ≥ 4 algunos de estos mosaicos no son compatibles con ningún cuadrado latino; es decir, todos los Sudokus en este tipo de mosaicos no tienen solución. [10]
La respuesta a la pregunta "¿Cuántas cuadrículas de Sudoku hay?" Depende de la definición de cuándo soluciones similares se consideran diferentes.
Para la enumeración de todas las soluciones posibles, dos soluciones se consideran distintas si alguno de sus valores de celda correspondientes (81) difiere. Se ignoran las relaciones de simetría entre soluciones similares, 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.
La primera solución conocida para completar la enumeración fue publicada por QSCGZ (Guenter Stertenbrink) en el grupo de noticias rec.puzzles en 2003, [11] [12] obteniendo 6.670.903.752.021.072.936.960 (6,67 × 10 21 ) soluciones distintas.
En un estudio de 2005, Felgenhauer y Jarvis [13] [12] analizaron las permutaciones de la banda superior utilizadas en soluciones válidas. Una vez que se identificaron las simetrías de Banda1 y las clases de equivalencia para las soluciones de cuadrícula parcial, se construyeron y contaron las terminaciones de las dos bandas inferiores para cada clase de equivalencia. La suma de las terminaciones de 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, lo que confirma el valor obtenido por QSCGZ. Posteriormente, el valor fue confirmado en numerosas ocasiones de forma independiente. Posteriormente se desarrolló una segunda técnica de enumeración basada en la generación de bandas que requiere un uso computacional significativamente menor. Esta técnica posterior requirió aproximadamente 1/97 del número de ciclos de cálculo que las técnicas originales, pero fue significativamente más complicada de configurar.
La estructura precisa del grupo de simetría del sudoku se puede expresar de manera sucinta utilizando el producto de corona (≀). ¡Las posibles permutaciones de fila (o columna) forman un grupo isomorfo a S 3 ≀ S 3 de orden 3! 4 = 1.296. [4] Todo el grupo de reordenamiento se forma dejando que la operación de transposición (isomorfa a C 2 ) actúe sobre dos copias de ese grupo, una para las permutaciones de fila y otra para las permutaciones de columna. Este es S 3 ≀ S 3 ≀ C 2 , un grupo de orden 1.296 2 × 2 = 3.359.232. Finalmente, las operaciones de reetiquetado conmutan con las operaciones de reordenamiento, por lo que el grupo completo de sudoku (VPT) es ( S 3 ≀ S 3 ≀ C 2 ) × S 9 de orden 1,218,998,108,160.
El conjunto de cuadrículas equivalentes al que se puede llegar mediante estas operaciones (excluyendo el reetiquetado) forma una órbita de cuadrículas bajo la acción del grupo de reordenamiento . El número de soluciones esencialmente diferentes es entonces el número de órbitas, que se puede calcular utilizando el lema de Burnside . Los puntos fijos de Burnside son cuadrículas que no cambian durante la operación de reordenamiento o solo difieren al volver a etiquetarse. Para simplificar el cálculo, los elementos del grupo de reordenamiento se clasifican en clases de conjugación , cuyos elementos tienen todos el mismo número de puntos fijos. Resulta que sólo 27 de las 275 clases de conjugación del grupo de reordenamiento tienen puntos fijos; [14] estas clases de conjugación representan los diferentes tipos de simetría (autosemejanza o automorfismo) que se pueden encontrar en las cuadrículas de sudoku completadas. Utilizando esta técnica, Ed Russell y Frazer Jarvis fueron los primeros en calcular el número de soluciones de sudoku esencialmente diferentes como 5.472.730.538 . [14] [15]
Excluyendo el reetiquetado, todas las operaciones del grupo de simetría del sudoku consisten en reordenamientos de celdas que preservan la solución , lo que plantea la cuestión de si todos esos reordenamientos de celdas que preservan la solución están en el grupo de simetría. En 2008, Aviv Adler e Ilan Adler demostraron que todos los reordenamientos celulares que conservan la solución están contenidos en el grupo, incluso para las cuadrículas generales. [dieciséis]
