On Jan 9, 2009, at 13:18, Tzach wrote:
> 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.
The return value of a function is the last expression that was
evaluated. Your sudoku function could have a structure like this:
(defn sudoku [board]
"solve a sudoku problem"
(if (complete? board)
board
(let [...]
..))
The problem is then in the let branch, as it can terminate without
returning a valid board.
> 2. Can this function be implemented as tail recursive (using loop?
> recur?)
As it is, no, because you have multiple recursive calls. However, I
wonder what those are good for. If I understand your algorithm
correctly, it find all valid values for the next cell to be filled,
and then tries for each of them to complete the puzzle, using a
recursive call.
I would rewrite the solver as a function that returns a lazy sequence
of valid solutions:
(defn all-solutions [board]
(if (complete? board)
(list board)
(let [[pos valid-values] (next-cell board)]
(apply concat (for [v valid-values]
(all-solutions (assoc-in board pos v)))))))
Note that you don't have to do anything to make the sequences lazy;
apply and for take care of that automatically.
The solver then just takes the first item of that sequence:
(defn sudoku [board]
"solve a sudoku problem"
(first (all-solutions board)))
Since the sequence is lazy, the remaining solutions (if any) are
never computed, so this version does not do more work than your
original one.
Konrad.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
