Re: OT: A bit of Sudoku

[Stefan.Lucks@uni-weimar.de]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1783 bytes --]

On Thu, 5 Jun 2014, Adam Beneschan wrote:

> 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.

It really depends on the problem you are trying to solve.

> 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.

Right. So the callee *must* undo the change(s) it made, before returning 
without a solution. If undoing is that trivial, then an in-out parameter 
(or "global" variable declared in some outer scope) for the state is 
reasonable. It may even be useful to transfer a solution found back to the 
callee (just don't undo the changes you made ...).

As I understand for the Sudoku case, the entire change is to assign a 
digit to an empty cell, and undoing means to turn the cell's state back to 
empty. If I am right, undoing changes is very easy, indeed!

> The last time I wrote a Sudoku solver,

Well, I have never written a Sudoku solver, but I did apply the 
above approach to other backtracking problems, see, e.g., 
<http://rosettacode.org/wiki/Knight%27s_tour#Ada>.

BTW, a Sudoku-solver for Ada is still missing at Rosetta Code 
<http://rosettacode.org/wiki/Sudoku>.


So long

Stefan

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--