stringtranslate.com

Matemáticas del sudoku

Un sudoku automórfico de 24 pistas con simetría traslacional.
Un sudoku automórfico de 24 pistas con simetría traslacional

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.

Rompecabezas

Número mínimo de datos dados

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.

Sudoku ordinario

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]

Sudoku simétrico

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]

Número total de rompecabezas mínimos

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%):

Variantes

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".

Contexto matemático

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.

Sudokus a partir de tablas de grupo

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.

Sudokus de rompecabezas

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]

Soluciones

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.

Sudoku ordinario

Todas las soluciones

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.

Soluciones esencialmente diferentes

El grupo de simetría del sudoku

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 3S 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 3S 3C 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 3S 3C 2 ) × S 9 de orden 1.218.998.108.160.

Puntos fijos y lema de Burnside

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]

Completitud del grupo de simetría del sudoku

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]

Véase también

Referencias

  1. ^ Lin, Keh Ying (2004), "Número de sudokus", Journal of Recreational Mathematics , 33 (2): 120–24.
  2. ^ "プ ロ グ ラ ミ ン グ パ ズ ル 雑 談 コ ー ナ ー". .ic-net.or.jp. Archivado desde el original el 12 de octubre de 2016 . Consultado el 20 de octubre de 2013 .
  3. ^ "Sudoku mínimo". Csse.uwa.edu.au. Archivado desde el original el 26 de noviembre de 2006. Consultado el 20 de octubre de 2013 .
  4. ^ ab McGuire, G.; Tugemann, B.; Civario, G. (2014). "No existe un sudoku de 16 pistas: solución del problema del sudoku con el número mínimo de pistas". Experimental Mathematics . 23 (2): 190–217. arXiv : 1201.0749 . doi :10.1080/10586458.2013.870056.
  5. ^ Taalman, Laura (2007), "Tomar el Sudoku en serio", Math Horizons , 15 (1): 5–9, doi :10.1080/10724117.2007.11974720, JSTOR  25678701, S2CID  126371771Véase en particular la figura 7, pág. 7.
  6. ^ Berthier, Denis (4 de diciembre de 2009). «Estadísticas imparciales de un CSP: un generador de sesgo controlado» . Consultado el 4 de diciembre de 2009 .
  7. ^ Berthier, Denis (noviembre de 2007). La lógica oculta del sudoku (segunda edición, revisada y ampliada). Lulu.com. ISBN 978-1847534729.
  8. ^ Yato, Takayuki; Seta, Takahiro (2003). "Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . E86-A (5): 1052–1060.
  9. ^ ab Lewis, R. Una guía para colorear gráficos: algoritmos y aplicaciones . Springer International Publishers, 2015.
  10. ^ ab de Ruiter, Johan (15 de marzo de 2010). "Sobre los sudokus y temas relacionados (tesis de licenciatura)" (PDF) . Instituto de Ciencias Informáticas Avanzadas de Leiden (LIACS) .
  11. ^ QSCGZ (Guenter Stertenbrink) (21 de septiembre de 2003). "pregunta combinatoria sobre 9x9 (rec.puzzles)". Grupos de discusión de Google . Consultado el 20 de octubre de 2013 .
  12. ^ ab Jarvis, Frazer (2 de febrero de 2008). «Sudoku enumeration problems». Página de inicio de Frazer Jarvis . Universidad de Sheffield . Consultado el 20 de octubre de 2013 .
  13. ^ Felgenhauer, Bertram; Jarvis, Frazer (20 de junio de 2005), Enumeración de posibles cuadrículas de Sudoku (PDF).
  14. ^ ab Ed Russell y Frazer Jarvis (7 de septiembre de 2005). "Hay 5472730538 cuadrículas de Sudoku esencialmente diferentes... y el grupo de simetría del Sudoku". Página de inicio de Frazer Jarvis . Universidad de Sheffield . Consultado el 20 de octubre de 2013 .
  15. ^ Ed Russell, Frazer Jarvis (25 de enero de 2006). "Matemáticas del Sudoku II" (PDF) .
  16. ^ Adler, Aviv; Adler, Ilan (2008). "Transformaciones fundamentales de cuadrículas de sudoku" (PDF) . Mathematical Spectrum . 41 (1): 2–7.

Lectura adicional

Enlaces externos