Monday, 9 June 2014

Queens

I finally got around to reading SICP, which is absolutely brilliant.
I love the way programming is treated as an extension of cognitive concepts that lie at the very core of our being. Here is a quote from the first chapter:

The acts of the mind, wherein it exerts its power over simple ideas, are chiefly these three:
  1. Combining several simple ideas into one compound one, and thus all complex ideas are made. 
  2. The second is bringing two ideas, whether simple or complex, together, and setting them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations.
  3. The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made.
- John Locke, An Essay Concerning Human Understanding (1690)

The book then goes on to describe the 3 important features of a programming language as follows:
  1. Primitive expressions, which represent the simplest entities the language is concerned with
  2. Means of combination, by which compound elements are built from simpler ones
  3. Means of abstraction, by which compound elements can be named and manipulated as units

Needless to say, I'm having a blast.

The book then explains these concepts with the help of various exercises, one of which is the N-Queens Problem. Here is a solution in Clojure that produces all possible configurations:

(ns queens)

(defn attacking? [[r1 c1] [r2 c2]]
  (or (= r1 r2)
      (= c1 c2)
      (= (+ r1 c1) (+ r2 c2))
      (= (- r1 c1) (- r2 c2))))

(defn safe? [board pos]
  (not (some #(attacking? % pos) board)))

(defn safe-poses [board n c]
  (for [r (range n)
        :let [pos [r c]]
        :when (safe? board pos)]
    pos))

(defn poss-boards [board n c]
  (for [pos (safe-poses board n c)]
    (conj board pos)))

(defn solutions [n]
  (loop [c 0, boards [[]]]
    (if (>= c n) boards
      (recur (inc c) (mapcat #(poss-boards % n c) boards)))))

Concise and expressive.
In fact, I was pretty surprised when i realized I was done, as my last attempt (in Java, around 3 years back) had been pretty complicated and unwieldy, and produced only one of the possible configurations.

Anyways, did I mention I'm having a blast?
Because I really am.

No comments:

Post a Comment