Problemas de satisfacción de restricciones¶

Un problema de satisfacción de restricciones se caracteriza por contar por los tres siguientes elementos:

  1. Un conjunto de variables $X = \{X_1, X_2,...,X_n\}$.
  2. Un conjunto de dominios para cada una de las variables $D = \{D_1, D_2,..., D_n\}$ que responden a los valores que puede tomar cada variable $X_i$. Cada dominio consta de un conjunto de valores $D_i = \{v_1,v_2,...,v_k\}$.
  3. Un conjunto de restricciones $C$ que restringe el valor de los dominios en las variables según la forma en que estas se den. Cada restricción $C_j$ es una tupla de la forma $(scope, relation)$, donde:
    1. scope: refiere a las variables que participan en la restricción.
    2. relation: es una relación que define las restricciones en los valores que las variables de scope pueden tomar.

Un ejemplo de restricción es de la forma $(\{X_1, X_2\}, X_1 > X_2)$, que indica que la restricción implica a las variables $X_1$ y $X_2$ y que la variable $X_2$ está restringida a ser menor que $X_1$.

Aquí aplicamos un algoritmo de satisfacción de restricciones, backtracking, al problema de sudoku.

Construcción del problema¶

El sudoku consiste en un tablero de $9\times 9$ donde aparecen número de 1 a 9 y donde el objetivo es llenar las casillas vacías que satisfagan las restricciones de:

  1. Todos los números en los renglones deben ser distintos.
  2. Todos los números en las columnas deben ser distintos.
  3. Todos los números en las cuadrículas de $3\times 3$ que llenan el tablero deben ser distintos.

En términos formales, tenemos la siguiente formalización del problema:

  1. Las variables $X_{i,j}$, con $i,j=1,...,9$ (se tienen $9\times 9=81$ variables), correspondientes a cada una de las casillas, aquí codificamos estas variables con los valores $(i,j)$ que corresponden a sus coordenadas en el tablero.
  2. El dominio es el mismo para cada variable, pues todas pueden tener valores numéricos $D_i = \{1,2,...,9\}$.
  3. Las restricciones $C_i$ corresponden a los casos anteriores en que todas las variables son distintas, lo cual determinamos por la función alldiff:
    1. Para toda $i$, se tiene la restricción $$\Big(\{X_{i,1},X_{i,2},...,X_{i,9}\},\mathrm{alldiff}(X_{i,1},X_{i,2},...,X_{i,9})\Big)$$
    2. Para toda $j$, se tiene la restricción $$\Big(\{X_{1,j},X_{2,j},...,X_{9,j}\},\mathrm{alldiff}(X_{1,j},X_{2,j},...,X_{9,j})\Big)$$
    3. Para $i,j = 2, 5, 8$, se tienen restricciones $$\Big(\{X_{i-1,j-1},X_{i-1,j},X_{i-1,j+1},X_{i-1,j},X_{i,j},X_{i+1,j},X_{i+1,j-1},X_{i+1,j},X_{i,j+1}\},\mathrm{alldiff}(X_{i-1,j-1},X_{i-1,j},X_{i-1,j+1},X_{i-1,j},X_{i,j},X_{i+1,j},X_{i+1,j-1},X_{i+1,j},X_{i,j+1})\Big)$$

En primer lugar, definimos la función alldiff que nos permitirá identificar cuando todas las variables tengan valores diferentes.

In [1]:
import numpy as np
from itertools import combinations

def alldiff(variables):
    """Revisa si son diferentes todas las variables."""
    for x_i,x_j in combinations(variables, 2):
        if x_i == x_j:
            return False
        
    return True

Ahora procedemos a crear la clase de sudoku para simular el juego. En este caso, el tablero inicial constará de un número limitado de casillas llenas. Indicamos esto con un diccionario que asocia a cada casilla un valor. También definimos la función para poner un número en una casilla y varias funciones que nos permitirán determinar si el estado del tablero es final o no revisando si se cumplen las restricciones.

