On Sat, Oct 10, 2009 at 4:21 PM, Mark Engelberg <mark.engelb...@gmail.com>wrote:
>
> Represent each cell as a row number, column number, and a set of
> possible digits that can go in that cell.
> Create a map that generates a keyword for the sector name from the row
> and column numbers.
> You're going to write a recursive function that processes a sequence
> of cells that still need to be analyzed, but this sequence is not
> maintained in grid order. Instead you keep them sorted by the number
> of possibilities for that cell. Do a backtracking search, starting
> with the cell with the fewest possibilities. When you assign a number
> to a cell, you remove that number from the possibilities in the other
> cells sharing the same row/column/sector. If you ever have an empty
> possibility list for a cell at the front of your still-to-analyze
> sequence, then you need to backtrack.
>
>
That's exactly the approach the Python code takes. My problem is not finding
the right algorithm but making into idiomatic clojure.
I've been told this solution isn't idiomatic:
(defn cross [A B]
(for [a A b B] (str a b)))
(def rows "ABCDEFGHI")
(def cols "123456789")
(def squares (cross rows cols))
(def unitlist (concat (for [c cols] (cross rows (str c)))
(for [r rows] (cross (str r) cols))
(for [rs (partition 3 rows)
cs (partition 3 cols)]
(cross rs cs))))
(def units (into {} (map (fn [s] {s (filter #(some (partial = s) %)
unitlist)}) squares)))
(def peers (into {} (map (fn [s] {s (apply hash-set (for [u (units s) s2
u :when (not= s2
s)] s2))})
squares)))
But its author couldn't put his finger on what's non-idiomatic about it.
The beauty is that with Clojure's non-destructive data structures, the
> backtracking is so elegant and easy to code, just using recursion.
> It's so much messier in Python. If you don't know how to do
> backtracking in functional programming languages, check out How To
> Design Programs:
> http://htdp.org/2003-09-26/Book/curriculum-Z-H-35.html#node_chap_28
>
>
The Python version also makes good use of cheap copies. That's one reason
why it felt like a good fit for a clojure port.
--~--~---------~--~----~------------~-------~--~----~
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
Note that posts from new members are moderated - please be patient with your
first post.
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
-~----------~----~----~----~------~----~------~--~---
