Re: OT: A bit of Sudoku

[Adam Beneschan <adambeneschan@gmail.com>]

On Friday, June 6, 2014 2:10:43 AM UTC-7, Stefan...@uni-weimar.de wrote:
> 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!

That makes assumptions about the algorithm.  If the data structure that represents the current problem state has additional information--for instance, if the data structure also has some additional summary information intended to help optimize the solver's search process--then undoing changes becomes more difficult.  You *could* use a simple 81-integer array as the entire state information, but there's nothing that says you have to; if you use a record that has, say, an 81-integer array, an 9-element array that holds a bit vector to indicate which numbers have been used in row, and similar 9-element arrays for each column and 3x3 grid, then undoing becomes messier, while copying is still simple.  (I'd have to go back and look for the algorithm I used last time I wrote a program for this, but I think I was using bit vectors like this to speed up the process.)  Copying becomes more difficult when the state information involves linked lists or trees or something like that.

Anyway, either way is a possibility; I'm just saying that in the cases I've worked with, the copying approach has worked better.  

                              -- Adam