zudoku PL

1

Modelo de Programaci´ n Lineal, Sudoku
o
Felipe Ambiado Melissa Lumio Maricela Solorza
Universidad T´ cnica Federico Santa Mar´a
e
ı
Avenida Espa˜ a 1680, Valpara´so, Chile
n
ı
felipe.ambiado@alumnos.usm.cl.
melissa.lumio@alumnos.usm.cl.
maricela.solorza@alumnos.usm.cl

Resumen—El proyecto consiste en el descubrimiento del algoritmo matem´ tico que se emplea para crear elsudoku, haciendo
a
uso de la l´ gica y de la matem´ tica de forma que no interfieran en
o
a
´
el sentido comun, partiendo por un m´ todo cient´fico usado en
e
ı
clases “programaci´ n lineal entera” que nos permite alcanzar
o
soluciones optimas al problema y con el fin de un mejor
funcionamiento. El origen y la importancia de este proyecto
radica en poner a prueba los conocimientos logrados enclases,
demostrando nuestra capacidad de aprendizaje en la soluci´ n en
o
cuesti´ n.
o
Palabras Claves—Juego de l´ gica sudoku, soluci´ n sudoku, moo
o
delo matem´ tico de sudoku, restricci´ nes y modelo matem´ tico
a
o
a
de juegos, algoritmo y programaci´ n lineal entera son algunos
o
de los terminos que se necesitan para poder encontrar dicho
proyecto.

I.

´
INTRODUCCI ONSudoku es un pasatiempo que se public´ por primera vez
o
a finales de la d´ cada de 1970 y se populariz´ en Jap´ n en
e
o
o
´
1986, d´ ndose a conocer en el ambito internacional en 2005
a
cuando numerosos peri´ dicos empezaron a publicarlo en su
o
secci´ n de pasatiempos. ¿en qu´ cosiste mi problema? el
o
e
objetivo del sudoku es rellenar una cuadr´cula de n × n celdas
ı
dividida ensubcuadr´culas de m × m (tambi´ n llamadas
ı
e
“cajas o regiones” donde n = m2 ) con las cifras del 1 al n
partiendo de algunos n´ meros ya dispuestos en algunas de
u
las celdas. La soluci´ n del problema consiste en que los n
o
elementos diferenciados no se deben repetir en una misma
fila, columna o subcuadr´cula. Un sudoku est´ bien planteado
ı
a
´
si la soluci´ n es unica. Lanecesidad por la que se creo es
o
para desarrollar la capacidad de concentraci´ n donde combina
o
la diversi´ n con el aprendizaje, es una forma sana y atractiva
o
de emplear el tiempo libre.

vector es 1 para cuando el valor k corresponde a dicha
posici´ n y el resto son ceros. Esto se define con una variable
o
binaria y restricciones, las que indican que no se pueden
repetir n´ meros (k)en la misma fila, columna y caja, adem´ s
u
a
estas restricciones pueden mostrar datos iniciales que nos
limitan las posibles soluciones, idealmente llev´ ndonos a una
a
´
unica soluci´ n. Con este problema queremos descubrir cu´ l
o
a
ser´ la respuesta que nos arrojar´ , cuanto tiempo tardar´ y
a
a
a
cuantas soluciones iniciales debemos darle para que sea
´
una unica soluci´ n, o sies posible que arroje una soluci´ n
o
o
azarosa, sin ninguna referencia, lo que lo hace un problema
interesante y din´ mico.
a
La desventaja de utilizar este m´ todo es que tiene falencias
e
´
cuando no es una unica soluci´ n, no sabemos cu´ ntas
o
a
opciones de sudoku existen. Solo muestra una soluci´ n
o
cuando se le restringe con las suficientes condiciones o
valores iniciales,de lo contrario puede que exista m´ s de
a
una soluci´ n las que desconoceremos. La gran ventaja de
o
utilizar este tipo de condiciones o m´ todo de b´ squeda a es la
e
u
rapidez con la que se encuentra la soluci´ n para un problema
o
que puede tardar mucho tiempo.

III.
III-A.

´
MODELO MATEM ATICO O LP

Variables

Se define la variable a utilizar:
xk : variable binaria paracada celda (i, j) tal que
ij
xk =
ij

1
0

si la soluci´ n es k
o
en caso contrario

donde:
II.

ESTADO DEL ARTE

Para el desarrollo del sudoku de n × n casillas y n cajas
de tama˜ o m × m, donde m2 = n, definiremos variables
n
binarias para cada casilla (i, j), donde i representa la fila y j
la columna, mientras que k ser´ el valor de esa celda, el cual
a
corresponde a un n´...