sudoku.clj

;; I think technically this works, but the algorithm is very slow and you won't 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] 
  (do (println (count puzzle))
    (= (count puzzle) 81)))

(defn get-solved-puzzle [puzzles]
  (loop [puzzles puzzles]
    (let [p puzzles first-p (first p) rest-p (rest p)]
      (cond (solved? first-p) first-p
            (empty? rest-p) nil
            :else (recur rest-p)))))  

(defn next-puzzle [puzzle]
  (map (fn [next-move] (assoc puzzle (next-move :position) (next-move :number))) (find-next-moves puzzle)))

(defn next-puzzles [puzzles]
  (flatten (map next-puzzle puzzles)))

(defn solve [puzzles]
  (loop [p puzzles]
    (let [solved-puzzle (get-solved-puzzle p)]
      (if (not (nil? solved-puzzle))
        solved-puzzle
        (recur (next-puzzles p))))))
      
; 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})

(solve [puzzle])