# Constraint Satisfaction Problems and Functional Backtracking Search

Recently I have reviewed my notes on the online course BerkeleyX: CS188.1x, which I took years ago (I can highly recommend the course, it is of outstanding didactic quality). As I reviewed the topic Constraint Satisfaction Problems, I was wondering how the imperative pseudo code for backtracking search formulated in the script could be translated into a functional programming language.

### Translating the pseudo code to real code

For this I translated the pseudo code in Python first. This seemed to me to require the least amount of effort and in fact the result is very similar to the pseudo code from the script:

`counter = 0`
`DOMAINS = "DOMAINS"`
`VARIABLES = "VARIABLES"`
`CONSTRAINTS = "CONSTRAINTS"`
`FAILURE = "FAILURE"`
`def is_complete(assignment):`
`  return None not in (assignment.values())`
`def select_unassigned_variable(variables, assignment):`
`  for var in variables:`
`    if assignment[var] is None:`
`      return var`
`def is_consistent(assignment, constraints):`
`  global counter`
`  counter += 1`
`  for constraint_violated in constraints:`
`    if constraint_violated(assignment):`
`      return False`
`  return True`
`def init_assignment(csp):`
`  assignment = {}`
`  for var in csp[VARIABLES]:`
`    assignment[var] = None`
`  return assignment`
`def recursive_backtracking(assignment, csp):`
`  if is_complete(assignment):`
`    return assignment`
`  var = select_unassigned_variable(csp[VARIABLES], assignment)`
`  for value in csp[DOMAINS]:`
`    assignment[var] = value`
`    if is_consistent(assignment, csp[CONSTRAINTS]):`
`      result = recursive_backtracking(assignment, csp)`
`      if result != FAILURE:`
`        return result`
`    assignment[var] = None`
`  return FAILURE`
0.2s
Python

### Testing the code translation

To test the code, we solve the problem of coloring the map of Australia. The constraints in this problem are simply that no two adjacent states can be the same color:

`counter = 0`
`def eq(a, b): return a is not None and b is not None and a == b`
`def wa_nt(asmt): return eq(asmt["WA"], asmt["NT"])`
`def wa_sa(asmt): return eq(asmt["WA"], asmt["SA"])`
`def nt_sa(asmt): return eq(asmt["NT"], asmt["SA"])`
`def nt_q(asmt): return eq(asmt["NT"], asmt["Q"])`
`def sa_q(asmt): return eq(asmt["SA"], asmt["Q"])`
`def sa_nsw(asmt): return eq(asmt["SA"], asmt["NSW"])`
`def sa_v(asmt): return eq(asmt["SA"], asmt["V"])`
`def q_nsw(asmt): return eq(asmt["Q"], asmt["NSW"])`
`def v_t(asmt): return eq(asmt["V"], asmt["T"])`
`my_csp = {VARIABLES: ["WA", "NT", "Q", "NSW", "V", "SA", "T"],`
`          DOMAINS: ["red", "green", "blue"],`
`          CONSTRAINTS: [wa_nt, wa_sa, nt_sa, nt_q, sa_q, sa_nsw, sa_v, q_nsw, v_t]}`
`result = recursive_backtracking(init_assignment(my_csp), my_csp)`
`[counter, result]`
0.2s
Python
[12, {'NSW': 'green', 'NT': 'green', 'Q': 'red', 'SA': 'blue', 'T': 'green', 'V': 'red', 'WA': 'red'}]

After checking all constraints 12 times, we find a valid coloring.

### A functional solution

Since the python code makes heavy use of jumping out of a method via the `return` clause, a direct translation in functional code is difficult. Furthermore, the recursive call to `recursive_backtracking` is not at a tail-recursive position, which is ok for pseudo code, but - depending on the size of the CSP - might be a problem for production code. In functional languages however, it is recommended to prefer Higher Order Functions over recursion, anyway.

For the functional solution, the general idea is to generate a lazy sequence of CSPs, which contain the (partial) assignment from colors to states. Every next CSP is either one step closer to the complete assignment, or - if a constraint was violated - the next branch of the backtracked assignment. We check each element of that sequence and stop as soon as an element is complete.

My functional language of choice is Clojure. In my opinion, the signal-to-noise ratio is very high in Clojure, so the algorithm gets very clear.

`(def counter (atom 0))`
`(defn init [domains variables constraints]`
`  {:domains domains`
`   :variables variables`
`   :any-constraints-violated? (apply some-fn constraints)`
`   :assignment (zipmap variables (repeat nil))})`
`(defn complete? [csp]`
`  (every? some? (vals (:assignment csp))))`
`(defn consistent? [{:keys [any-constraints-violated?]`
`                    :as csp}]`
`  (swap! counter inc)`
`  (not (any-constraints-violated? csp)))`
`(defn select-unassigned-variable [csp]`
`  (first (filter (comp nil?`
`                       (partial get-in csp)`
`                       (partial conj [:assignment]))`
`                 (:variables csp))))`
`(defn next-csps [csp]`
`  (map (fn [d]`
`         (assoc-in csp`
`                   [:assignment (select-unassigned-variable csp)]`
`                   d))`
`       (:domains csp)))`
`(defn backtracking-seq [csps]`
`  (lazy-seq (if-let [[\$first & \$rest] (seq csps)]`
`              (if (consistent? \$first)`
`                (cons \$first`
`                      (backtracking-seq (concat (next-csps \$first)`
`                                                \$rest)))`
`                (backtracking-seq \$rest)))))`
`(defn backtracking [csp]`
`  (if-let [result (first (filter complete?`
`                                 (backtracking-seq (next-csps csp))))]`
`    result`
`    :failure))`
0.3s
Clojure
user/backtracking

### Testing the functional solution

`(defn constraint [state-a state-b]`
`  (fn [csp]`
`    (if-let [a (get-in csp [:assignment state-a])]`
`      (= a (get-in csp [:assignment state-b]))`
`      false)))`
`(reset! counter 0)`
`(let [csp (init #{:red :green :blue}`
`                [:WA :NT :Q :NSW :V :SA :T]`
`                #{(constraint :WA :NT)`
`                  (constraint :WA :SA)`
`                  (constraint :NT :SA)`
`                  (constraint :NT :Q)`
`                  (constraint :SA :Q)`
`                  (constraint :SA :NSW)`
`                  (constraint :SA :V)`
`                  (constraint :Q :NSW)`
`                  (constraint :V :T)})`
`      result (backtracking csp)]`
`  [@counter result])`
0.2s
Clojure
Vector(2) [12, Map]

Again, we find a complete assignment after checking all constraints 12 times.