From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.58.218.232 with SMTP id pj8mr3931512vec.3.1402070770093; Fri, 06 Jun 2014 09:06:10 -0700 (PDT) X-Received: by 10.182.78.70 with SMTP id z6mr15827obw.36.1402070769862; Fri, 06 Jun 2014 09:06:09 -0700 (PDT) Path: border1.nntp.dca3.giganews.com!backlog3.nntp.dca3.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!j5no1946926qaq.1!news-out.google.com!qf4ni19593igc.0!nntp.google.com!c1no23870484igq.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Fri, 6 Jun 2014 09:06:09 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=66.126.103.122; posting-account=KSa2aQoAAACOxnC0usBJYX8NE3x3a1Xq NNTP-Posting-Host: 66.126.103.122 References: <5365d3f0-43cc-47ef-989c-d47992c84c9f@googlegroups.com> <3d4f61d0-8f8f-49e9-a4ce-8fedffc5da10@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <7b3ff390-6153-4f2c-9966-fe4de4f3e989@googlegroups.com> Subject: Re: OT: A bit of Sudoku From: Adam Beneschan Injection-Date: Fri, 06 Jun 2014 16:06:09 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Original-Bytes: 3974 Xref: number.nntp.dca.giganews.com comp.lang.ada:186766 Date: 2014-06-06T09:06:09-07:00 List-Id: On Friday, June 6, 2014 2:10:43 AM UTC-7, Stefan...@uni-weimar.de wrote: > On Thu, 5 Jun 2014, Adam Beneschan wrote: >=20 > > My own experience with problems of this sort has been that passing the= =20 > > entire problem-state to the next level as an IN OUT parameter (or the= =20 > > equivalent, in other languages) makes life more difficult. >=20 > It really depends on the problem you are trying to solve. >=20 > > The callee needs to be able to make changes to the problem-state in=20 > > order to try different possibilities; the caller needs the problem-stat= e=20 > > to stay the same, so that if the callee returns without finding a=20 > > solution, the caller can try the next thing on the problem-state it was= =20 > > given as an input parameter. >=20 > Right. So the callee *must* undo the change(s) it made, before returning= =20 > without a solution. If undoing is that trivial, then an in-out parameter= =20 >=20 > (or "global" variable declared in some outer scope) for the state is=20 > reasonable. It may even be useful to transfer a solution found back to th= e=20 > callee (just don't undo the changes you made ...). >=20 > As I understand for the Sudoku case, the entire change is to assign a=20 > digit to an empty cell, and undoing means to turn the cell's state back t= o=20 > empty. If I am right, undoing changes is very easy, indeed! That makes assumptions about the algorithm. If the data structure that rep= resents the current problem state has additional information--for instance,= if the data structure also has some additional summary information intende= d to help optimize the solver's search process--then undoing changes become= s 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-e= lement arrays for each column and 3x3 grid, then undoing becomes messier, w= hile copying is still simple. (I'd have to go back and look for the algori= thm I used last time I wrote a program for this, but I think I was using bi= t vectors like this to speed up the process.) Copying becomes more difficu= lt when the state information involves linked lists or trees or something l= ike 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. =20 -- Adam