n-queens puzzle solved in hy and cps

In the previous blog posting, I showed a way to solve n-queens puzzle with Tiny Rule Engine. This blog post will look how to solve the same problem with Classical Problem Solver (or CPS for short). Both are modules in Hy library called Stilpo.

Goal of CPS module of Stilpo is to give tools for solving search problems. There are implementation for breadth first, depth first, best first and a* searches. Interface for breadth first and depth first searches is identical, as they only differ in which order they explore the problem space. Best first search requires extra function that can give distance between current state and goal state, while a* in addition requires information on how far it has already traveled. Because no such a function exists for n-queens problem, we’re limited to depth and breadth first searches.

Encoding I selected for the problem is a tuple, containing queen positions as tuples. For 4 queens, this would be a tuple containing 4 tuples, like below. Initial state would be empty tuple, meaning there are no queens on the board.

(, (, 0 1) (, 1 3) (, 2 0) (, 3 2))

Now that we have encoding, we need to state our goal:

(defn goal? [queens]
  "has the solution been found?"
  (and (= (len queens) n)
       (not (conflicts? queens))))

If there are n queens on the board and there are no conflicts, we have found a valid solution. But for that we need to know if a given board is valid. For this there’s two functions:

(defn conflicts? [queens]
  "can any of the queens take any other queen?"
  (any (map (fn [x] (can-take-any? x queens)) queens)))

(defn can-take-any? [queen queens]
  "can queen take any other queen?"
  (any (map (fn [x]
              (and (not (= x queen))
                   (or (= (first x) (first queen))
                       (= (second x) (second queen))
                       (= (abs (- (first x) (first queen)))
                          (abs (- (second x) (second queen)))))))
            queens)))

conflicts? checks each queen on the board and reports if there are any conflicts. It uses can-take-any? function, that does the actual work. Given a queen and a set of queens, it proceeds to check each of them and see if any of them happens to be on a same colum, row or diagonal.

Having stated initial state and goal, we need to tell our search how to proceed towards the goal. In CPS this is achieved by giving a list of operators. To define an operator that places a queen at given spot, we have following function:

(defn place-queen [location]
  "create place queen operator"
  {:action (fn [state]
             (if state
               (+ state (, location))
               (, location)))
   :desc (.format "place queen at {0}" location)})

Dictionary contains two keys. :action is a function, which when given a state will return a new state. :desc is plain text description that is useful when reporting at the end how a particular solution was achieved.

To create an actual list of operators that can be used for given state, we define operators function:

(defn operators [queens]
  "give list of valid operators for given state"
  (setv current (len queens))

  (->> (map (fn [x]
              (, current x))
            (range n))
       (filter (fn [x]
                 (not (can-take-any? x queens))))
       (map place-queen)))

When given a board containing some amount of queens, operators will first find first empty column and then create a list of actions of all valid queen placements on that column. If no valid placements are left, empty list is returned.

Last function to be defined is identical?. This is needed for loop detection. Without it search might end up going in circles and never terminate. Here we’re making an assumption that queens are in same order on both boards and just use = operator to check if boards are identical. Skipping the sorting makes search a bit faster at the risk that bug somewhere else puts queens out of order, causing loop detection to fail.

(defn identical? [queens-a queens-b]
  "are two states identical?"
  (= queens-a queens-b))

That’s actually all that is needed. Now we can construct our depth first searcher and call it with an initial state. In no time (depending on the n, it should produce a list of queen placements):

(setv solver (depth-first-solver :is-goal goal?
                                 :operators operators
                                 :is-identical identical?))
(solver (, ))

Because TRE in previous blog post uses depth first search, these two solvers will give the same answer. CPS is just quite a bit faster, because it needs to do far less operations for each assumption. This nicely highlights that it makes sense to think the problem, problem space and assumed solution to it, before commiting to specific set of algorithms and tools.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s