Hace algún tiempo estuve hablando con Víctor y Adán Lerma (Padre e hijo) sobre un puzzle en el que estaban un poco atorados… Éste era un Sudoku. Luego ayer en la mañana vi en la publicación Día Siete del diario El Universal un Sudoku en la sección de pasatiempos, así que decidí dedicar un post a este tipo de “rompecabezas”
El Sudoku es un juego en el cual se tiene una matriz de 9x9 en la que se tiene que llenar cada renglón, columna y submatriz de 3x3 con los números del 1 al 9.
Si quieren ver la solución hagan click en la imagen
Historia
Sudoku puede haberse originado en Nueva York. Su origen se remonta a finales de la década de los 70, más concretamente en 1979. Entonces, la empresa Dell Magazines publicó este puzzle, ideado por Howard Games, bajo el nombre de Number Place (el lugar de los números). Posteriormente la idea fue introducida en el periódico japonés Monthly Nikolist en 1984 que le dio el nombre de Suji wa dokushin ni kagiru (los números deben estar solos), hasta que posteriormente se abrevió esta nomenclatura para dar con el nombre por el que le conocemos hoy, Sudoku (números sólos).
Aunque es mucho más probable que el sudoku se crease a partir de los trabajos de Leonhard Euler, famoso matemático suizo del siglo XVIII. Dicho matemático no creo el juego en sí, sino que utilizó el sistema llamado del cuadrado latino para realizar cálculos de probabilidades. (Un cuadrado latino es una matriz de nxn en la que en cada renglón y cada columna se tienen permutaciones de los mismos valores. Así cada solución de un Sudoku es un cuadrado latino, pero no todos los cuadrados latinos son soluciones de Sudoku, por la restricción adicional de las submatrices)
En 1986, Nikoli introdujo dos innovaciones que garantizarían la popularidad del rompecabezas: el número de cifras que venían dadas estaría restringida a un máximo de 30 y los puzzles serían “simétricos” (es decir, las celdas con cifras dadas estarían dispuestas de forma rotacionalmente simétrica). Esto no siempre se cumple en los Sudokus actuales. En 1997 Wayne Gould preparó algunos sudokus para el diario The Times, que los publicó bastante más tarde, en diciembre de 2004. Tres días después, The Daily Mail publicó sus sudokus con el nombre codenumber. En 2005 muchos otros periódicos británicos empezaron a incluir sudokus a diario en sus páginas.
Métodos de resolución
Para resolver un Sudoku se espera que se utilice una mezcla entre las siguientes técnicas:
- Escaneo: Consta de dos técnicas básicas: trama cruzada y recuento, que pueden usarse alternativamente.
- Trama cruzada: escaneo de filas (o columnas) para identificar qué línea en una región particular puede contener un número determinado mediante un proceso de eliminación.
- Recuento 1-9 por regiones, filas y columnas para identificar números perdidos. El recuento basado en el último número descubierto puede aumentar la velocidad de la búsqueda.
Marcado:La mayoría encuentra útil guiar este análisis mediante el marcado de números candidatos en las celdas vacías. Hay dos notaciones populares: subíndices y puntos.
Análisis: Hay dos aproximaciones principales - eliminación y “y-si”.
- En eliminación, el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo
- En la aproximación “y-si”, se selecciona una celda con sólo dos números candidatos y se realiza una conjetura.
Rankeo de dificultad
Para medir el nivel de dificultad de un puzzle se ha creado una fórmula, la cual toma en cuenta las siguientes variables:
- Porcentaje de recuadros vacíos
- Porcentaje de recuadros que se pueden obtener por eliminación
- Porcentaje de supuestos (guesses) que se deben hacer para encontrar la solución
- Número de backtraces (regresos) que se deben hacer para encontrar la solución
La fórmula toma con una relación negativa a las primeras variables (mientras mayores son es menos dificil) y con una positiva a las últimas dos (mientras mayores son mayor es la dificultad)
Matemáticas en Sudoku
El problema de resolver Sudoku para matrices de dimensión (n^2) x (n^2) con submatrices de nxn se sabe que es NP-Completo, aunque para Sudokus de dimensión finita y fija se pueden resolver por medio de algoritmos.
El problema de resolver un Sudoku se puede expresar como un problema de coloración de gráficas. El objeto del juego es encontrar una 9-coloración de una gráfica en particular, dada una 9-coloración parcial (esto para el Sudoku de 9x9). Nuestra gráfica en cuestión tiene 81 vértices, cada punto de la matriz, el cual puede ser expresado con el par ordenado (x,y) representando sus coordenadas dentro de la misma.
Sean (x,y), (x’,y’) dos vértices, crearemos una arista entre éstos vértices si se cumple alguna de las siguientes condiciones.
- x = x’
- y = y’
- [x/3] = [x’/3] y [y/3] = [y’/3] con [z] la función techo de z
El Sudoku se completa al asignar un entero entre 1 y 9 a cada vértice, de tal forma que si dos vértices están unidos por una arista no tengan el mismo número asignado.
Finalmente el número de soluciones válidas para Sudokus de 9x9 fue calculado por Bertram Felgenhauer en 2005 el resultado fue 6,670,903,752,021,072,936,960 soluciones. Si se añade la restricción de que el Sudoku sea simétrico se tienen 5,472,730,538 soluciones.
Para más información ver este artículo de Wikipedia
ahora nuestra página sale siempre al final de las listas pero no tengo ni idea de porqué…
