SOLUCIÓN DE SUDOKU POR MEDIO DE

PROGRAMACIÓN LINEAL ENTERA MIXTA

Nombre Código Nota solicitada
Manuel Soto T00046482
Jesus De La Vega T00028464

4.0

Resumen
Un Sudoku es un juego de rompecabezas muy conocido y expendido entre las personas a lo largo
del mundo. Dada su recursividad, es un juego muy distribuido en diarios, periódicos, revistas,
páginas web, aplicaciones de celular, etc. Sin embargo, es un juego de difícil resolución por lo que
requiere de mucho tiempo para su solución. En este trabajo se genera un aplicativo para resolver el
problema del Sudoku como un problema de programación lineal entera mixta, y se evalúan el
método de solución aplicando a diversas instancias de prueba generadas aleatoriamente.

Introducción
El Sudoku es un rompecabezas lógico engañosamente simple que ha capturado un gran interés en
todo público. Los rompecabezas publicados, que consisten en una cuadrícula de 9 × 9 y se subdividen
en "mini-cuadriculas" de tamaño 3×3, son lo suficientemente simples en concepto para que amplios
sectores de la población intenten su solución. Aunque los sudokus conservan un desafío suficiente
para la mayoría, es necesario la aplicación de varios métodos de razonamiento. El interés académico
en esta clase de rompecabezas ha crecido en los últimos años, debido tanto a su relación con otras
estructuras combinatorias (en particular los cuadrados latinos) como a su conexión demostrada con
muchos problemas del mundo real. ( Jones, Perkins, & Roach, 2007)

Este rompecabezas ha tomado la forma de una prueba matemática de propiedades específicas y ha

generado mucho interés entre las personas, incluso en la búsqueda y aplicación de técnicas de
optimización para su solución. En este documento, se destacan características importantes del
sudoku y se muestran pruebas de varios de ellos.

1
Estado del arte
El Sudoku es un rompecabezas que se subdivide en ‘mini-cuadrículas’ o ‘sub-rejillas’ de tamaño 3×3,
con cada una de las 81 celdas de la cuadrícula, que se rellenará con los dígitos 1 a 9 de modo que
cada dígito aparezca exactamente una vez en cada fila, columna y en cada mini-cuadrícula. De
hecho, aunque los rompecabezas Sudoku publicados son generalmente de 3×3 en tamaño, se
pueden usar otras dimensiones, y para cada dimensión n hay n×n cuadriculas (Gupta, 2006). Sin
embargo, no todos los tamaños de Sudoku tienen mini-cuadriculas de tamaño único. Como
ejemplos, un Sudoku de 6×6 (conocido como Rudoku) puede tener mini-cuadriculas de tamaño 3×2
o 2×3 (aunque estos son esencialmente simplemente una rotación de uno a otro), y un Sudoku de
12×12 puede tener mini-cuadriculas de tamaño 3×4 o 6×2 (lo que genera a rompecabezas muy
diferentes). Los rompecabezas publicados muestran cuadrículas incompletas, con varias celdas
predefinidas con dígitos fijos o dados. ( Jones, Perkins, & Roach, 2007)

Las raíces de Sudoku se encuentran en el desarrollo de Euler de los cuadrados latinos en 1783, es
decir, las cuadrículas de Sudoku son casos especiales de Cuadrados latinos que poseen una
restricción adicional sobre las mini-cuadriculas. Rompecabezas similares al Sudoku se estaban
produciendo en periódicos franceses ya desde fines del siglo XIX. (Boyer, 2006)