In [2]:
class Sudoku(object):
    """Simulación de sudoku"""
    def __init__(self, init_pos={(0,2):3,(0,4):2,(0,6):6,
                           (1,0):9,(1,3):3,(1,5):5,(1,8):1,
                           (2,2):1,(2,3):8,(2,5):6,(2,6):4,
                           (3,2):8,(3,3):1,(3,5):2,(3,6):9,
                           (4,0):7,(4,8):8,
                           (5,2):6,(5,3):7,(5,5):8,(5,6):2,
                           (6,2):2,(6,3):6,(6,5):9,(6,6):5,
                           (7,0):8,(7,3):2,(7,5):3,(7,8):9,
                           (8,2):5,(8,4):1,(8,6):3}):
        #Guarda el tablero
        self.board = None
        #Inicia las posiciones
        self.init_pos = init_pos
        #Agrega los números iniciales
        self.set_numbers()
        
    def __str__(self):
        return str(self.board)
        
    def set_numbers(self):
        """Inicia el tablero con números colocados."""
        self.board = np.zeros((9,9))
        for idx, value in self.init_pos.items():
            self.board[idx] = value
            
    def put(self,row,column,value):
        """Función para colocar número"""
        self.board[row,column] = value
            
    def check_rows(self):
        """Revisa que todos los renglones tengan números distintos"""
        diff = []
        for row in self.board:
            diff.append( alldiff(row) )
        return all(diff)
    
    def check_columns(self):
        """Revisa que todos las columnas tengan números distintos"""
        diff = []
        for row in self.board.T:
            diff.append( alldiff(row) )
        return all(diff)
    
    def check_boxes(self):
        """Revisa que todos los cuadros 3x3 tengan números distintos"""
        boxes = []
        for i in [0,3,6]:
            rows =  self.board[i:i+3] 
            box1, box2, box3 = rows[:,:3].reshape(9),rows[:,3:6].reshape(9),rows[:,6:].reshape(9)
            boxes.append( all([alldiff(box1),alldiff(box2),alldiff(box3)]) ) 
    
        return all(boxes)
    
    def is_final(self):
        """Revisa si se ha solucionado el problema"""
        return all([self.check_rows(), self.check_columns(), self.check_boxes()])

Algoritmo de backtracking para satisfacción de restricciones¶

Para solucionar el problema del sudoku usaremos el algoritmo de backtracking. Este algoritmo hace una búsqueda en busca de una solución con base en asignaciones parciales. Una asignación parcial en un problema de satisfacción de restricciones es una asignación de valores a las variables que deja algunas variables sin un valor asignado.

Una asignación consistente es una asignación de valores que satisface las restricciones. Así, una asignación parcial consistente será una asignación incompleta de valores, pero donde los valores asignados satisfacen las restricciones. Definimos dos funciones que nos harán posible hacer estas asignaciones.

La función select_unassigned_values nos regresará los valores del dominio de la variable que sean consistentes de acuerdo a la asignación parcial actual. La función check_grids nos permitirá ver si los cuadros de $3\times 3$ satisfacen las restricciones.

In [3]:
def select_unassigned_values(csp):
    """Asigna valores consistentes del dominio a cada variable."""
    #Guarda valores
    domains = []
    for i in range(9):
        for j in range(9):
            #Revisa si no hay números asignados
            if csp.board[i,j] == 0:
                #Valores de 1 a 9
                cell_values = np.array(range(1,10))
                #Regresa los valores que sean distintos
                cell_values = np.setdiff1d(cell_values,csp.board[i,:][np.where(csp.board[i,:] != 0)]).tolist()
                cell_values = np.setdiff1d(cell_values,csp.board[:,j][np.where(csp.board[:,j] != 0)]).tolist()
            else:
                #Mantiene los valores
                cell_values = [int(csp.board[i,j])]
            domains.append(cell_values)
    return domains

def check_grids(i,j,cell,csp):
    """Revisa si los boxes cumplen la restricción."""
    #Crea los boxes de 3x3
    boxes = np.lib.stride_tricks.sliding_window_view(csp.board, window_shape=(3,3))[::3, ::3]
    #Checa los boxes izquierdos
    if i < 3:
        if j < 3:
            return cell in boxes[0,0]
        elif j < 6: 
            return cell in boxes[0,1]
        else:
            return cell in boxes[0,2]
    #Checa los boxes de en medio
    elif i < 6:
        if j < 3:
            return cell in boxes[1,0]
        elif j < 6:
            return cell in boxes[1,1]
        else:
            return cell in boxes[1,2]
    #Choca los boxes derechos
    else:
        if j < 3:
            return cell in boxes[2,0]
        elif j < 6:
            return cell in boxes[2,1]
        else:
            return cell in boxes[2,2]

Finalmente, podemos definir el algoritmo de backtracking para resolver el problema del sudoku. El algoritmo tomará como estados las asignaciones parciales y cada acción (colocar un número) extenderá estas asignaciones, creando nuevas asignaciones parciales, hasta obtener una asignación completa. Si esta asignación satisface lo contrario, hemos acabado, de otra forma seguiremos buscando.

