Problemas de satisfacción de restricciones es un tipo especial de problemas que satisfacen algunas propiedades adicionales.
Las restricciones pueden involucrar una o varias variables al mismo tiempo.
A veces en estos problemas conviene hacer una verificación hacia adelante (forward checking) para detectar estados sin solución (e.g., las 8-reinas).
Muchas veces lo que conviene es analizar la variable más restringida, ésto es, asignarle un valor a la variable que está involucrada en la mayor cantidad de restricciones.
Otra heurística común es seleccionar un valor que elimine el menor número de valores en las otras variables asociadas a la variable por medio de una restricción.
A veces la descripción del estado contiene toda la información necesaria para llegar a una solución (e.g., las 8-reinas) y se utilizan algoritmos que hacen mejoras iterativas.
La idea general es empezar con una configuración completa y hacer modificaciones para mejorar su calidad.
Normalmente, en problemas de maximización se trata de moverse hacia el pico más alto. Los métodos iterativos normalmente guardan sólo su estado actual y no ven mas allá de sus vecinos inmediatos.
Aquí podemos mencionar a gradiente descendiente (hill-climbing) y a recocido simulado (pero esos los veremos más adelante).