sudoku.clj

;; sudoku.clj
;; Mac Mason <mac@cs.duke.edu>
;;
;; Writing sudoku in LISP!
;;
;;
(set! *warn-on-reflection* true)

(use 'clojure.set)

(defn parse-board
  "Given a filename, parse it into a properly-formatted vector."
  [^String filename] 
  (let [string (slurp filename)  ; Grab the entire file.
        lines (clojure.string/split string #"\n")]  ; Split it at linebreaks.
    (mapv #(clojure.string/split % #"\s+") lines))) ; And again at spaces.

(defn board-to-string
  "Given a vector of vectors (one of our boards), generate the appropriate 
  String for printing it out."
  [board]
  (letfn [(row-to-string [row] 
            (apply str (interleave row (cycle " "))))]
    (if (nil? board) "Nil!"
      (apply str (interleave (map row-to-string board) (cycle "\n"))))))

(defn get2
  "Two-dimensional substripting on a vector."
  [v [r c]] 
  ((v r) c))

(defn set2
  "Two dimensional \"set\" on a vector."
  [v [r c] a] 
  (assoc v r (assoc (v r) c a)))

(defn find-empties
  "Given a board, generate a sequence of [row, col] pairs for the empty cells."
  [board]
  (let [idxs (range (count board))]
    (for [i idxs j idxs :when (= "0" (get2 board [i j]))] [i j])))

(def valid-values
  "All potential values for a cell. Note that we're in Strings, not ints."
  (set (map str (range 1 10))))

(defn find-legals
  "Given a board and a location on the board, compute every legal move for
  that location"
  [board [r c]]
  (let [rowset (set (board r))
        colset (set (map #(get % c) board))
        boxrow (* 3 (quot r 3)) ; These get the upper-left corner of the box.
        boxcol (* 3 (quot c 3))
        boxidxs (for [x (range 3) y (range 3)] [(+ x boxrow) (+ y boxcol)])
        boxset (set (for [p boxidxs] (get2 board p)))]
    (clojure.set/difference valid-values rowset colset boxset)))

(defn solve
  "Return a solution to a Sudoku board, or nil, should one not exist."
  ([board] (solve board (find-empties board)))
  ([board empties]
   (if (empty? empties) board  ; Base case!
     (let [loc (first empties)
           legals (find-legals board loc)
           calls (for [l legals] (solve (set2 board loc l) (rest empties)))
           wins (filter #(not (nil? %)) calls)]
       (if (empty? wins) nil (first wins))))))

(doseq [x *command-line-args*] 
  (-> x parse-board solve board-to-string println))