Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas

Variables, dominios y restricciones, el grafo de restricciones, backtracking, las heurísticas MRV y LCV, la comprobación hacia delante, AC-3 y min-conflicts, coloreando las regiones de Chequia, con un sudoku y con ocho reinas.

15 minutos Matěj Žalmánek 2026-10-15

Serie Fundamentos de IA Parte 23 de 52

1. Mapa de la inteligencia artificial: qué es cada cosa y cómo encaja todo
2. Breve historia de la inteligencia artificial: de Turing a los modelos de lenguaje
3. Datos, modelo, entrenamiento, inferencia: los conceptos básicos en un solo ejemplo
4. Cómo leer la notación matemática: símbolos, subíndices, sumatorios y cuantificadores
5. Conjuntos y relaciones: las piezas con las que se construyen las definiciones en IA
6. Funciones y aplicaciones: por qué todo modelo de IA es una función
7. Lógica y demostraciones: las reglas con las que se razona en IA
8. Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales
9. Álgebra lineal para aprendizaje automático: vectores, matrices y por qué la IA sobre todo multiplica
10. Derivadas, gradiente y regla de la cadena: cómo sabe un modelo en qué dirección aprender
11. Descenso de gradiente: cómo aprende un modelo
12. Qué es la probabilidad: del lanzamiento de un dado a los axiomas de Kolmogórov
13. Probabilidad condicionada y teorema de Bayes: cómo cambiar una estimación cuando te enteras de algo nuevo
14. Variable aleatoria y función de distribución: una sola función que lo dice todo sobre la distribución
15. Función de densidad y función de probabilidad: por qué una variable continua tiene probabilidad cero en cada punto
16. Esperanza, varianza y covarianza: dónde está una distribución, qué anchura tiene y qué se relaciona con qué
17. Resumen de las distribuciones de probabilidad: Bernoulli, binomial, Poisson, uniforme, normal y exponencial
18. Ley de los grandes números y teorema central del límite: por qué las medias se comportan de forma tan predecible
19. Estadística y estimación de parámetros: máxima verosimilitud, MAP e intervalos de confianza
20. Teoría de la información: entropía, entropía cruzada y divergencia KL, el origen de las funciones de pérdida
21. Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones
22. Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search
23. Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas
24. Lógica y sistemas basados en conocimiento: encadenamiento hacia delante y hacia atrás, resolución y sistemas expertos
25. Planificación: STRIPS, el mundo de bloques, heurísticas a partir de la relajación y la planificación en los agentes de IA
26. Búsqueda local y recocido simulado: un viajante por las capitales regionales checas
27. Algoritmos genéticos: población, cruce, mutación y selección en una mochila para la excursión
28. Estrategias evolutivas y programación genética: de la regla de un quinto a la ley de Kepler
29. Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto
30. Optimización por enjambre de partículas: inercia, experiencia propia y experiencia del enjambre
31. Neuroevolución: evolución de los pesos y la forma de las redes neuronales, y el algoritmo NEAT
32. Conjuntos difusos y funciones de pertenencia: cómo escribir «algo cálido»
33. Lógica difusa y probabilidad: por qué «algo cálido» no significa «probablemente cálido»
34. Lógica difusa: t-normas, implicaciones y reglas SI–ENTONCES
35. Control difuso: Mamdani y Sugeno, del ventilador al péndulo invertido sobre un carro
36. Agrupamiento difuso: el algoritmo fuzzy c-means y los puntos entre clusters
37. Sistemas neuro-difusos (ANFIS): reglas difusas que aprenden de los datos
38. Cadenas de Markov: matriz de transición, distribución estacionaria y PageRank
39. Modelos ocultos de Márkov: el algoritmo de Viterbi y el casino deshonesto
40. Redes bayesianas: por qué está mojada la hierba y qué significa eso para el aspersor
41. El filtro de Kalman: cómo estimar a partir de mediciones imprecisas dónde está un coche y a qué velocidad va
42. Tipos de aprendizaje automático: supervisado, no supervisado, semisupervisado y más
43. Prompts, contexto y RAG: cómo darle a un modelo la información correcta
44. Autocodificadores variacionales (VAE): imágenes nuevas a partir de un espacio latente continuo
45. Redes generativas adversarias (GAN): el falsificador contra el detective
46. Modelos de difusión: cómo el ruido puro se convierte en una imagen
47. Procesos de decisión de Markov: estados, acciones, recompensas y ecuaciones de Bellman
48. Q-learning y DQN: aprender el valor de las acciones, de la tabla a la red neuronal
49. Gradiente de la política y PPO: aprender directamente la política
50. Cómo funciona un agente de IA: un modelo de lenguaje en un bucle con herramientas
51. Programación con agentes de IA: encargo, pruebas y revisión
52. Evaluación y seguridad de los sistemas de IA: cómo medir y cómo vigilar

