clojoku.clj

(ns clojoku
  (:use [clojure.contrib.seq-utils :only (indexed)])
  (:use [clojure.contrib.str-utils :only (str-join)])
  (:use [clojure.set :only (union)]))

(defstruct board :cells)

(defn interpose-n [n sep coll]
  "Returns a list with sep inserted after every n entries in coll"
  (mapcat (fn [[idx x]]
            (cond (= 0 (rem (inc idx) n)) [x sep]
                  :else [x]))
          (indexed coll)))

(defn take-n-from [n start coll]
  "Takes n elements from coll, starting at index start"
  (take n (nthrest coll start)))

(defn parse-board [s]
  (let [parse-char (fn [c] (if (= c \.) nil
                               (. Integer parseInt (str c))))]
    (struct-map board :cells (into [] (map parse-char s)))))

(defn cell-to-str [val]
  (if (nil? val) "." (str val)))

(defn board-to-str [b]
  (str-join "" (map cell-to-str (:cells b))))

(defn pretty-print-board [b]
  (let [groups (re-seq #"[1-9\.]{3}" (board-to-str b))
        lines  (drop-last (interpose-n 3 ["-----------"]
                                       (partition 3 groups)))]
    (doseq [line lines]
      (println (str-join "|" line)))))

(defn cell-to-row [n]
  "Returns the index of the row (0..8) of a given cell (0..80)"
  (.intValue (/ n 9)))

(defn cell-to-col [n]
  "Returns the index of the column (0..8) of a given cell (0..80)"
  (rem n 9))

(defn cell-to-box [n]
  "Returns the index of the box (0..8) of a given cell (0..80)"
  (let [row (cell-to-row n)
        col (cell-to-col n)]
    (+ (* 3 (int (/ row 3)))
       (int (/ col 3)))))

(defn box-to-first-cell [n]
  "Returns the index of the initial cell in box n"
  (cond (< n 3) (* n 3)
        (< n 6) (+ (* (rem n 3) 3) 27)
        (< n 9) (+ (* (rem n 3) 3) 54)))

(defn row [board n]
  "Returns the values of the cells in row n"
  (nth (partition 9 (:cells board)) n))

(defn col [board n]
  "Returns the values of the cells in column n"
  (take-nth 9 (nthrest (:cells board) n)))

(defn box [board n]
  "Returns the values of the cells in box n"
  (let [n     (box-to-first-cell n)
        cells (:cells board)]
    (concat (take-n-from 3 n cells)
            (take-n-from 3 (+ n 9) cells)
            (take-n-from 3 (+ n 18) cells))))

(defn values-in-row-of-cell [board n]
  (disj (set (row board (cell-to-row n)))
        nil))

(defn values-in-col-of-cell [board n]
  (disj (set (col board (cell-to-col n)))
        nil))

(defn values-in-box-of-cell [board n]
  (disj (set (box board (cell-to-box n)))
        nil))

(defn neighbouring-values-of-cell [board n]
  (set (concat (values-in-row-of-cell board n)
               (values-in-col-of-cell board n)
               (values-in-box-of-cell board n))))

(defn candidates-for-cell [board n]
  (if (nth (:cells board) n) nil
      (apply disj
             (set (range 1 10))
             (neighbouring-values-of-cell board n))))

; (defn solve-sudoku [board & steps]
;   (let [steps (or steps []),
;       step  (find-next-solution-step board)]
;     (if step
;       (recur (apply-solution-step board step) (conj steps step))
;       [board steps])))

(ns clojoku-test
  (:use clojure.contrib.test-is)
  (:use [clojure.contrib.str-utils :only (str-join)]))

(def board-strings
     {:empty (str-join "" (replicate 81 "."))
      :full  "253971468476582913189364257345829176891736542627415839918647325562193784734258691"
      :easy  "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"})

(deftest test-interpose-n
  (is (= nil (clojoku/interpose-n 1 0 [])))
  (is (= '(1 0) (clojoku/interpose-n 1 0 [1])))
  (is (= '(1) (clojoku/interpose-n 2 0 [1])))
  (is (= '(1 2 3 0 4 5 6 0) (clojoku/interpose-n 3 0 [1 2 3 4 5 6])))
  (is (= '(1 2 3 0 1 2 3 0 1 2) (clojoku/interpose-n 3 0 [1 2 3 1 2 3 1 2]))))

(deftest test-parse-board
  (let [empty-board (clojoku/parse-board (board-strings :empty))
        cells       (:cells empty-board)]
    (is (= cells (replicate 81 nil))))

  (let [full-board (clojoku/parse-board (board-strings :full))
        cells      (:cells full-board)]
    (is (= (count cells) 81))
    (is (empty? (filter #(= nil %) cells)))
    (is (= cells [2 5 3 9 7 1 4 6 8
                  4 7 6 5 8 2 9 1 3
                  1 8 9 3 6 4 2 5 7
                  3 4 5 8 2 9 1 7 6
                  8 9 1 7 3 6 5 4 2
                  6 2 7 4 1 5 8 3 9
                  9 1 8 6 4 7 3 2 5
                  5 6 2 1 9 3 7 8 4
                  7 3 4 2 5 8 6 9 1])))

  (let [some-board (clojoku/parse-board (board-strings :easy))
        cells      (:cells some-board)]
    (is (= (count cells) 81))
    (is (= cells [  4 nil nil nil nil nil   8 nil   5
                  nil   3 nil nil nil nil nil nil nil
                  nil nil nil   7 nil nil nil nil nil
                  nil   2 nil nil nil nil nil   6 nil
                  nil nil nil nil   8 nil   4 nil nil
                  nil nil nil nil   1 nil nil nil nil
                  nil nil nil   6 nil   3 nil   7 nil
                    5 nil nil   2 nil nil nil nil nil
                    1 nil   4 nil nil nil nil nil nil]))))

(deftest test-board-to-str
  (let [empty-board-s (board-strings :empty)
        full-board-s  (board-strings :full)
        some-board-s  (board-strings :easy)]
    (is (= empty-board-s (clojoku/board-to-str (clojoku/parse-board empty-board-s))))
    (is (= full-board-s  (clojoku/board-to-str (clojoku/parse-board full-board-s))))
    (is (= some-board-s  (clojoku/board-to-str (clojoku/parse-board some-board-s))))))

(defn pretty-printed-board [b]
  (with-out-str (clojoku/pretty-print-board b)))

(deftest test-pretty-print-board
  (let [output (pretty-printed-board (clojoku/parse-board (board-strings :easy)))]
    (is (= output "4..|...|8.5
.3.|...|...
...|7..|...
-----------
.2.|...|.6.
...|.8.|4..
...|.1.|...
-----------
...|6.3|.7.
5..|2..|...
1.4|...|...\n"))))

(deftest test-values-in-row-of-cell
  (let [easy-board (clojoku/parse-board (board-strings :easy))
        get-vals   (partial clojoku/values-in-row-of-cell easy-board)]
    (is (= #{4 8 5} (get-vals 0)))
    (is (= #{3}     (get-vals 9)))
    (is (= #{7}     (get-vals 19)))
    (is (= #{2 6}   (get-vals 30)))
    (is (= #{8 4}   (get-vals 44)))
    (is (= #{1}     (get-vals 45)))
    (is (= #{6 3 7} (get-vals 56)))
    (is (= #{5 2}   (get-vals 63)))
    (is (= #{1 4}   (get-vals 75)))))

(deftest test-values-in-col-of-cell
  (let [easy-board (clojoku/parse-board (board-strings :easy))
        get-vals   (partial clojoku/values-in-col-of-cell easy-board)]
    (is (= #{4 5 1} (get-vals 0)))
    (is (= #{4 5 1} (get-vals 9)))
    (is (= #{3 2}   (get-vals 1)))
    (is (= #{4}     (get-vals 20)))
    (is (= #{7 6 2} (get-vals 30)))
    (is (= #{8 1}   (get-vals 13)))
    (is (= #{3}     (get-vals 5)))
    (is (= #{8 4}   (get-vals 78)))
    (is (= #{6 7}   (get-vals 7)))
    (is (= #{5}     (get-vals 8)))))

(deftest test-values-in-box-of-cell
  (let [easy-board (clojoku/parse-board (board-strings :easy))
        get-vals   (partial clojoku/values-in-box-of-cell easy-board)]
    (is (= #{4 3}   (get-vals 0)))
    (is (= #{4 3}   (get-vals 10)))
    (is (= #{7}     (get-vals 3)))
    (is (= #{8 5}   (get-vals 16)))
    (is (= #{2}     (get-vals 27)))
    (is (= #{8 1}   (get-vals 30)))
    (is (= #{6 4}   (get-vals 33)))
    (is (= #{5 1 4} (get-vals 64)))
    (is (= #{6 3 2} (get-vals 57)))
    (is (= #{7}     (get-vals 60)))))

(deftest test-neighbouring-values-of-cell
  (let [easy-board (clojoku/parse-board (board-strings :easy))
        neighbours (partial clojoku/neighbouring-values-of-cell easy-board)]
    (is (= #{1 3 4 5 8} (neighbours 0)))
    (is (= #{2 3 4 5 8} (neighbours 1)))
    (is (= #{2 3 4}     (neighbours 10)))
    (is (= #{1 4 8}     (neighbours 40)))
    (is (= #{2 3 6 7}   (neighbours 59)))))

(deftest test-candidates-for-cell
  (let [easy-board (clojoku/parse-board (board-strings :easy))
        get-cands  (partial clojoku/candidates-for-cell easy-board)]
    (is (= nil          (get-cands 0)))
    (is (= #{1 6 7 9}   (get-cands 1)))
    (is (= #{1 2 6 7 9} (get-cands 2)))
    (is (= #{1 3 9}     (get-cands 3)))))

(run-tests)