Hi Clojure fans
My first attempt with Clojure is a Sudoku solver, and I'm fighting
with what are probably trivial problems (for a non newbie)
The main function sudoku is recursive:
1. Getting a sudoku board as an input
2. Choosing the next empty (zero) cell to test, loop on all valid
values, and call sudoku with the new board
3. When a solution (board with no zero values) is found: throw.
(defn sudoku [board]
"solve a sudoku problem"
(when (complete? board)
(do
(println "complete")
(print-board board)
(throw nil)))
(let [cell (next-cell board)
pos (first cell)
valid-values (second cell)]
(when cell
(doseq [v valid-values]
(sudoku (assoc-in board pos v)))
)))
Although it does work, we can all agree its pretty ugly, so I would
appreciate your help on the following questions:
1. How to can I return a solution via the recursive stack with out
throwing an exception? I understand there is no "return-from"
facility.
2. Can this function be implemented as tail recursive (using loop?
recur?)
Naturally, any other inputs are welcome.
Thanks
Tzach
---------------
Full source:
(defn print-board [board]
"Pretty print the sudoku board"
(doseq [row board] (println row)))
(defn mod3range [x]
(let [start (- x (rem x 3))]
(range start (+ 3 start))))
(defn neighbors-pos [pos]
"return a collection of neighbors positions to pos"
(remove #(= pos %)
(distinct (concat
(for [y (range 3) z (range 3)] [(get pos 0) y z]) ; row
neighbors
(for [x (range 9)] [x (get pos 1) (get pos 2)]) ; col
neighbors
(for [x (mod3range (get pos 0)) z (range 3)] [x (get pos 1)
z]))) ; square neighbors;
))
(defn neighbors-values [board pos]
"return a list of neighbor positions values"
(map #(get-in board %) (neighbors-pos pos)))
(defn valid-values [board pos]
"return a list of values which does not violate the neighbors
values. return nil if the position already have a value"
(if (zero? (get-in board pos))
(clojure.set/difference (set (range 1 10)) (neighbors-values board
pos))
(seq nil)))
(defn map-board [board f]
"execute function f on each of the position on board. function
f get the position and the board as parameters"
(for [x (range 9) y (range 3) z (range 3)]
(let [pos [x y z]]
[pos (f board pos) ]
)))
(defn next-cell [board]
"return the next potential cell to set, and the valid alternatives"
(first (filter
#(not (empty? (second %)))
(sort-by #(count (second %)) (map-board board valid-values)))))
(defn complete? [board]
(not (some #(second %)
(map-board board (fn [board pos] (zero? (get-in board pos)))))))
(defn sudoku [board]
"solve a sudoku problem"
(when (complete? board)
(do
(println "complete")
(print-board board)
(throw nil)))
(let [cell (next-cell board)
pos (first cell)
valid-values (second cell)]
(when cell
(doseq [v valid-values]
(sudoku (assoc-in board pos v)))
)))
;;; use the solver
(def *sudoku-problem*
[[[0 0 0] [5 0 0] [0 9 1]]
[[1 0 0] [8 6 0] [0 3 2]]
[[0 0 6] [9 3 0] [0 0 0]]
[[0 0 4] [6 0 0] [0 7 3]]
[[0 5 0] [4 9 3] [0 1 0]]
[[3 6 0] [0 0 8] [9 0 0]]
[[0 0 0] [0 8 5] [3 0 0]]
[[8 3 0] [0 1 6] [0 0 5]]
[[6 7 0] [0 0 9] [0 0 0]]])
(sudoku *sudoku-problem*)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
