.png/1280px-Sudoku_Puzzle_(automorphic_with_translational_symmetry).png)
Las matemáticas se pueden utilizar para estudiar los rompecabezas de 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 se divide generalmente entre el análisis de las propiedades de los rompecabezas no resueltos (como el número mínimo posible de pistas dadas) y el análisis de las propiedades de los rompecabezas resueltos. El análisis inicial se centró principalmente en la enumeración de soluciones, y los primeros resultados aparecieron 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 solo se pueden encontrar en aproximadamente el 0,005 % de todas las cuadrículas llenas. Un rompecabezas ordinario con una solución única debe tener al menos 17 pistas. Hay un rompecabezas solucionable con un máximo de 21 pistas para cada cuadrícula resuelta. El rompecabezas mínimo más grande encontrado hasta ahora tiene 40 pistas en las 81 celdas.
Los sudokus comunes ( rompecabezas reales ) tienen una solución única. Un sudoku minimalista es un sudoku del que no se puede quitar ninguna pista, por lo que sigue siendo un sudoku real. Los distintos sudokus minimalistas pueden tener una cantidad diferente de pistas. En esta sección se analiza la cantidad mínima de datos que deben darse para los rompecabezas reales.
Se han encontrado muchos Sudokus con 17 pistas, aunque encontrarlos no es una tarea trivial. [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, un Sudoku de este tipo también exhibe automorfismo . Se sabe que existe un Sudoku con 24 pistas, simetría diedra (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 esta cantidad de pistas es mínima 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, técnicas estadísticas combinadas con un generador ( 'Unbiased Statistics of a CSP – A Controlled-Bias Generator' ), [6] muestran que existen aproximadamente (con un error relativo del 0,065%):
Existen muchas variantes del Sudoku, que se caracterizan 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 cajas, y una pila es una parte de la cuadrícula que encapsula tres columnas y tres cajas. 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 ha sido explorada 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 sudokus en cuadrículas n 2 × n 2 de bloques n × n es NP-completo . [8]
Un rompecabezas puede expresarse como un problema de coloración de grafos . [9] El objetivo es construir una coloración de 9 de un grafo particular, dada una coloración de 9 parcial. El grafo 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 una arista si y solo si :
El rompecabezas se completa entonces asignando un número entero entre 1 y 9 a cada vértice, de tal manera que los vértices que están unidos por una arista no tengan el mismo número entero asignado.
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.
Al igual que en el caso de los cuadrados latinos, las tablas de suma y multiplicación ( 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 los subgrupos y los grupos de cocientes :
Tomemos como ejemplo el grupo de pares, sumando cada componente por separado módulo algunos . Al omitir uno de los componentes, de repente nos encontramos en (y esta aplicación 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 faltante con para volver a .
Bajo esta vista, escribimos el ejemplo, Cuadrícula 1 , para .
Cada región del Sudoku se ve igual en el segundo componente (es decir, como el subgrupo ), porque estos se suman 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 de cocientes ). Como se describe en el artículo de los 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, ordenándolos . Esto, por supuesto, conserva 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 ). De este modo, 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 de igual tamaño. Una denominada secuencia exacta corta de grupos finitos de tamaño apropiado ya funciona. Pruebe, por ejemplo, el grupo con cociente y subgrupo . Parece claro (ya a partir de 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 un Sudoku Jigsaw. En particular, un cuadrado N × N donde N es primo solo puede ser embaldosado con N -ominós irregulares . Para valores pequeños de N se ha calculado el número de formas de embaldosar el cuadrado (excluyendo simetrías) (secuencia A172477 en la OEIS ). [10] Para N ≥ 4 algunos de estos embaldosados no son compatibles con ningún cuadrado latino; es decir, todos los rompecabezas de Sudoku en un embaldosado de este tipo 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 posibles soluciones, dos soluciones se consideran distintas si cualquiera 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 posibles soluciones.
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 identificadas las simetrías de Band1 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 en las clases de equivalencia, ponderadas por el tamaño de la clase, da como resultado un número total de soluciones de 6.670.903.752.021.072.936.960, lo que confirma el valor obtenido por QSCGZ. El valor se confirmó posteriormente numerosas veces de forma independiente. Posteriormente se desarrolló una segunda técnica de enumeración basada en la generación de bandas que es significativamente menos intensiva en términos computacionales. Esta técnica posterior dio como resultado la necesidad de 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 sucintamente 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] El grupo de reordenamiento completo 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. Esto 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 sudoku completo (VPT) es ( S 3 ≀ S 3 ≀ C 2 ) × S 9 de orden 1.218.998.108.160.
El conjunto de cuadrículas equivalentes que se puede alcanzar utilizando 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 bajo la operación de reordenamiento o solo difieren mediante el reetiquetado. 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 solo 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 (autosimilitud o automorfismo) que se pueden encontrar en 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, las operaciones del grupo de simetría del sudoku consisten en reordenamientos de celdas que preservan la solución , lo que plantea la pregunta 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 de celdas que preservan la solución están contenidos en el grupo, incluso para cuadrículas generales. [16]
