ClojureJuly 27, 2011
After ages and ages, I finally got into a new language. On the pretext of preparing for a brown bag session with the team, I started reading about Clojure and all of its benefits. The brown bag went off decently enough – I re-used Rich Hickey’s slides and talked about functional programming, Java inter-op and mainly the concurrency mechanisms. While preparing, I copy-pasted several bits of code, ran them etc and started getting a feel for the language. But the penny really dropped at the very end of the session when I was asked to write a simple hello world…and couldn’t! I later found (def hello (fn  “Hello world”)) on the clojure website and promptly sent it off to the guys
Since I wasn’t totally put off by the language and even somewhat impressed by it, I decided I needed to do some hands-on development to learn the intricacies of the language. To begin with, I stayed away from all the concurrency constructs and picked a problem to try and tackle the functional elements – a sudoku problem solver. Its most likely not the most efficient algorithm though I might try to parallelize it.
- My “grid” is actually just a vector of 81 elements.
- Rows, columns and sub-grids are views of the appropriate indices on the vector.
- setup-grid sets up the problem.
- solve uses brute-force in a depth-first manner to solve the puzzle.
3 - 8 2 9 1 - - - 1 7 9 - - - 2 6 - - - - - - 6 1 - - 8 - 5 1 - - 6 - - - - - 6 3 9 - - - - - 6 - - 8 3 - 2 - - 1 5 - - - - - - 5 4 - - - 8 1 7 - - - 8 1 7 4 - 6
- - 2 - - - - - 6 5 4 - 9 - - 2 - - - - - 8 2 - - - - - 5 - - - - 7 - - - - 4 7 1 6 5 - - - - 1 - - - - 8 - - - - - 9 2 - - - - - 9 - - 7 - 4 8 4 - - - - - 1 - -
(def size 9) (def sqrt (Math/sqrt size)) (def values (loop [c 1 v (set )] (if (> c size) v (recur (inc c) (conj v (str c)))))) (defn index [x y] (+ (* x size) y)) (defn place [grid x y] (-> grid (nth (index x y)))) (defn assign [grid x y val] (assoc grid (index x y) (str val))) (defn setup-base-grid  (vec (take (* size size) (cycle [nil])))) (defn setup-grid [init-setup] (loop [grid (setup-base-grid) ks (keys init-setup) vs (vals init-setup)] (if (and ks vs) (recur (assign grid ((first ks) 0) ((first ks) 1) (first vs)) (next ks) (next vs)) grid))) (defn row [grid x] (let [start (* x size) end (+ start size)] (subvec grid start end))) (defn col [grid y] (loop [c 0 v ] (if (>= c size) v (recur (inc c) (conj v (place grid c y)))))) (defn sub-grid [grid x y] (let [startx (* x sqrt) endx (+ startx sqrt) starty (* y sqrt) endy (+ starty sqrt)] (loop [c startx v ] (if (>= c endx) (vec v) (recur (inc c) (concat v (subvec (row grid c) starty endy))))))) (defn pretty-print [grid] (loop [c 0 out ""] (if (>= c size) (println (.replace (.replace (.replace out "nil" "-") "[" "") "]" "")) (recur (inc c) (str out (println-str (row grid c))))))) (defn missing [section] (clojure.set/difference values (set section))) (defn solve ([grid] (solve grid 0)) ([grid counter] (if (>= counter (* size size)) grid (if (grid counter) (solve grid (inc counter)) (let [row-number (quot counter size) col-number (rem counter size) sub-grid-number [(quot row-number sqrt) (quot col-number sqrt)]] (loop [possibles (seq (missing (clojure.set/union (row grid row-number) (col grid col-number) (sub-grid grid (sub-grid-number 0) (sub-grid-number 1)))))] (if (nil? (first possibles)) nil (let [possible-grid (solve (assign grid row-number col-number (first possibles)) (inc counter))] (if (nil? possible-grid) (recur (next possibles)) possible-grid)))))))))