The New Sudoku Players' Forum

[wes_dnvr]

Over the weekend I put together a program to solve Sudoku puzzles. Then I come to this site and see these programs are quite common!
Anyway, as I've worked on these puzzles, I've noted that those in my newspaper classified as "easy" and "medium" do not require exploring candidate entries with backtracking when these candidates prove to be wrong, but "hard" puzzles seem to require this. I've been too impatient to explore these candidate search paths by hand with all the erasing and keeping track of what entries are fixed and what entries are being tentatively tried. But my program deals with this quite well. It's a recursive formulation (reminiscient of search problems in a computer science class). A board state is a matrix with each cell having a final value (possibly not specified), and a list of "can be" values and "cannot be" values. A candidate search path uses one of the "can be" values as the final value of the cell and tries to populate the board with this in place. If the board becomes inconsistent (with a cell having no possible values) then backtracking is performed. If a consistent board can have no further cells populated then another recursive call is performed with an additional candidate value.
I'm new to this site so I'm not up on the terminology in use here. I'll look around to see how my thinking about these puzzles compares to others' thinking. Any feedback is appreciated, thanks.

[simes]

Most (ok, "most" is a complete guess) puzzles from newspapers don't require backtracking (or T&E, or guessing). Pappocom's puzzles certainly don't, although they may require some solving techniques you're not aware of.

If you'd like some in-depth reading, take a look here

Simon