16 May
2012
16 May
'12
5:41 p.m.
On May 16, 2012, at 5:47 PM, Mouse wrote:
I didn't do a full complexity analysis on mine,
because it uses
heuristics that mean any human-solvable puzzle is solved in so close to
zero time that it's not worth improving it. (Specifically, most of the
time there is at least one cell that can be filled in only one way for
some reason, and the program knows at least four different possible
such reasons; I've rarely seen puzzles needing a search tree with more
than a dozen or so nodes, and many need no search at all, ie, there is
no backtracking.)
Mine didn't have a search tree; it just kept a list of possible values
for its cells and removed them as the pre-filled values for the puzzle
were entered (i.e. if that value were added to the cell's row, column
or box). If a cell ever wound up with only one possibility, it would
fill that value in, etc. For a properly deterministic puzzle (and I'm
given to understand that a puzzle isn't "right" if it's not
deterministic), this would result in an answer by the time the last
pre-filled value was entered.
Using "human" strategies, there might be faster ways. I'd be curious
to see how it worked on non-deterministic puzzles (if indeed valid
ones do exist).
The actual class assignment is still online here; it's entertaining
reading, if nothing else. His assignments from other years pose
other interesting algorithmic challenges.
http://www.csee.umbc.edu/~tadwhite/441.f05/project.html
- Dave