Posts Tagged ‘sudoku’

h1

Parallel Sudoku

August 15, 2011

Following on from my previous post where I wrote a Sudoku solver in Clojure, I tried to improve the performance of the algorithm by having each branch of my search tree execute in a separate thread. I first tried using the ref construct and while it solved the easy puzzle, there was a non-trivial bug which went into some infinite loop with the hard one. I finally gave up on it and decided to use the agent construct to notify the main thread when the puzzle was solved. The main thread just hangs around waiting for the agent state to change to the right solution.

While performance between the two solutions is interchangeable on the easy puzzle, there is a noticeable difference in the performance on the hard one – the parallel solution is consistently 3.5-4 times slower! I have tried changing around some of the parameters (increasing thread pool size to 1000, decreasing it to 4 – the number of cores on my laptop, increasing the sleep interval on the main thread to try and reduce the amount of processor time it grabs etc), all to no avail. I can’t believe context switching between threads costs so much more than the benefits of a parallel search.

So, why is this slower (and by this magnitude)? Alternatively, how could I profile this application (it takes approximately 4 seconds to run) to get some hints?

Here is the relevant additional code:

(def executors (java.util.concurrent.Executors/newFixedThreadPool 100))

(defn solve-in-parallel-worker [grid counter solution-agent]
  (if (>= counter (* size size)) 
    (send-off solution-agent conj grid)
    (if (grid counter) 
      (solve-in-parallel-worker grid (inc counter) solution-agent)
      (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))))) 
             dummy nil]
            (if (nil? (first possibles))
              nil 
              (recur 
                (next possibles) 
                (.submit executors 
                  (fn[] (solve-in-parallel-worker 
                          (assign grid row-number col-number (first possibles)) 
                          (inc counter) 
                          solution-agent))))))))))

(defn solve-in-parallel [grid]
  (let [solution-agent (agent [])]
    (.submit executors (fn[] (solve-in-parallel-worker grid 0 solution-agent)))
    (while (= @solution-agent []) 
      (Thread/sleep 1)) 
    (first @solution-agent)))
h1

Clojure

July 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.
Having written no automated tests (lots of manual testing via the REPL while writing the code only), I tested it out with two examples from websudoku. The first was the “easy level” and took 98.684439 msecs whereas the “evil level” took 1139.137917 msecs. Here are the two examples:
Easy
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
Evil
- - 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 - -
And if you are interested, the code: (and yes, I know there are a lot of brackets)
(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)))))))))