Temario completo de la serie 52 de 83 temas publicados

Un horario escolar en el que ningún profesor da clase a dos grupos a la vez. Un sudoku. La colocación de componentes en una placa, los turnos de un hospital, la asignación de aviones a puertas de embarque. Todos estos problemas tienen en común que no buscamos un camino, sino una asignación: dar a cada variable un valor de modo que se cumplan todas las reglas a la vez. A un problema así se le llama problema de satisfacción de restricciones y, a diferencia de la búsqueda general, tiene una gran ventaja: las reglas están a la vista, así que el algoritmo puede razonar a partir de ellas, no solo probar.

Continúa las partes Búsqueda en el espacio de estados y Grafos y árboles.

1. Qué es un problema de satisfacción de restricciones

Definición — CSP

Un problema de satisfacción de restricciones (constraint satisfaction problem, CSP) es una terna (X, D, C), donde

• X = {X₁, …, X_n} es el conjunto de variables,
• D = {D₁, …, D_n}, donde D_i es el dominio: el conjunto de valores que puede tomar X_i,
• C es el conjunto de restricciones. Cada restricción es un par (ámbito, relación): el ámbito es una lista de variables y la relación indica qué combinaciones de sus valores están permitidas.

Una restricción con dos variables en su ámbito es binaria, por ejemplo X₁ ≠ X₂.

Definición — asignación y solución

Una asignación da a algunas variables un valor de su dominio. Es consistente si no viola ninguna restricción y completa si todas las variables tienen valor.

Una solución de un CSP es una asignación completa y consistente.

¿Por qué no plantearlo como una búsqueda corriente? Se podría: el estado es la asignación a medio hacer y la acción es «da un valor a la siguiente variable». Pero la búsqueda vería el estado como una caja negra. Un CSP ve dentro de la caja: sabe qué reglas rigen y a qué variables afectan. En eso se apoyan todos los trucos de esta parte.

2. El grafo de restricciones: colorear un mapa de regiones

Un problema clásico: colorear un mapa de modo que dos estados vecinos nunca tengan el mismo color. Tomemos las catorce regiones de Chequia. Las variables son las regiones, el dominio es un juego de colores y por cada frontera común hay una restricción «colores distintos».

Definición — grafo de restricciones

El grafo de restricciones de un CSP binario tiene como vértices las variables y una arista entre X_i y X_j si y solo si alguna restricción las une.

Con cuatro colores sale sin problemas. Con tres no sale de ninguna manera, y el grafo muestra por qué. La región de Bohemia Central es vecina de Praga y de siete regiones que forman a su alrededor un anillo cerrado. Un anillo con un número impar de vértices necesita por sí solo tres colores (dos tendrían que alternarse con regularidad, y con un número impar eso no cuadra). La región de Bohemia Central es vecina de las siete, así que para ella tiene que quedar un cuarto color:

Que cuatro colores bastan para cualquier mapa es el famoso teorema de los cuatro colores. Lo demostraron Appel y Haken en 1976, como el primer gran teorema matemático demostrado con ayuda de un ordenador, que comprobó casi dos mil casos.

