Thanks Konrad A very elegant solution. 40 years of laziness, and I finally realize what a great feature the lazy evaluation is ;)
Tzach On Jan 9, 3:30 pm, Konrad Hinsen <konrad.hin...@laposte.net> wrote: > On Jan 9, 2009, at 13:18, Tzach wrote: > > > > > The main functionsudokuis recursive: > > 1. Getting asudokuboard as an input > > 2. Choosing the next empty (zero) cell to test, loop on all valid > > values, and callsudokuwith the new board > > 3. When a solution (board with no zero values) is found: throw. > > > (defnsudoku[board] > > "solve asudokuproblem" > > (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. Yoursudokufunction could have a structure like this: > > (defnsudoku[board] > "solve asudokuproblem" > (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: > > (defnsudoku[board] > "solve asudokuproblem" > (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 clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
