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
Python 3

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
Python 3
[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
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
Clojure
Vector(2) [12, Map]

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

Runtimes (2)