3. Backtracking

Definición — backtracking

El backtracking es una búsqueda en profundidad que en cada paso asigna un valor a una variable más. Un valor que viola una restricción con las variables ya asignadas ni siquiera lo prueba. Cuando a una variable no le queda ningún valor, vuelve a la variable anterior y prueba su siguiente valor.

En el peor caso recorre O(dⁿ) asignaciones, donde d es el tamaño del dominio y n el número de variables. El CSP general es NP-difícil, así que en el peor caso no sabemos hacerlo mejor.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # todo tiene valor: solución
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # callejón sin salida: vuelve atrás
    return None

En las regiones con cuatro colores, el backtracking hace 14 asignaciones, una por región, y no vuelve atrás ni una vez. Con tres colores tiene que demostrar que no existe solución, y eso significa probarlo todo: 93 asignaciones antes de rendirse.

4. Qué variable y qué valor

El esqueleto del backtracking deja abiertas dos preguntas: qué variable tomar a continuación y en qué orden probar sus valores. Las respuestas importan más de lo que parece.

Definición — MRV, grado, LCV

MRV (minimum remaining values): elige la variable con el menor número de valores que todavía no están en conflicto con la asignación.

Heurística del grado: en caso de empate, elige la variable que tiene más restricciones con variables aún sin asignar.

LCV (least constraining value): prueba los valores de la variable empezando por el que elimina menos opciones a sus vecinas.

Con tres colores en las regiones, MRV junto con la comprobación hacia delante del siguiente apartado reduce el número de asignaciones de 93 a 45: empieza por la región a la que le quedan menos colores y encuentra la contradicción el doble de rápido.

5. Comprobación hacia delante

Definición — comprobación hacia delante

Tras la asignación X_i = v, recorre cada variable sin asignar X_j unida a X_i por una restricción y elimina de D_j los valores incompatibles con v. Si algún dominio se queda vacío, deshaz la asignación de inmediato.

La diferencia se ve en el sudoku de más abajo. El backtracking simple, con las casillas por filas, necesita más de 14 millones de asignaciones. Con la comprobación hacia delante son 11 400. Y si le añadimos MRV, baja a 81: 30 números dados y 51 rellenados, sin una sola vuelta atrás.

6. Consistencia de arcos y AC-3

La comprobación hacia delante solo mira un paso más allá: a las vecinas de la variable que acabamos de asignar. Se puede ser más minucioso: eliminar valores también entre variables que todavía no tienen valor.

Definición — consistencia de arcos

Una variable X_i es arco-consistente con respecto a X_j si para cada valor x ∈ D_i existe un y ∈ D_j tal que el par (x, y) cumple la restricción entre ellas. Un CSP es arco-consistente si esto se cumple para cada arista orientada (X_i, X_j) del grafo de restricciones.

Algoritmo — AC-3

1. Mete en la cola todas las aristas orientadas (X_i, X_j).
2. Saca una arista de la cola y elimina de D_i cada valor que no tenga pareja en D_j.
3. Si D_i se ha reducido, devuelve a la cola todas las aristas (X_k, X_i) de las vecinas X_k ≠ X_j: sus valores podrían haberse quedado sin pareja. Si D_i está vacío, el CSP no tiene solución.
4. Repite hasta que la cola esté vacía.

Para c restricciones binarias y dominios de tamaño como mucho d, AC-3 tarda O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # dominio vacío: no existe solución
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Sudoku: la propagación en la práctica

El sudoku es un CSP de manual: 81 variables, dominios {1, …, 9} y la restricción «valores distintos» para cada par de casillas de la misma fila, columna o cuadro de 3 × 3. Así, cada casilla tiene 20 vecinas en el grafo de restricciones.

Lancemos solo AC-3 sobre un enunciado con 30 números, sin una sola asignación a ciegas. Elimina 408 valores, y a cada una de las 51 casillas vacías le queda exactamente uno. El sudoku queda resuelto con puro razonamiento:

