| + Ficha Técnica |
| + Mapa Publicaciones |
| + Videos Asociados |
|
Introducción El presente algoritmo matemático constituye el núcleo conceptual de la aplicación publicada en Internet bajo la denominación Sudoku-U1  .Dicha aplicación corresponde a un editor y generador de tableros de Sudoku desarrollado conforme a un conjunto de reglas que se han denominado Platinum, cuyo propósito fundamental consiste en garantizar que cada tablero generado posea una única solución.1 
En el contexto de la aplicación Sudoku-U1 , el usuario puede construir, simular y resolver tableros generados automáticamente por el sistema, así como trabajar con configuraciones propias o propuestas en publicaciones especializadas.
Ahora, el objetivo de este documento complementario es describir de manera sistemática el algoritmo matemático empleado en la resolución de sudokus clasificados como de solución única9. Asimismo, describir el procedimiento mediante el cual dichos tableros se construyen a partir de una configuración inicial válida. En una primera etapa se completa una matriz global \( M_{9\times 9} \) utilizando valores del conjunto \[ D=\{1,2,3,4,5,6,7,8,9\}, \] cumpliendo estrictamente las condiciones estructurales del rompecabezas.2  Diagrama de Proceso En efecto, \( M \in D^{9\times9} \) tiene una solución completa válida del Sudoku3. El algoritmo Sudoku-U1 genera un puzzle \( U \subset M \) tal que
Ejemplo: 
Ejemplo de Unicidad ~ Eliminación Controlada8 Es decir, el tablero generado posee una única solución. Dado que el algoritmo implementa el siguiente principio lógico, expresado en la ecuación de diferencias:
$$
U_{k+1}=U_{k}\text{∖} \{m_{ij}\} \iff
$$
$$
(|Sol(U_{k+1})|=1
$$
$$
\text{En caso contrario}
$$
$$
U_{k+1}=U_{k}
$$
Invariancia de la unicidad bajo eliminación controlada7
Este algoritmo no acepta una eliminación que produzca más de una solución. Por lo tanto, en cada paso se preserva la propiedad \( |Sol(U_{k+1})|=1 \). (Ver Diagrama de Flujo) Definiciones Sea \( M \) una matriz cuadrada de orden \( 9\times9 \), formada por \(81\) celdas cuyos elementos se denotan por \( m_{ij} \), con \( i,j \in \{0,1,2,\dots,8\} \). Cada elemento \( m_{ij} \) pertenece al conjunto \( D \) y se dispone en la matriz respetando las restricciones fundamentales del Sudoku clásico. En términos formales, la matriz \( M \) debe satisfacer simultáneamente las siguientes condiciones:
ii) Cada columna contiene exactamente una vez cada elemento del conjunto \( D \). iii) La matriz puede particionarse en nueve submatrices de tamaño \( 3\times3 \), y cada una de ellas contiene también todos los elementos del conjunto \( D \) sin repetición.  Matriz \( M_{9\times9} \) particionada en 9 submatrices de \( 3\times3 \) El proceso de llenado de la matriz \( M \) con valores \( m_{ij}\in D \) se realiza verificando, entre otras condiciones, que la suma de los elementos de cada fila y de cada columna sea igual a \( 45 \), es decir, Esta propiedad constituye una consecuencia directa de la utilización del conjunto \( D \). La configuración matemática del algoritmo empleado para garantizar una solución única se estructura en tres etapas principales, que se describen a continuación. 1. Generación de la Solución Completa
Generar
En la primera etapa se construye un tablero completamente resuelto mediante un algoritmo basado en el método de backtracking (búsqueda con retroceso). Este método consiste en una exploración sistemática del espacio de soluciones bajo restricciones. El algoritmo asigna valores a cada celda de la matriz y, si en algún punto no existe una opción válida, retrocede al estado anterior y continúa explorando alternativas hasta completar correctamente toda la matriz. El procedimiento comienza generando permutaciones aleatorias del conjunto \( D \), las cuales se validan progresivamente para construir una matriz que cumpla simultáneamente todas las restricciones del Sudoku12.
Luego, el llenado de las celdas de la matriz \( M \) con los valores \( m_{ij} \in D \), donde \( i,j = \{0,1,2,..,8\} \) son índices, con los que se verifica que la sumatoria de cada fila y cada columna es igual a \( 45 \) (i.e.\( \sum m_{ij}=45 \) para cualquier fila o columna fija de los números de \( D \) 4). En la localización de valores durante el proceso de llenado de \( M \), se aplican las reglas de no repetición de un número ni en sus filas, ni en sus columnas y tampoco un número puede repetirse en su subcuadrante. Justamente, por eso un procedimiento restringido y aleatorio como backtracking, marca una diferencia con el método Montecarlo5, porque este método probabilístico se basa en la generación aleatoria de configuraciones, y no resulta apropiado para garantizar la obtención de una solución válida y, en particular, una solución única. La configuración del método matemático empleado para garantizar una solución única consta de tres etapas, que estarán representadas por tres botones en la aplicación desarrollada como explicación de la construcción del Sudoko. 2. Generación del Planteamiento
Puzzle
Una vez obtenida una solución completa válida, se procede a generar el planteamiento del Sudoku mediante la eliminación controlada de valores. Este proceso puede interpretarse como una aplicación inversa del algoritmo de construcción: se eliminan valores uno por uno, verificando en cada paso que el tablero resultante continúe teniendo una única solución. Si la eliminación de un valor produce múltiples soluciones posibles, dicho valor se restituye y el algoritmo continúa con otra celda. De esta forma se obtiene un tablero incompleto que conserva la propiedad fundamental de unicidad10. Desde una perspectiva matemática, este procedimiento puede interpretarse como la exploración de un árbol de decisiones11, en el cual cada eliminación representa una bifurcación y el algoritmo verifica continuamente la estabilidad estructural del sistema.
Entonces, se establecen las funciones que validarán las reglas del Sudocko por columnas y localizando las filas en la matriz \( M \) .Se generan los valores por celda mediante una arreglo (array) \( mm[] \), declarado como variable global.
Luego, invocando las funciones anteriores se comienza el llenado de la matriz \( M \). Se localizan valores en la celdas utilizando las referencias ID con DOM Javascript.
A efecto de armar el Puzzle, i.e. la segunda etapa del algoritmo, opera una serie de funciones:
3. Recuperación de la Solución
Solucionar
Finalmente, cuando el usuario visualiza el tablero incompleto, la solución permanece almacenada en una estructura auxiliar generada en la etapa inicial. Al activar el botón correspondiente, el algoritmo recupera dichos valores y completa automáticamente las celdas restantes, garantizando la coherencia lógica del resultado. Diagrama de Flujo Algoritmo Sudoku-U1  Síntesis Matemática del Algoritmo Sudoku-U1 En consecuencia, el algoritmo descrito no sólo permite generar tableros válidos, sino también garantizar formalmente la existencia de una única solución, lo que constituye una propiedad esencial en los sudokus clasificados como de tipo Platinum. Sea el conjunto finito \[ D=\{1,2,3,4,5,6,7,8,9\}. \] Se denomina configuración válida de Sudoku a toda matriz cuadrada \( M_{9\times9}=(m_{ij}) \) cuyos elementos pertenecen al conjunto \( D \) y satisfacen simultáneamente las siguientes condiciones:
ii) Para todo índice \( j \), la columna \( j \) contiene exactamente una vez cada elemento de \( D \). iii) Cada submatriz \( 3\times3 \) contiene exactamente una vez cada elemento de \( D \). Sea \( U \) una matriz \( 9\times9 \) que contiene valores del conjunto \( D \) en algunas de sus celdas y celdas vacías en las restantes. Se dirá que \( U \) es un Sudoku de solución única si existe exactamente una matriz \( M \) que complete \( U \) y que sea una configuración válida según la Definición 1. El algoritmo basado en búsqueda con retroceso (backtracking) permite construir una matriz \( M_{9\times9} \) que constituye una configuración válida de Sudoku. El algoritmo asigna valores del conjunto \( D \) a cada celda \( m_{ij} \) de la matriz de manera secuencial. En cada paso se selecciona un valor que no viole ninguna de las tres restricciones fundamentales: unicidad en la fila, unicidad en la columna y unicidad en el subcuadro \( 3\times3 \). Si para una celda determinada no existe ningún valor admisible, el algoritmo retrocede a la celda anterior y selecciona una nueva alternativa. Dado que el conjunto \( D \) es finito y el número de celdas es también finito, el procedimiento termina necesariamente después de un número finito de pasos. Además, en cada asignación se preservan las condiciones de la Definición 1, por lo que la matriz obtenida al finalizar el proceso es una configuración válida de Sudoku. Esto completa la demostración. El procedimiento de eliminación controlada de valores sobre una matriz solución \( M \), combinado con un verificador de unicidad basado en backtracking, permite generar un Sudoku con solución única. Sea \( M \) una matriz solución válida. El algoritmo elimina sucesivamente valores \( m_{ij} \) de la matriz y, después de cada eliminación, ejecuta un procedimiento de verificación que intenta reconstruir la solución. Si el verificador encuentra más de una solución posible, el valor eliminado se restituye. Por lo tanto, el algoritmo sólo conserva eliminaciones que no alteran la unicidad de la solución. Como el proceso termina cuando no es posible eliminar más valores sin perder unicidad, el resultado final es una matriz incompleta que posee exactamente una solución. Esto prueba el teorema. Entrada: conjunto \( D=\{1,2,3,4,5,6,7,8,9\} \). Etapa 1: Generación de una solución completa
Para cada celda \( m_{ij} \), seleccionar un valor de \( D \) que no viole las restricciones. Si no existe valor válido, retroceder a la celda anterior. Repetir el proceso hasta completar toda la matriz. Etapa 2: Generación del planteamiento
Eliminar su valor. Verificar si la solución sigue siendo única. Si no es única, restaurar el valor. Repetir hasta que no sea posible eliminar más valores. Etapa 3: Visualización y solución
Al solicitar la solución, recuperar la matriz original. Completar automáticamente las celdas vacías. Luego, el algoritmo garantiza formalmente la generación de sudokus válidos y de solución única. |