Sin embargo, el Sudoku propiamente dicho, no surgió hasta fines de la década de 1970, cuando la
editorial de Nueva York Dell Magazines publicó los primeros acertijos con el nombre "Number
Place". En 1984, el grupo de rompecabezas japonés Nikoli agregó la restricción de que las posiciones
elegidas de los dígitos iniciales dados deben formar un patrón simétrico. Nikoli registró el
rompecabezas bajo el nombre de Sudoku, con "Su" refiriéndose al número y "Doku" a sencillo
(derivado de la frase Suuji wa dokushin ni kagiru, que significa " the number is limited to being single,
or unmarried). Los acertijos de Sudoku de Nikoli se hicieron inmediatamente populares en un país
donde los acertijos numéricos se han preferido tradicionalmente a los acertijos de palabras, debido
a un alfabeto que es inherentemente inadecuado para crucigramas. (Smith, 2005)

En los últimos años, el rompecabezas ha ganado popularidad mundial, por ejemplo, se lanzó en The
Times el 12 de noviembre de 2004. Han surgido respaldo de al valor y la utilidad de Sudoku, incluida
la revista Teachers, que recomienda Sudoku como "ejercicio mental" en las aulas, y se sugirió incluso
que la finalización regular de los rompecabezas de Sudoku podría retrasar la progresión del
Alzheimer y otras condiciones. ( Jones, Perkins, & Roach, 2007)

Los números en los rompecabezas de sudoku se usan por conveniencia. Funciona igual de bien si los
números se reemplazan con letras, formas, colores u otros símbolos. Sudoku no es un rompecabezas
matemático o aritmético; Las relaciones aritméticas entre números son absolutamente irrelevantes.
De hecho, Penny Press usa letras en su versión llamadas scramblets; Knight Features Syndicate
también usa letras en su Sudoku Word. (Santos & Palomino, Solving Sudoku Puzzles with Rewriting
Rules, 2007)

2
 Figura 1. Sudoku de letras

Fuente: (Santos & Palomino, Solving Sudoku Puzzles with Rewriting Rules, 2007)

Al resolver un sudoku, miles de lectores de periódicos aplican esquemas de propagación clásicos en

la programación de restricciones como X-wing y wordfish, patrones que cubren varias filas y
columnas, buscando un número candidato que pueda eliminarse de otras listas en las
correspondientes columnas y filas, para encontrar una solución. Se sabe que el problema general
de resolver rompecabezas de sudoku en n × n es NP-Hard. Esto da una indicación vaga de por qué
los sudokus son difíciles de resolver, pero para tableros de tamaño finito, el problema también es
finito y puede resolverse con algoritmos. Sin embargo, para un tablero de partida no trivial, el
problema es muy grande, por lo que algunos métodos no son factibles. (Santos & Palomino, Solving
Sudoku Puzzles with Rewriting Rules, 2007)

Los tipos de razonamiento lógico empleados por los solucionadores humanos también pueden
incorporarse a los solucionadores automáticos, y muchos de estos programas están actualmente
disponibles comercialmente. Estos tienden a ser bastante lentos para alcanzar soluciones a los
acertijos, y muchos también emplean una cierta cantidad de "prueba y error". De hecho, El examen
de un gran número de permutaciones se considera inevitable. ( Jones, Perkins, & Roach, 2007)
Una forma estándar de resolver sudoku es mediante la aplicación de la recursividad. Un algoritmo
donde la solución depende de soluciones a instancias más pequeñas del problema de referencia.
Uno verifica todas las combinaciones (para cada celda considera todos los enteros entre 1 y 9) y se
detiene al encontrar una solución que satisfaga las restricciones. (Santos, Solving Sudoku Puzzles
with Rewriting Rules, 2007) (Gabor & Woeginger, 2010). Alternativamente, podemos aplicar la
optimización de programación entera. (Barlett, A., Chartier, Langville, & Rankin, 2008). Como, de
hecho, no hay una función que queramos maximizar, el problema de sudoku puede llamarse un
problema de satisfacción o factibilidad. Los requisitos son incluir en cada fila, columna y cuadrado
de 3x3 (de los nueve adyacentes) todos los enteros del 1 al 9. Las celdas conocidas pueden tratarse
como restricciones adicionales.

