yet another solver program

Programs which generate, solve, and analyze Sudoku puzzles

yet another solver program

Postby wes_dnvr » Mon Nov 07, 2005 8:02 pm

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.
wes_dnvr
 
Posts: 1
Joined: 07 November 2005

Postby simes » Mon Nov 07, 2005 8:40 pm

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
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK


Return to Software