Con los sudokus fáciles suele pasar así; con los más difíciles, la propagación se atasca en algún punto y entra en juego la búsqueda: un backtracking que, tras cada asignación, vuelve a lanzar la propagación. Esta combinación (mantenimiento de la consistencia de arcos, MAC) es la base de la mayoría de los resolvedores reales. Como comparación, sobre el mismo enunciado:

De catorce millones a cero. La fuerza bruta y el razonamiento inteligente resuelven el mismo problema; solo uno de ellos lee las reglas.

8. Búsqueda local: min-conflicts

Una estrategia completamente distinta: no construir la solución pieza a pieza, sino empezar con una asignación completa que viola un montón de restricciones e irla corrigiendo poco a poco. Es la búsqueda local de la parte sobre búsqueda, solo que la función objetivo es el número de restricciones violadas.

Algoritmo — min-conflicts

1. Empieza con una asignación completa aleatoria.
2. Mientras alguna restricción no se cumpla: elige al azar una variable en conflicto y dale el valor con el que viola menos restricciones (en caso de empate, al azar).

La prueba clásica es el problema de las n reinas: colocar n reinas de ajedrez en un tablero de n × n de modo que ninguna amenace a otra. La variable es la fila de la reina en cada columna. Con ocho reinas, nuestra ejecución empezó con seis pares que se amenazaban y terminó tras 8 pasos:

Fíjate en los pasos intermedios: el número de conflictos se mantiene en uno durante cuatro pasos; el algoritmo mueve reinas «de lado» por una meseta hasta encontrar la jugada que elimina el conflicto. Lo sorprendente es lo bien que escala: min-conflicts resuelve un millón de reinas en unos cincuenta pasos de media. Con el mismo método se planificaban las observaciones del telescopio espacial Hubble.

9. Las restricciones en la práctica

• Horarios y planificación. Los horarios escolares, los turnos, la asignación de aulas y los planes de producción se plantean como variables, dominios y restricciones. Resolvedores como Google OR-Tools combinan propagación, búsqueda y mejora local.
• Los resolvedores SAT resuelven CSP en los que cada variable es verdadero/falso. Verifican diseños de chips, buscan errores en el software, y los gestores de paquetes (por ejemplo, en Linux) los usan para combinar versiones de bibliotecas que funcionen juntas.
• Los compiladores asignan las variables del programa a los registros del procesador coloreando un grafo: dos variables que viven a la vez no pueden compartir registro, exactamente igual que dos regiones vecinas no pueden compartir color.
• Los configuradores de las tiendas en línea y de la fabricación vigilan que los componentes elegidos sean compatibles entre sí.
• Los agentes de IA y los modelos de lenguaje a menudo no destacan en los CSP: para un sudoku o un horario, un resolvedor es más fiable. Por eso un buen agente no resuelve el problema «de cabeza»: lo traduce a variables y restricciones y llama a una herramienta.

10. Resumen

• Un CSP es una terna (X, D, C): variables, dominios y restricciones. Una solución es una asignación completa que no viola ninguna restricción.
• El backtracking asigna las variables una tras otra y vuelve atrás desde los callejones sin salida; en el peor caso es exponencial.
• Las heurísticas MRV y LCV eligen la variable más difícil y el valor más complaciente; la comprobación hacia delante detecta un callejón sin salida un paso antes.
• AC-3 propaga las eliminaciones por el grafo de restricciones hasta que cada valor tiene pareja; resuelve un sudoku fácil sin ninguna búsqueda.
• Min-conflicts corrige una asignación completa y puede incluso con problemas enormes, como un millón de reinas.

¿Quieres probarlo tú mismo? Pide a un agente de IA que escriba un resolvedor de sudoku con backtracking y luego añádele la comprobación hacia delante, MRV y AC-3, y cuenta cuántas asignaciones te ahorras.

¿Lo ves de otra manera? Escribe a support@coden-app.com.