Cuaderno de trabajo de:
El sudoku es un puzzle lógico en el que tenemos que rellenar una cuadrícula 9x9 introduciendo en cada casilla un número del 1 al 9:
https://es.wikipedia.org/wiki/Sudoku
Sudoku online (hay otras páginas pero por favor usad ésta)
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/solo.html
Al comenzar el sudoku sólo está relleno en parte, y tenemos que encontrar los números que faltan.
Lo representamos como una matriz de enteros.
El sudoku solo puede tomar el valor 1,2,3,4,5,6,7,8,9 (sólo 9 valores enteros) en cada casilla. Un 0 indica que la casilla está vacía.
import matplotlib.pyplot as plt
import numpy as np
from optlang import Model, Variable, Constraint, Objective
FACIL = np.array([
[0,0,6,0,3,1,0,0,2],
[5,1,0,0,0,0,0,4,8],
[0,0,2,7,0,5,0,0,0],
[9,0,8,0,0,3,0,0,0],
[0,0,0,1,0,8,0,0,0],
[0,0,0,5,0,0,9,0,7],
[0,0,0,8,0,6,1,0,0],
[6,2,0,0,0,0,0,5,4],
[1,0,0,2,5,0,3,0,0],
])
MUY_DIFICIL=np.array([
[0,0,0,0,5,0,0,0,0],
[0,0,0,0,9,1,0,4,0],
[0,4,0,3,0,0,6,0,5],
[0,0,4,0,0,0,5,0,0],
[6,0,0,9,0,5,0,0,1],
[0,0,1,0,0,0,7,0,0],
[9,0,5,0,0,2,0,8,0],
[0,2,0,6,3,0,0,0,0],
[0,0,0,0,7,0,0,0,0],
])
#Atencion a los índices de fila y columna que empiezan por cero
#Elemento
print(FACIL[0,0])
#Fila
print(FACIL[0,:])
#Columna
print(FACIL[:,0])
print(FACIL)
Es tentador usar variables c[j,k], donde c[j,k] es el número en la fila j y la columna k, exigir que deban tomar solo valores enteros e intentar imponer que por ejemplo los números en la fila 1, columna 2 (c[1,2]) y en la fila 1 columna 7 (c[1,7]) tienen que ser distintos.
Pero no podemos imponer que dos números sean distintos, sólo podemos poner igualdades y desigualdades (=, <=, >=).
Por eso nos vemos obligados a usar variables binarias c[j,k,n], que se interpretan de esta forma:
c[j,k,n] = 1 si en la fila j columna k el número es n.c[j,k,n] = 0 si en la fila j columna k el número no es n.Almacenamos las variables en un dict. Las filas y columnas comienzan en 0, para mantener la convención habitual en python.
Para trabajar con estas variables lo primero que tenemos que hacer es asegurarnos de que en la fila j columna k no puede haber dos números distintos. Por lo tanto, exactamente una de las variables debe ser 1, lo que podemos imponer con una sola desigualdad
c[j,k,1] + c[j,k,2] + c[j,k,3] + c[j,k,4] + c[j,k,5] + c[j,k,6] + c[j,k,7] + c[j,k,8] + c[j,k,9] == 1
Esta desigualdad se puede escribir de forma más compacta así
sum(c[j,k,n] for n in N19) == 1
Y anidando bucles podemos imponer estas restricciones para todas las casillas:
#Solo un numero en cada posicion
for j in range(9):
for k in range(9):
#La suma de las variables 0/1
suma_variables_fila_j_col_k = sum(c[j,k,n] for n in N19)
constraints.append(Constraint(suma_variables_fila_j_col_k, lb= 1, ub=1))
Además, tenemos que imponer que no se puede repetir un número en una misma fila, en una columna, o en un bloque 3x3.
#Los números del 1 al 9
N19 = range(1,10)
def SUDOKU(data):
#c[j,k,n] = 1 si el numero en la posicion j,k es n
#c[j,k,n] = 0 si el numero en la posicion j,k **no** es n
#los indices de fila y de columna van de 0 a 8
# (es el mismo criterio que siguen los arrays en python)
#el numero n puede ser un entero enre 1 y 9, o 0 si la casilla esta vacia
c = {(j,k,n):Variable('x%d%d_%d'%(j,k,n), type='binary') for n in N19
for k in range(9)
for j in range(9)
}
constraints = []
#Datos (casillas a rellenas)
for j in range(9):
for k in range(9):
#Datos (recuerda que los indices de fila de un array van de 0 a 8)
d = data[j,k]
if d>0:
constraints.append(Constraint(c[j,k,d], lb=1))
#Solo un numero en cada posicion
for j in range(9):
for k in range(9):
#La suma de las variables 0/1
suma_variables_fila_j_col_k = sum(c[j,k,n] for n in N19)
constraints.append(Constraint(suma_variables_fila_j_col_k, lb= 1, ub=1))
#No se puede repetir un numero en cada fila
#Para cada fila
for j in range(9):
for n in N19:
#La suma de las variables 0/1
suma_variables_fila_j_numero_n = sum(c[j,k,n] for k in range(9))
constraints.append(Constraint(suma_variables_fila_j_numero_n, lb= 1, ub=1))
#No se puede repetir un numero en cada columna
#Para cada columna
for k in range(9):
for n in N19:
#La suma de las variables 0/1
suma_variables_col_k_numero_n = sum(c[j,k,n] for j in range(9))
constraints.append(Constraint(suma_variables_col_k_numero_n, lb=1, ub=1))
#No se puede repetir un numero en cada bloque 3x3
#Para cada bloque
for a in range(3):
for b in range(3):
for n in N19:
suma_variables_bloque_ab_numero_n = sum(
c[3*a+ra,3*b+rb,n]
for ra in range(3)
for rb in range(3)
)
constraints.append(Constraint(suma_variables_bloque_ab_numero_n, lb=1, ub=1))
obj = Objective(1, direction='max')
model = Model(name='Sudoku')
model.objective = obj
model.add(constraints)
return c,model
%%time
c, model = SUDOKU(FACIL)
status = model.optimize()
print("status:", model.status)
def muestra_SUDOKU(c):
M = np.zeros((9,9), dtype=np.int8)
for j in range(9):
for k in range(9):
for n in N19:
if c[j,k,n].primal:
#Rellenamos el array M
#recuerda que los indices de fila de un array van de 0 a 8
M[j,k]= n
return M
FACIL
muestra_SUDOKU(c)
%%time
c, model = SUDOKU(MUY_DIFICIL)
status = model.optimize()
print("status:", model.status)
MUY_DIFICIL
muestra_SUDOKU(c)
Ejercicio 1 Entra en la página web:
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/solo.html
elige un sudoku y resuélvelo con el código anterior. Comprueba la solución escribiendo los números en la web anterior.
Ejercicio 2 El código anterior impone que una solución del problema MixedIntegerLinearProgram tiene que ser una solución del sudoku.
Investiga qué pasa si le pides al programa que resuelva un sudoku con datos incompatibles, es decir, un sudoku que no se puede resolver.
Ejercicio 3 En el ejercicio anterior, es fácil encontrar un sudoku imposible de resolver si por ejemplo repetimos un número dos veces en la misma fila, columna, o bloque 3x3. Es decir, violando una de las restricciones fundamentales que definen el sudoku.
Piensa cómo puedes encontrar un sudoku parcialmente relleno de modo que los números que están en la cuadrícula no violen ninguna de las restricciones fundamentales (ningún número se repite en la misma fila, columna o bloque 3x3), y que sin embargo, no tenga solución, es decir, que no se pueda rellenar por completo.
Investiga qué pasa si le pides al programa que resuelva este sudoku:
Ejercicio 4 En el caso anterior, supongamos que nos interesa intentar rellenar tantos números como sea posible, pero permitiendo que haya casillas sin rellenar.
Entre todas las variables xjk_n para la fila j columna k y cualquier número n, permitimos que haya una, o también ninguna, que tomen el valor 1. Pero no permitimos que haya más de una:
xjk_1 + xjk_2 + xjk_3 + xjk_4 + xjk_5 + xjk_6 + xjk_7 + xjk_8 + xjk_9 <= 1O, en forma compacta:
suma_variables_fila_j_col_k = sum(c[j,k,n] for n in N19)
debe tener una cota superior de 1:
Constraint(suma_variables_fila_j_col_k, ub=1)
También es necesario relajar las otras restricciones: que ya no sea necesario poner exactamente un número en cada fila, sino que sea posible que en la fila 1 el número 3 aparezca 1 vez, o ninguna. Lo mismo para todas las filas, para todos los números; lo mismo para las columnas y los bloques 3x3.
También es importante pensar despacio la función objetivo, a la que no habíamos prestado mucha atención.
Queremos pedir al MixedIntegerLinearProgram que intente rellenar el máximo de casillas, lo que se consigue cuando, dentro de las restricciones previstas, toman el valor 1 cuantas más variables c[j,k,n] mejor.
x00_1 + x00_2 + ... + x88_9
En notación compacta, se trata de maximizar:
sum(c[j,k,n] for j in range(9) for k in range(9) for n in N19)
IMPOSIBLE = np.array([
[0,0,6,0,3,1,0,0,2],
[5,1,0,0,0,0,0,4,8],
[0,0,2,7,0,5,0,0,0],
[9,0,8,0,0,3,0,0,0],
[0,4,0,1,0,8,0,0,0],
[0,0,0,5,0,0,9,0,7],
[0,0,0,8,0,6,1,0,0],
[6,2,0,0,0,0,0,5,4],
[1,0,0,2,5,0,3,0,0],
])
#Los números del 1 al 9
N19 = range(1,10)
def SUDOKU_RELAX(data):
#c[j,k,n] = 1 si el numero en la posicion j,k es n
#c[j,k,n] = 0 si el numero en la posicion j,k **no** es n
#los indices de fila y de columna van de 0 a 8
# (es el mismo criterio que siguen los arrays en python)
#el numero n puede ser un entero enre 1 y 9, o 0 si la casilla esta vacia
### TRABAJA AQUI
return