sudoku2.clj

; things are looking up; you might see the solution in your lifetime

(def digits (range 9))

(defn find-open-position [puzzle]
  (first 
    (remove nil? 
            (for [i digits j digits] 
              (cond (nil? (puzzle [i j])) [i j] 
                    :else nil)))))

(defn nums-in-row [puzzle position]
  (remove nil? (for [i digits] (puzzle [i (last position)]))))
            
(defn nums-in-col [puzzle position]
  (remove nil? (for [j digits] (puzzle [(first position) j]))))

(defn get-squ-digits [x] 
  (let [val (/ x 3)]
    (cond
      (>= val 2) [6 7 8]
      (>= val 1) [3 4 5]
      (> val 0)  [0 1 2])))

(defn nums-in-squ [puzzle position]
  (remove nil? (for [i (get-squ-digits (first position)) j (get-squ-digits (last position))] (puzzle [i j]))))

(defn used-numbers [puzzle position]
  (concat (nums-in-row puzzle position)
          (nums-in-col puzzle position)
          (nums-in-squ puzzle position)))

(defn open-positions [puzzle]
  (remove nil? (for [i digits j digits] (cond (nil? (puzzle [i j])) [i j] :else nil))))

(defn free-numbers [puzzle position]
  (remove (fn [num] (contains? (set (used-numbers puzzle position)) num)) digits))

(defn find-next-moves [puzzle]
  (for [position (open-positions puzzle) number (free-numbers puzzle position)]
    {:position position :number number}))

(defn solved? [puzzle] 
    (= (count puzzle) 81))

(defn solve [puzzle]
  (reduce (fn [foo-puzzle next-move]
            (let [next-puzzle (assoc puzzle (next-move :position) (next-move :number))]
              (if (solved? foo-puzzle)
                (reduced foo-puzzle)
                (solve next-puzzle))))
          puzzle
          (find-next-moves puzzle)))
      
; test puzzle
(def puzzle {[0 4] 4
             [0 8] 3
             [1 1] 5
             [1 2] 3
             [1 3] 8
             [1 4] 2
             [2 2] 1
             [2 5] 6
             [2 6] 2
             [2 7] 8
             [3 0] 2
             [3 1] 6
             [3 6] 3
             [3 8] 1
             [4 0] 1
             [4 1] 8
             [4 3] 5
             [4 5] 2
             [4 7] 6
             [4 8] 9
             [5 0] 3
             [5 2] 5
             [5 7] 7
             [5 8] 2
             [6 1] 1
             [6 2] 9
             [6 3] 2
             [6 6] 7
             [7 4] 8
             [7 5] 1
             [7 6] 9
             [7 7] 4
             [8 0] 6
             [8 4] 9})