Sudoku

Mi primera prueba de optimización tuvo como primera pregunta plantear el modelo matemático para resolver un Sudoku, bueno, en ese momento cometí un error garrafal, puse restricciones no lineales obteniendo 0 puntos y bueno como este fue uno de mis ramos favoritos, siempre me acorde de la mala experiencia.

Es por eso que hoy vengo a corregir aquel error del pasado.

Un Sudoku es un juego de ingenio que en reglas es muy simple, pero la verdad para mi es difícil de resolver, consiste en una grilla de 9×9 donde vienen unos números en algunas celdas mientras que otras están vacias, el puzle consiste el rellenar en cada fila hay y cada columna con numeros del 1 al 9 sin que se repitan.

La condición anterior tambien debe cumplirse para cada uno de los cuadrilateros de 3×3 de la siguiente imagen, donde se puede ver el puzle y su solución a la derecha:

Bueno esto matemáticamente se puede plantear del siguiente modo, e iré mostrando como se programa lo mismo en Python usando PuLP. Al final pondré todo el código en un repositrio GIT

Inicializar el problema matemático
prob = pulp.LpProblem("prob", pulp.LpMaximize)

Indices:

Fila f \in 1..9
fila = [x for x in range(9)]
Columna c \in 1..9
colum = [x for x in range(9)]
Valor v \in 1..9
val = [x for x in range(9)]

Variables de decisión

G_{f,c,v} \in [0,1] donde 1 significa que en la fila f, columna c se asigna el valor v.

game = [[[pulp.LpVariable(cat ='Binary', name ='fila {}, col {} es {}'.format(f, c, v+1)) for f in fila] for c in colum] for v in val]

Parámetros

P_{f,c,v} \in [0,1] donde 1 significa que en la fila f, columna c se debe asignar el valor v.

wb = load_workbook("sudoku.xlsx", data_only=True)
sh = wb.worksheets[0]
puzzle = [[[0 for k in range(9)] for j in range(9)] for i in range(9)]
for f,c,v in product(range(9),range(9),range(9)):
    if sh.cell(f+1,c+1).value == v+1:
        puzzle[f][v] = 1

Función Objetivo

max \sum_{f,c,v} G_{f,c,v} Maximizar el número de valores asignados

prob += pulp.lpSum(game)

Restricciones:

Se debe respetar el puzle

\forall f,c,v G_{f,c,v} \ge P_{f,c,v}

for f,c,v in product(fila,colum,val):
    prob += game[f][v] >= puzzle[f][v]
En cada celda solo puede haber un valor

\forall f,c \sum_v G_{f,c,v} \le 1

for f,c in product(fila,colum):
    prob += pulp.lpSum([game[f][v] for v in val]) <= 1
Cada Fila puede contener solo una vez cada valor

\forall f,v \sum_c G_{f,c,v} \le 1

for f,v in product(fila,val):
    prob += pulp.lpSum([game[f][v] for c in colum]) <= 1
Cada Columna puede contener solo una vez cada valor

\forall c,v \sum_f G_{f,c,v} \le 1

for c,v in product(fila,val):
    prob += pulp.lpSum([game[f][v] for f in fila]) <= 1
Cada cuadrilátero debe tener una vez cada valor

cc = indice del cuadrilátero en columna
cf = indice del cuadrilátero en fila
f = fila del cuadrilátero
c = columna del cuadrilátero
`$$ \forall cf,cc,v \in [1,2,3],[1,2,3],val \sum{f\in[1,2,3],c\in[1,2,3],v} G{f+3cf,f+3cc,v} \le 1 $$

for cf,cc,v in product(range(3),range(3),val):
    prob += pulp.lpSum([game[f+3*cf][v] for f,c in product(range(3),range(3))]) <= 1

Resolver el problema y obtener resultados

solver = pulp.getSolver('PULP_CBC_CMD')
prob.solve(solver)

sol = [[0 for k in range(9)] for j in range(9)]
for f,c,v in product(fila,colum,val):
    if(pulp.value(game[f][v]) > 0.9):
        sol[f] = v + 1

for f in fila:
    print(sol[f])
[6, 4, 3, 5, 1, 7, 9, 2, 8]
[8, 1, 5, 3, 2, 9, 7, 4, 6]
[2, 9, 7, 8, 6, 4, 3, 1, 5]
[9, 2, 8, 1, 7, 5, 6, 3, 4]
[4, 7, 1, 6, 3, 2, 5, 8, 9]
[5, 3, 6, 9, 4, 8, 1, 7, 2]
[7, 5, 9, 4, 8, 3, 2, 6, 1]
[3, 6, 4, 2, 5, 1, 8, 9, 7]
[1, 8, 2, 7, 9, 6, 4, 5, 3]

Que es igual al ejemplo:

Puedes encontrar el código completo en mi github:
https://github.com/danielfm123/sudoku_solver

Saludos!

Print Friendly, PDF & Email