although writing a program to solve Sudoku puzzles
would also be a
fun effort.
I found it so. Writing code to generate sudoku was fun too, [...]
My experience writing Sudoku solvers was for an algorithms class,
which was quite an interesting look at it. It was actually a rather
boring algorithm for solving, and the only part that was much
challenge was the data structure to bring the time down to O(n^6)
instead of O(n^7), where n is the order of the puzzle (e.g. 3 for a
normal 9x9 puzzle).
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.)
/~\ 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
