Cuando hablamos de paradigmas de programación todos tenemos claro de lo que estamos hablando: programación orientada a objetos, o sea, Java y C#, o programación funcional, o sea, F# y compañía. Lo cierto es que existen otros muchos paradigmas de programación basados en distintos modelos, como por ejemplo la programación lógica de la que hablé hace tiempo.

En este post vamos a ver otro paradigma de programación, emparentado en cierto modo con la programación lógica: la programación basada en restricciones o constraint programming.

Constraint Programming

OJO: No soy un experto (ni mucho menos) en constraint programming ni en teoría de lenguajes de programación en general, así que es muy probable que en este post haya inexactitudes y seguramente los términos que utilice no sean los más ortodoxos. Mi objetivo, aparte de aclarar mis ideas, es darte a conocer este tipo de programación y, si te interesa, siempre puedes ampliar la información, empezando por el artículo de la wikipedia sobre programación basada en restricciones.

La programación basada en restricciones es un paradigma de programación declarativo, es decir, en lugar de indicar cómo queremos que se hagan las cosas, nos limitamos a decir qué queremos que pase y el sistema/librería/lenguaje se encargará de hacerlo.

La programación basada en restricciones se basa en crear un modelo formado por variables, para las cuales deberemos indicar qué posibles valores pueden tomar, y restricciones, que expresan relaciones que deben cumplirse entre esas variables. Una vez creado el modelo, el sistema se encarga de encontrar aquellas soluciones que se ajustan a las restricciones.

Un ejemplo sencillo sería el modelo formado por las siguientes restricciones:

1) x es un valor entre 1 y 10
2) y es un valor entre 1 y 10
3) x < y
4) x + y = 4

Partiendo de estas restricciones, el sistema sería capaz de encontrar todas las posibles soluciones al problema (en este caso, sólo hay una):

x = 1
y = 3

Aunque a priori pueda parecer que esto sólo sirve para problemas "numéricos", con un poco de imaginación (tampoco demasiada) se puede aplicar a otro tipo de problemas.

Seguro que muchos conocéis el problema de 8 reinas, que consiste en colocar sobre un tablero de ajedrez 8 reinas sin que ninguna amenace a las demás. Modelar ese problema a base de restricciones es posible:

1) (xi, yi) es la posición de la reina i-ésima.
2) xi es un valor entre 0 y 7
3) yi es un valor entre 0 y 7
4) Todos los xi son distintos (i.e. no hay dos reinas en la misma fila)
5) Todos los yi son distintos (i.e. no hay dos reinas en la misma columna)
6) Todos los xi - yi son distintos (i.e. no hay dos reinas en la misma diagonal de arriba-izquierda a abajo-derecha)
7) Todos los xi + yi son distintos (i.e. no hay dos reinas en la misma diagonal de arriba-derecha a abajo-izquierda)

A partir de este modelo, una librería de programación basada en restricciones sería capaz de encontrar todas las soluciones posibles al problema. Pese a lo sencillo del ejemplo, viendo cómo se define "que dos reinas no estén la misma diagonal", ya nos vamos haciendo a la idea de que a veces traducir nuestro problema a restricciones puede ser un poco complicado.

La clave de todo esto está en el algoritmo que se usa para encontrar las soluciones y para ello existen varias alternativas con distinto grado de complejidad y optimización. Si le queréis echar un vistazo a algunas (muy bien explicadas), podéis revisar este precioso sitio sobre Constraint Programming.

loco, constraints programming en Clojure

Por último, vamos a ver cómo podemos utilizar este sistema en todo tipo de lenguajes a través de librerías externas. Para el ejemplo, usaré clojure, mi lenguaje por defecto para cosas divertidas y loco, una librería muy agradable de utilizar basada en Choco (los nombres no los he puesto yo).

En loco un modelo se define como una secuencia de restricciones, y para crear cada restricción podemos usar las funciones incluidas en la librería:

(def model
  [($in :x 1 10)
   ($in :y 1 10)
   ($ < :x :y)
   ($= ($+ :x :y ) 4)])

Con $in podemos declarar las variables y sus rangos de valores, y con los $operator podemos establecer relaciones entre ellas. El modelo se corresponde con el primero ejemplo de restricciones que veíamos en el post y, a poco que estés un poco familiarizado con la sintaxis de clojure, resulta extremadamente legible.

Para obtener las soluciones podemos utilizar solution que nos devuelve una solución, o solutions, que nos da la lista de todas las soluciones posibles:

(solution model)
;; => {:x 1 :y 3}

Una ventaja de loco es que, al igual que muchas librerías de Clojure (por ejemplo las de Datomic), se basa en construir estructuras de datos "estándar" y luego procesarlas con una función. El modelo no es más que una secuencia que podemos construir como queramos, lo que nos permite aprovechar la típicas funciones para manejar este tipo de estructuras de datos.

Por ejemplo, si queremos modelar el problemas de las 8 reinas, podríamos tener:

(def queens-model
  ;; Variables [:x i] [:y i] para la posición de la reina i-ésima
  (let [vars (mapcat #(vector ( $in [:x %] 0 7) ($in [:y %] 0 7)) (range 8))]
    (conj vars
          ;; Todas las filas deben ser distintas
          ($distinct (map (partial vector :x) (range 8)))
          ;; Todas las columnas deben ser distintas
          ($distinct (map (partial vector :y) (range 8)))
          ;; Todas las diagonales deben ser distintas
          ($distinct (map #($- [:x %] [:y %]) (range 8)))
          ;; Toas las contra-diagonales deben ser distintas
          ($distinct (map #($+ [:x %] [:y %]) (range 8))))))

Nuevamente es una traducción casi directa del enunciado de las restricciones. Primero definimos las variables x_i e y_i, que representamos como vectores [:x i] e [:y i] y luego añadimos el resto de restricciones, como que todos los [:x 0] ... [:x 7] deben ser distintos.

Si queréis jugar un rato, tenéis el código en este gist junto con una función para mostrar la solución de una forma un poco más legible.