El algoritmo primero revisará cuáles casillas están vacías, es decir, cuáles variables deben de ser asignadas. Irá revisando cuáles son las posibles asignaciones consistentes hasta llenar el tablero; revisará entonces si se ha llegado a un estado final, y repetirá el proceso hasta alcanzar el estado final.

Se puede pensar al algoritmo de backtracking como una búsqueda en profundidad, donde se explora una asignación consistente que nos lleva a un nuevo estado, en este nuevo estado (asignación parcial) intentamos otra asignación consistente, si al final llegamos a un punto en que no se puede hacer una asignación consistente, repetiremos el proceso con otra asignación distinta.

In [4]:
def backtracking_sudoku(csp):
    """Función para solucionar el problema de sudoku por backtracking"""
    #Guarda los dominios posibles
    var = select_unassigned_values(csp)
    #Conteo
    count = 0
    #Revisa la solución
    solution = False
    #Revisa los renglones y columnas vacías
    rows = np.array(np.where(csp.board == 0))[0]
    cols = np.array(np.where(csp.board == 0))[1]
    #Asigna un diccionario de valores para estos
    assigned_values  = dict(zip(list(range(len(rows))), np.zeros(len(rows),dtype = int).tolist()))
    while solution == False:
        #Checa si ha llegado al final cuando el conteo supera los renglones no asignados
        if count >= len(rows):
            solution = csp.is_final()
            break

        #Índices de casillas vacías
        i = rows[count]
        j = cols[count]
        #Guarda los dominios consistentes
        domain_x = var[9*i+j]
        #Revisa los valores asignados
        v_k = assigned_values[count]
        while v_k < len(domain_x):
            #Toma un valor del dominio de X_k
            value = domain_x[v_k]
            #Si el valor está en el renglón avanza al siguiente
            if value in csp.board[i,:]:
                v_k += 1
                continue           
            #Si el valor está en la columna avanza al siguiente
            if value in csp.board[:,j]:
                v_k += 1
                continue
            #Si el valor está en el box avanza al siguiente
            if check_grids(i,j,value,csp):
                v_k += 1
                continue
            
            #Asigna el índice del valor al diccionario
            assigned_values[count] = v_k
            #Avanza en el conteo
            count += 1
            #Agrega el valor en la celda correspondiente
            csp.put(i,j,value)
            break
        
        #Si no es estado final
        else:
            #Se elimina la asignación de la casilla
            csp.board[i,j] = 0 
            #Se reinician los valores asignados en ese estado
            assigned_values[count] = 0
            #Se retrocede en el conteo
            count -= 1

Aplicación de backtracking a un tablero de sudoku¶

Iniciamos un tablero de sudoku con una configuración que sabemos que tiene solución. Esta se puede ver a continuación:

In [5]:
sudoku = Sudoku()
print('Asignación inicial:\n')
print(sudoku)

Asignación inicial:

[[0. 0. 3. 0. 2. 0. 6. 0. 0.]
 [9. 0. 0. 3. 0. 5. 0. 0. 1.]
 [0. 0. 1. 8. 0. 6. 4. 0. 0.]
 [0. 0. 8. 1. 0. 2. 9. 0. 0.]
 [7. 0. 0. 0. 0. 0. 0. 0. 8.]
 [0. 0. 6. 7. 0. 8. 2. 0. 0.]
 [0. 0. 2. 6. 0. 9. 5. 0. 0.]
 [8. 0. 0. 2. 0. 3. 0. 0. 9.]
 [0. 0. 5. 0. 1. 0. 3. 0. 0.]]

Aplicando el algoritmo de backtracking podemos, entonces, ver que llegamos a una asignación que satisface las restricciones. Por tanto, hemos resuelto este tablero de sudoku:

In [6]:
backtracking_sudoku(sudoku)
print('Solución propuesta:\n')
print(sudoku)

Solución propuesta:

[[4. 8. 3. 9. 2. 1. 6. 5. 7.]
 [9. 6. 7. 3. 4. 5. 8. 2. 1.]
 [2. 5. 1. 8. 7. 6. 4. 9. 3.]
 [5. 4. 8. 1. 3. 2. 9. 7. 6.]
 [7. 2. 9. 5. 6. 4. 1. 3. 8.]
 [1. 3. 6. 7. 9. 8. 2. 4. 5.]
 [3. 7. 2. 6. 8. 9. 5. 1. 4.]
 [8. 1. 4. 2. 5. 3. 7. 6. 9.]
 [6. 9. 5. 4. 1. 7. 3. 8. 2.]]