Otros métodos son aplicables para resolver el problema tradicional del sudoku, como técnicas
clásicas de Metaheurísticas (Lewis, 2007) (Moon, Gunther, & Kupin, 2009); técnicas de optimización
dispersa (sparse optimization technique) (Tang, Wu, & Zhu, 2015). También Conjunctive Normal
Form (CNF) se usa a menudo para producir diferentes codificaciones del problema ( Jones, Perkins,
& Roach, 2007), para lograr soluciones de manera más rápida o confiable.

3
Descripción del problema
Un Sudoku clásico de 3x3 consiste en completar una cuadrícula de nueve por nueve (como se
menciona anteriormente, existen variaciones), de modo que cada fila, columna y sub-cuadrícula de
tres por tres contenga solo uno de un valor entero (del 1 al 9). (Tang, Wu, & Zhu, 2015) (Morgan,
2017) En otras palabras, no se puede ingresar otro “1” en la primera fila, la primera columna o la
primera sub-cuadrícula del Sudoku. Al principio, varias celdas ya pueden tener números
preestablecidos. La siguiente figura detalla la idea general del sudoku.

Un solo “4” en esta columna

Un solo “4” en esta

Un solo “4” en esta fila
sub-cuadricula

Figura 2. Ejemplo de Sudoku

Como hay nueve valores con los que se puede llenar cada cuadro, a lo largo de cada una de las nueve
filas y nueve columnas, se tiene 9³ = 729 parámetros. A diferencia de muchos problemas, no hay
solución para un sudoku que sea mejor que otro. En este caso, se desea encontrar cualquier solución
factible, que satisfaga con todas las limitaciones del problema. (Morgan, 2017)

En la página web [Link] puede encontrar una aplicación para generar escenarios para
el juego, donde clasifica el juego como Fácil, Medio, Difícil, Experto.

4
Modelo matemático
El modelo matemático generado, fue basado en el propuesto por (Barlett, A., Chartier, Langville, &
Rankin, 2008). Considere un sudoku como una matriz de 3 dimensiones de tamaño (𝑘, 𝑘, 𝑘) donde
𝑘 es el tamaño del sudoku:

Figura 3. Codificación del Sudoku

La imagen anterior muestra un sudoku de tamaño 4x4, donde 𝑖 representa las filas y 𝑗 las columnas.
Cada celda (𝑖, 𝑗) está compuesta por un vector de tamaño 𝑘 que representa los posibles valores 𝑛
que puede tomar esa celda.

Con esto se puede definir:

Parámetros:
𝑘: 𝐷𝑖𝑚𝑒𝑛𝑠𝑖ó𝑛 𝑑𝑒𝑙 𝑠𝑢𝑑𝑜𝑘𝑢
𝑡𝐶𝑎𝑗𝑎: 𝐷𝑖𝑚𝑒𝑛𝑠𝑖ó𝑛 𝑑𝑒 𝑙𝑎𝑠 𝑐𝑎𝑗𝑎𝑠 𝑑𝑒𝑙 𝑠𝑢𝑑𝑜𝑘𝑢
𝑆𝑢𝑑𝑜𝑘𝑢𝑖𝑗 : 𝑉𝑎𝑙𝑜𝑟 𝑝𝑟𝑒𝑑𝑒𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑑𝑜 𝑑𝑒 𝑙𝑎 𝑐𝑒𝑙𝑑𝑎 (𝑖, 𝑗)

