Re: OT: A bit of Sudoku

[Adam Beneschan <adambeneschan@gmail.com>]

On Thursday, June 5, 2014 10:49:01 AM UTC-7, Mike H wrote:
> Purely for my own amusement I have written a Sudoku puzzle solver. The 
> program is written In Ada. However being in my ninth decade I am firmly 
> stuck in an Ada95 time-warp. As a general rule, Sudoku puzzles rated as 
> 'gentle' or 'moderate' can be solved by systematic elimination of 
> alternatives. But these relatively simple deterministic methods can be 
> expected to fail when confronted by a puzzle rated as 'tough' or a 
> 'diabolical'. When this happens in my program, trial and error is 
> invoked. It is rare that more than four or five trial and error passes 
> are required.
> 
> The enclosing subprogram is called recursively by the trial and error 
> process. Each recursive call adds a pair of nodes onto an implicit but 
> invisible binary tree (the run-time call stack). What I was hoping was 
> that on detected that the solution has been found, it would be possible 
> to return to, and exit from, the main program by simply exiting each 
> recursive call in turn in order climb back up the recursion ladder. 
> 
> However, each step of that climb is a re-entry into the caller where 
> there may be remaining unfinished business. The solution having been 
> found, that unfinished business is now known to be no more than garbage. 
> Nevertheless an elegant solution might be expected to clear garbage 
> before that caller re-enters its own caller.
> 
> 
> The only solution that I can see is to jump straight out of the tree. 
> But that seems to lack elegance. The jump is made by raising an 
> exception which has been declared in, and is handled by, the enclosing 
> subprogram. The exception is 'silent' because the handler contains a 
> null statement.
> 
> I fear that perhaps I am missing something but have no idea what.

Without seeing an actual program or any code at all, I can't really tell, but ... when a caller calls itself recursively, isn't there either a function result or an OUT parameter that allows the callee to tell the caller whether it has succeeded?  In which case the caller simply exits, and returns to *its* caller passing back the correct answer and if necessary a flag indicating that it's succeeded.  I have no idea whether I've identified the problem correctly, but it's the best I can do without seeing any code.  Anyway, I think that's the general approach to handling backtracking problems.

                                -- Adam