On Sun, Oct 11, 2009 at 22:12, Matt Wilson <m...@problemattic.net> wrote:
>
> My approach (which I might upload once I've tidied it up a bit) was to
> use a hash-map of [x y] cell coordinates to a set of all remaining
> numbers. So, something like:
>
> {[0 0] #{1 2 3 4} [0 1] #{5 6 7 8} …}
>
> Then I just made some functions that mapped an [x y] pair to all it's
> peers -- e.g. unit, row, col (which were generated by another
> function.) I memoized those functions.
>
> The only hassle with a map is that iterating over it (in my case, with
> a `for`) turns it into a list of [key value], which makes it a pain to
> turn back into a map once you're done. The magical incantation for
> round-tripping turns out to be:
>
> (apply hash-map (apply concat seq-of-pairs))
I've recently hacked up my own sudoku solver. This is essentially the
representation I've chosen, except that I use integers 0 through 80 to
identify positions on the game board. This allows my to use vectors
where you'd have used a map.
So, I've got a vector which we'll call freedoms, indexed from 0 to 80,
which contains sets of symbols from the solution alphabet, specifying
which symbols are possible at that position.
Additionally, for each position p, I keep a sorted map (could have
used a vector here too, I guess) from (count (freedoms p)) to a set of
all p with that (count (freedoms p)). We'll call it freeranks. This
has two advantages:
1. it's wasy to see when I'm done (= 81 (count (freeranks 1))
2. It's easy to find the position for the next move:
(first
(apply
concat
(for [[nfree positions] freeranks :when (> nfree 1)]
positions)))
It turns out to be *very* beneficial to always choose the move with
the fewest freedoms as the next move.
--
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
