Re: OT: A bit of Sudoku

[Mike H <postmaster@ada-augusta.demon.co.uk>]

In message <5365d3f0-43cc-47ef-989c-d47992c84c9f@googlegroups.com
>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.
Thank you for giving me an alternative angle of view.

The trial and error process is optimised by preselection of a matching 
pair of cells, they match in the sharing of a common pair of candidate 
solutions. By analogy, it is a choice of left or right. On  average, 50% 
of trials will have explored both possibilities in which the first will 
have been wrong and the second will have proved to be correct. In the 
other 50%, the first choice will have been correct so the second choice 
is left dangling and unvisited..

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.

I am beginning to think that a three-state flag is required (NO,  MAYBE, 
YES). YES is not known until the 81st cell is solved. The job is now 
complete and control must now be passed back up the tree. What is 
different is that a YES would be a tangible way of contradicting the 
previous assumption that a return of control means failure.

-- 
Mike
Swim? Naturally at Severn Vale
<http://www.severnvalesc.org/>