Re: OT: A bit of Sudoku

[Adam Beneschan <adambeneschan@gmail.com>]

On Thursday, June 5, 2014 1:03:10 PM UTC-7, Mike H wrote:

> I chose, perhaps wrongly, that the complete grid of 81 cells is passed 
> down the recursion tree (as IN OUT). At each level, the grid is further 
> completed as the full gamut of deterministic algorithms is exercised 
> before either a lack of further success prompts a further trial and 
> error attempt or a positive failure forces a return of up the tree. 
> Thus, a return of control to a caller is taken as a positive signal of 
> failure. But, currently, there is no equivalent positive indicator of 
> success.

My own experience with problems of this sort has been that passing the entire problem-state to the next level as an IN OUT parameter (or the equivalent, in other languages) makes life more difficult.  The callee needs to be able to make changes to the problem-state in order to try different possibilities; the caller needs the problem-state to stay the same, so that if the callee returns without finding a solution, the caller can try the next thing on the problem-state it was given as an input parameter.  The last time I wrote a Sudoku solver, I therefore made sure the grid I passed to recursive calls was a (modified) copy of the input parameter, not a reference to the same parameter.  For some kinds of problems, this might be unfeasible; but an array of 81 integers is pretty easy to handle.  By the way, the program found answers almost instantaneously, and it used only backtracking--no attempt to try to deal with simple cases the way I would approach it if solving by hand.  So while it might be interesting (and instructive) to try to write a program that will work optimally, in practice it isn't necessary for this particular game.

Good luck.  Backtracking programs aren't easy to write correctly.

                                    -- Adam