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.50.80.13 with SMTP id n13mr7598358igx.0.1402000857909; Thu, 05 Jun 2014 13:40:57 -0700 (PDT) X-Received: by 10.50.164.129 with SMTP id yq1mr10747igb.15.1402000857724; Thu, 05 Jun 2014 13:40:57 -0700 (PDT) Path: border1.nntp.dca3.giganews.com!backlog3.nntp.dca3.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.glorb.com!h18no819062igc.0!news-out.google.com!gi6ni19657igc.0!nntp.google.com!c1no23633042igq.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Thu, 5 Jun 2014 13:40:57 -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> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <3d4f61d0-8f8f-49e9-a4ce-8fedffc5da10@googlegroups.com> Subject: Re: OT: A bit of Sudoku From: Adam Beneschan Injection-Date: Thu, 05 Jun 2014 20:40:57 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Original-Bytes: 3247 Xref: number.nntp.dca.giganews.com comp.lang.ada:186751 Date: 2014-06-05T13:40:57-07:00 List-Id: On Thursday, June 5, 2014 1:03:10 PM UTC-7, Mike H wrote: > I chose, perhaps wrongly, that the complete grid of 81 cells is passed=20 > down the recursion tree (as IN OUT). At each level, the grid is further= =20 > completed as the full gamut of deterministic algorithms is exercised=20 > before either a lack of further success prompts a further trial and=20 > error attempt or a positive failure forces a return of up the tree.=20 > Thus, a return of control to a caller is taken as a positive signal of=20 > failure. But, currently, there is no equivalent positive indicator of=20 > success. My own experience with problems of this sort has been that passing the enti= re problem-state to the next level as an IN OUT parameter (or the equivalen= t, in other languages) makes life more difficult. The callee needs to be a= ble to make changes to the problem-state in order to try different possibil= ities; 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 thin= g on the problem-state it was given as an input parameter. The last time I= wrote a Sudoku solver, I therefore made sure the grid I passed to recursiv= e calls was a (modified) copy of the input parameter, not a reference to th= e same parameter. For some kinds of problems, this might be unfeasible; bu= t an array of 81 integers is pretty easy to handle. By the way, the progra= m found answers almost instantaneously, and it used only backtracking--no a= ttempt to try to deal with simple cases the way I would approach it if solv= ing by hand. So while it might be interesting (and instructive) to try to = write a program that will work optimally, in practice it isn't necessary fo= r this particular game. Good luck. Backtracking programs aren't easy to write correctly. -- Adam