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 \sumv 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 \sumc 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 \sumf 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