Variables:
1 𝑠𝑖 𝑒𝑙 𝑣𝑎𝑙𝑜𝑟 𝑛 = 1 … 𝑘 𝑠𝑒 𝑢𝑏𝑖𝑐𝑎 𝑒𝑛 𝑙𝑎 𝑐𝑒𝑙𝑑𝑎 (𝑖, 𝑗)
𝑥𝑖𝑗𝑛 : {
0 𝑑𝑙𝑐

Modelo:
𝑘 𝑘 𝑘

min 𝑍0 = ∑ ∑ ∑ 𝑥𝑖𝑗𝑛
𝑖=1 𝑗=1 𝑛=1

NOTA: Vale aclarar que el valor de la función objetivo tiene poca importancia para este modelo, ya
que solo es necesario que se cumpla con todas las restricciones. Por lo tanto, se puede especificar
una función objetiva arbitraria. (Barlett, A., Chartier, Langville, & Rankin, 2008)

5
S.A.

1) Asignar los valores predeterminados:

𝑥𝑖𝑗𝑛 = 1 ∀ 𝑖, 𝑗, 𝑛 = 1 … 𝑘 | 𝑛 = 𝑆𝑢𝑑𝑜𝑘𝑢𝑖𝑗

2) No se puede repetir ningún valor en cada columna

∑ 𝑥𝑖𝑗𝑛 = 1 ∀ 𝑗, 𝑛 = 1 … 𝑘
𝑖=1

3) No se puede repetir ningún valor en cada fila

∑ 𝑥𝑖𝑗𝑛 = 1 ∀ 𝑖, 𝑛 = 1 … 𝑘
𝑗=1

4) No se puede repetir ningún valor en cada celda

∑ 𝑥𝑖𝑗𝑛 = 1 ∀ 𝑖, 𝑗 = 1 … 𝑘
𝑛=1

5) No se puede repetir ningún valor en cada caja

𝑎×𝑡𝐶𝑎𝑗𝑎 𝑏×𝑡𝐶𝑎𝑗𝑎

∑ ∑ 𝑥𝑖𝑗𝑛 = 1 ∀ 𝑛 = 1 … 𝑘, 𝑎, 𝑏 = 1 … 𝑡𝐶𝑎𝑗𝑎
𝑖=𝑎×𝑡𝐶𝑎𝑗𝑎−𝑡𝐶𝑎𝑗𝑎+1 𝑗=𝑏×𝑡𝐶𝑎𝑗𝑎−𝑡𝐶𝑎𝑗𝑎+1

6) Restricciones sobre el tipo de variable

𝑥𝑖𝑗𝑛 ∈ {0,1} ∀ 𝑖, 𝑗, 𝑛 = 1. . 𝑘

6
Resultados numéricos
El modelo se codifico en GAMS 24.1.3. y se compilo en un computador con procesador Intel Core
i7-6700T con CPU de 2.8Ghz y memoria RAM-8GB.

Se muestran algunos resultados de instancias aleatorias:

2 3 4 2 1

4 1 2 3 4

2 2 1 4 3

1 4 3 1 2
Figura 4. Sudoku de 2x2 resuelto

2 1 9 3 8 5 7 6 4

2 1 9 8 7 3 4 6 2 1 5 9 8

5 7 4 3 6 8 5 7 9 4 1 3 2

6 5 8 1 9 2 6 4 5 3 8 7 1

6 4 8 5 1 2 6 7 3 4 9

7 9 6 4 7 3 9 1 8 2 5 6

6 8 4 7 5 6 8 1 3 9 4 2 7

3 4 5 3 4 2 8 7 6 9 1 5

9 5 2 6 1 9 7 5 4 2 6 8 3

Figura 5. Sudoku de 3x3 Resuelto

Para estos problemas el modelo es capaz de Tamaño del Tiempo

encontrar la solución óptima rápidamente. A problema computacional (seg)
continuación, se muestra una comparación 2x2 0.02
3x3 0.10
del tiempo medio de solución de problemas
4x4 0.19
de acuerdo al tamaño: 5x5 72.19
6x6 1000.05
Figura 6. Tiempo de ejecución
Como es de observar, para problemas de
mayor tamaño el tiempo de computacional es
considerablemente mayor. Para un problema
de 6x6 el tiempo requerido de solución es
mayor a 15 minutos. Sin embargo, sigue
siendo un tiempo significativamente bajo,
comparado con el tiempo estipulado para que
una persona sea capaz de resolver dicho
problema.
Figura 7. Gráfica tiempo de ejecución

