Sunday, September 11, 2011

Eight Queens in Clojure Land


Hello again. When time flies and you find yourself with your hands full of books and article to read, finding and writing about some subject can become very hard. In such times I try to look in my bag of things I-always-wanted-to-do-but-never-took-time-to-do (you can breath) . I had a little bit more than two hours to kill yesterday before digging again in Clojure in Action and the new chapter edited by Joshua Suereth in Scala in Depth.
There remain few basic algorithmic problems I want to tackle before switching to distributed algorithms. One of them is the famous eight queen problem. Fortunately Martin Odersky presented a Scala version in his book, in order to expose a nice use of the comprehensions in Scala. So, unfortunately for me Scala was not an option to implement a solution.

I wanted it recursive and having committed myself into the study of Clojure for a few months now, the language was an option. Although I am not at the level of expert Lisp and Clojure developers I took the liberty to try my very first personal implementation.
The result is not the result I expected, but as usual any critic will be welcomed: although being french I do like learning from critics as from failures and retries (really need to embrace a new nationality). In conclusion a very brief and relaxing exercise today.

  As a reminder you can get details about the the eight queen puzzle there. Basically our purpose is to dispatch eight queens on a chessboard so that, none of them can attack the others. Applying the basic rules of chess game, two queens cannot be located on the same rows, nor columns nor diagonals. Numerous readers must have stopped there finding that too basic.
For the others let's continue. Indulge me and consider that it would more elegant to provide a solution dealing with the dispatch of n queens on a n sized chessboard (the others should not have left). In order to solve the problem I adopted the same attitude as when solving the Hanoi Tower problem.
Let us consider the problem partially solved - one say - on a four sized chessboard. At step 3, my only partial solutions can be expressed as list of list of ...list:

(   ((3 3) (2 1) (1 4) ()) 
    ((3 4) (2 1) (1 3) ()) 
    ((3 1) (2 4) (1 2) ())
    ((3 2) (2 4) (1 1) ()))

A tuple represents a queen position.
The adopted rules being to index the upper left corner as (1 1) and the lower right as (4 4), the car of the list being the row number and the cdr being the column number.
A list of positions is a partial solution to be completed
And the list of list of list (:)) is the list of solutions.
 No big deal there.

 The solutions are to be read from left to right, the first element being the most recent position found. The annoying empty list at the beginning of the solution is due to my choice of starting from no solution. All I have to do is considering all the possible positions on the fourth row and choose the matching ones that would lead to acceptable solution. The scenario is applicable whatever is the step index value in a n sized chessboard. In the four cell chessboard the two solutions are:

One should notice that the solutions are symmetric and there might be interesting exercises to implement in order to reduce the number of solution to the reduced forms by symmetry considerations.

Considering the eight queen problem we are to find 92 solutions.

 I usually do TDD. And I will present you the unitary tests. But I have to confess that I did not start like that. You generally start implementing some algorithm in pseudo code before writing anything, but the conciseness of Lisp languages (they are homoiconic languages) makes them natural candidates to write the algorithm as-is.

I wrote what came in mind and backwardly tested my methods one after the other adjusting the first shot. Worked nice for me: I worked both with IntelliJ and Leinengen, with the following project.clj configuration:
(defproject states "1.0"
  :description "N-Queens"
  :dependencies [[org.clojure/clojure "1.3.0-beta2"]
  			     [org.clojure/clojure-contrib "1.2.0"]])
although the clojure-contrib is not needed. Just in case ;) .

 The entry point of my algorithm is where I set my intention to match the different positions for a queen at step k , within a n dimension chessboard. Using Abelson and Sussman wishful programming approach lead me to:
(ns algorithms.n-queens)

;.......

(defn place-queens [at-step within-boundaries]
    (if (= 0 at-step)
      (list (list (list)))
      (let [solutions (place-queens (dec at-step) within-boundaries)
             for-positions (possible-positions at-step within-boundaries)]
        (mapcat (possible-solutions for-positions) solutions))))

This is where the little annoying empty list comes from.
As Martin Odersky, I define my no-solution expression as an empty list. In Clojure the empty list is not a bottom form marking the end of a list like Nil. I learned that during the exercise :), but too late.

At the very top we find the working namespace definition (algorithms.n-queens), so my file is located under some algorithms directory and the code implemented in a n-queens.clj file.
Starting, literally at step 0, I do return a (list(list(list))), otherwise I define my set of solutions as the solutions recursively found for a decremented number of steps and the range of positions to be tested.
I then return a list of the possible new solutions as a result from comparing all possible positions versus already found solutions.
 The easier function to be tested is possible-positions in charge to extract all the possible positions in the row at-step. Driven by test we start with something like:

(ns test.algorithms.n-queens-specs
  (:use algorithms.n-queens)
  (:use clojure.test))

(deftest possible-positions-at-defined-step-should-be-generated
    (is (= (list '(1 1) '(1 2)) (possible-positions 1 2))))
