16 May
2012
16 May
'12
8:12 p.m.
(Specifically,
most of the time there is at least one cell that can
be filled in only one way for some reason, [...]; 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. The actual class assignment is still online here;
it's entertaining
reading, if nothing else. [...]
http://www.csee.umbc.edu/~tadwhite/441.f05/project.html
I find it interesting that his idea of "proper" sudoku includes no
backtracking necessary, but does not mention symmetry - though all his
sample puzzles do indeed have 180-degree rotational symmetry in the
pattern of pre-filled cells - whereas I thought the symmetry was one of
the things which made a proper sudoku but was unaware of any
prohibition on backtracking. (And, yes, my program has no trouble with
any of his examples, once the input format is converted, and resorts to
tree search on only the one he doesn't say shouldn't need it.)
/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B