7
Conclusiones

8
Bibliografía
Jones, S. K., Perkins, S., & Roach, P. (2007). Properties of Sudoku Puzzles. Proceedings of the 2nd
Research Student Workshop, At University of Glamorgan.

Barlett, A., Chartier, T., Langville, A., & Rankin, T. (2008). An Integer Programming Modelfor the
Sudoku Problem.

Boyer, C. (2006). Les ancêtres français du sudoku. Pour La Science.

Gabor, A., & Woeginger, G. (2010). How ∗not∗ to solve a Sudoku. Operations Research Letters.

Gupta, S. (March de 2006). Some results on su doku. Obtenido de Department of Theoretical

Physics.

Lewis, R. (2007). Metaheuristics can solve sudoku puzzles. Journal of Heuristics.

Moon, T., Gunther, J., & Kupin, J. (2009). , Sinkhorn solves Sudoku, . IEEE Transactions on
Information Theory.

Morgan, A. (2017). Using Integer Linear Programming to Solve Sudoku Puzzles. Obtenido de
Toward Data Science.

Santos, G. (2007). Solving Sudoku Puzzles with Rewriting Rules. Electronic Notes in Theoretical
Computer Science.

Santos, G., & Palomino, M. (2007). Solving Sudoku Puzzles with Rewriting Rules. Electronic Notes in
Theoretical Computer Science.

Smith, D. (2005). So you thought Sudoku came from the Land of the Rising Sun. The Observer.

Tang, Y., Wu, Z., & Zhu, C. (2015). A Warm Restart Strategy for Solving Sudoku by Sparse
Optimization Methods.

9
ANEXOS

10
Anexo A. Manual de usuario del
aplicativo
Entrada interfaz:
Primero ejecute el archivo de Excel [Link]. A continuación, se le mostrará la venta de inicio,
donde se tiene varios botones:
- set model
- view model
- generar sudoku
- cargar sudoku
- run gams

Set Model: Clic en el botón para seleccionar la respectiva ubicación del archivo de GAMS
“[Link]” en el computador.

View Model: Clic si requiere abrir el modelo en GAMS.

Load Sudoku: Clic en este botón le permitirá ingresar los datos de entrada (tamaño y celdas
predeterminadas) del sudoku que se quiere solucionar.

Runs GAMS: Clic para ejecutar GAMS y solucionar el sudoku cargado.

View Solution: Clic en este botón, y le permitirá ver la solución generada.

11
Load Sudoku:

Al dar clic en el primer botón, se mostrará la siguiente ventana:

Esta ventana tiene los siguientes botones:

NUEVO SUDOKU: Al dar clic, necesita digitar el tamaño del sudoku en la ventana de dialogo que se
le muestra. Una vez digitado el valor, dar clic en aceptar y se genera el cuadro del sudoku.

Digite los valores predeterminados en cada celda. Una vez digitado los valores dar clic en el botón
GENERAR PARÁMETROS.

GENERAR PARÁMETROS: Este botón genera el fichero con la información necesaria para cargar los
datos a GAMS. Una vez creado el fichero, copie los datos de la hoja Input en el archivo de entrada
de GAMS.

12
View Solution:

Una vez ejecutado el archivo de GAMS, retorne al menú principal y de clic en SUDOKU RESUELTO.
Esto lo lleva a la siguiente ventana:

En la ventana tiene un botones:

CARGAR SUDOKU: Este botón muestra la solución generada.

Si sudoku que se quiere solucionar no tiene solución, se muestra un cuadro de dialogo que indica
esta situación.

13
Puede hacer uso de esta sencilla herramienta para la solución de sudokus de cualquier tamaño.

14