Provided at the top is the namespace definition including the clojure.test namespace. At step 1, in a two dimensional chessboard I expect ((1 1) (1 2)) as possible positions. The matching implementation is:
(defn possible-positions [at-row boundary]
  (map #(list at-row %)(range 1 (inc boundary))))

We use a map higher order function in order to apply a #(list at-row %) lambda function taking as parameter all the range from 1 to the boundary limit (upper limit is exclusive so we have to increment the boundary value)
 In the placed-queens method the (possible-solutions for-positions) is surrounded by parenthesis because I decided to use a closure. I found more natural to close onto the set of possible positions, and then find a match for each possible solution. That 's the purpose of
(mapcat (possible-solutions for-positions) solutions)
mapcat allowing me to slice a list of list of solutions into recursive list of solution, and I must confess once more that I found it using TDD. No magic, just the good effect of testing. A typical test scenario for the possible-solutions implementation would be:
 
(deftest possible-solutions-with-positions-for-known-solution-should-complete-solution
  (let [for-positions (possible-positions 4 4)
          from-solution (list '(3 1) '(2 4) '(1,2))]
    (is (= (list (list '(4 3) '(3 1) '(2 4) '(1,2)))
          ((possible-solutions for-positions) from-solution)))))
where starting at row 4 with the already found partial solution ( (3 1) (2 4) (1 2)) we would find ((4 3) (3 1) (2 4) (1 2)) Of course keep warm the test. It won't pass, we do not have the function yet. My function definition can be :
(defn matching [in-solution]
  (fn [position]
      (every? (safe? position) in-solution)))

(defn safe [positions matching-solution]
  (filter #(matching-solution %) positions))

(defn possible-solutions [positions]
  (fn [solution]
    (reduce #(cons (cons %2  solution) %1) nil
      (safe positions (matching solution)))))

with the help of matching and the help of safe.
The expression   (matching solution) defines yet another closure which captures a solution and allows the challenge of a possible position versus all the positions of the captured solution.
This closure is reused in the safe function to filter the possible positions matching, in effect the partial solution. From these filtered positions combined to the en-closed solution we will build new solutions. Take your time, higher order functions and their use is not always simple.

 The function possible-solutions rebuild then a list of new solutions from nil, each new solution appending a filtered position to the en-closed solution. From each solution we can have multiple possible new solutions. We return a list of lists (solutions) of ...lists (positions). The bunch of tests used to qualify this approach are:
(deftest matching-solution-with-matching-position-should-return-true
  (let [solution (list '(3 1) '(2 4) '(1,2))]
    (is (true? ((matching solution) '(4 3))))))

(deftest matching-solution-with-un-matching-position-should-return-false
  (let [solution (list '(3 1) '(2 4) '(1,2))]
    (is (false? ((matching solution) '(4 2))))))

(deftest safe-positions-with-matching-solution-should-return-valid-positions
  (is (= (list '(4 3)) (safe (possible-positions 4 4) (matching (list '(3 1) '(2 4) '(1,2)))))))
trying effective different scenarii on four dimension chessboards...But you can't test'em till the safe? function invoked from matching is implemented.

 The safe function basically creates yet (yet) another closure, closing onto a new possible position. This closure will test all the existing positions in a solution in order to ensure that the enclosed position can be appended to form a new solution. I need tests to challenge the safe? function:
(deftest position-safe-for-not-safe-position-should-return-false
  (is (false? ((safe? '(1 1)) '(2 1))))
  (is (false? ((safe? '(1 1)) '(1 2))))
  (is (false? ((safe? '(1 1)) '(2 2)))))

(deftest position-safe-for-empty-position-should-return-true
  (is (true? ((safe? '(1 1)) '(3 2)))))

(deftest position-safe-for-safe-position-should-return-true
  (is (true? ((safe? '(1 1)) '()))))
You will notice I have also tested the empty starting solution. So, Our solution comes to be
(defn on-diagonal [position previous-position]
   (= (Math/abs (- (second position) (second previous-position)))
              (Math/abs (- (first position) (first previous-position)))))

(defn safe? [position]
  (fn [previous-position]
  (or
    (empty? previous-position)
    (and
      (not (= (first position) (first previous-position)))
      (not (= (second position) (second previous-position)))
      (not (on-diagonal position previous-position))))))
As a summary the whole program is:
(ns algorithms.n-queens)

(defn possible-positions [at-row boundary]
  (map #(list at-row %)(range 1 (inc boundary))))

(defn on-diagonal [position previous-position]
   (= (Math/abs (- (second position) (second previous-position)))
              (Math/abs (- (first position) (first previous-position)))))

(defn safe? [position]
  (fn [previous-position]
  (or
    (empty? previous-position)
    (and
      (not (= (first position) (first previous-position)))
      (not (= (second position) (second previous-position)))
      (not (on-diagonal position previous-position))))))

(defn matching [in-solution]
  (fn [position]
      (every? (safe? position) in-solution)))

(defn safe [positions matching-solution]
  (filter #(matching-solution %) positions))

(defn possible-solutions [positions]
  (fn [solution]
    (reduce #(cons (cons %2  solution) %1) nil
      (safe positions (matching solution)))))

(defn place-queens [at-step within-boundaries]
    (if (= 0 at-step)
      (list (list (list)))
      (let [solutions (place-queens (dec at-step) within-boundaries)
             for-positions (possible-positions at-step within-boundaries)]
        (mapcat (possible-solutions for-positions) solutions))))

(defn placed-queens[for-number]
  (time
    (place-queens for-number for-number)))
Here we are with our Eight Queens. Too many books to read, so be seeing you !!! :)

5 comments:

Geoff Knauth said...

This was a fun read to start off the day. Thank you.

Mike Meyer said...

The eight queens problem is also an interesting tool for exploring parallel processing in clojure: http://blog.mired.org/2011/03/easy-parallel-processing-in-clojure.html

Globulon said...

Really thank you for your two feedbacks. I really appreciate them :) and will check the link for sure.

Tim Olsen said...

Eight queens is also an exercise given in the text Structure and Interpretation of Computer Programs (which uses Scheme). Try googling "eight queens SICP" for some sample solutions to compare yours too (also good for comparing Clojure to Scheme!).

Globulon said...

Thanks. I will do it. I did the exercise before reading an explained solution in the book :) The whole story is that I watched the presentation of the problem by Harold Abelson and was frustrated not to have solved the problem before. Inspired by his description I wrote this solution :)

Post a Comment