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.236.222.36 with SMTP id s34mr1468052yhp.24.1401993029848; Thu, 05 Jun 2014 11:30:29 -0700 (PDT) X-Received: by 10.182.50.201 with SMTP id e9mr380390obo.2.1401993029735; Thu, 05 Jun 2014 11:30:29 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!news.glorb.com!hw13no4871104qab.0!news-out.google.com!gi6ni19621igc.0!nntp.google.com!h18no800195igc.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Thu, 5 Jun 2014 11:30:29 -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: User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <5365d3f0-43cc-47ef-989c-d47992c84c9f@googlegroups.com> Subject: Re: OT: A bit of Sudoku From: Adam Beneschan Injection-Date: Thu, 05 Jun 2014 18:30:29 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:20145 Date: 2014-06-05T11:30:29-07:00 List-Id: On Thursday, June 5, 2014 10:49:01 AM UTC-7, Mike H wrote: > Purely for my own amusement I have written a Sudoku puzzle solver. The=20 > program is written In Ada. However being in my ninth decade I am firmly= =20 > stuck in an Ada95 time-warp. As a general rule, Sudoku puzzles rated as= =20 > 'gentle' or 'moderate' can be solved by systematic elimination of=20 > alternatives. But these relatively simple deterministic methods can be=20 > expected to fail when confronted by a puzzle rated as 'tough' or a=20 > 'diabolical'. When this happens in my program, trial and error is=20 > invoked. It is rare that more than four or five trial and error passes=20 > are required. >=20 > The enclosing subprogram is called recursively by the trial and error=20 > process. Each recursive call adds a pair of nodes onto an implicit but=20 > invisible binary tree (the run-time call stack). What I was hoping was=20 > that on detected that the solution has been found, it would be possible= =20 > to return to, and exit from, the main program by simply exiting each=20 > recursive call in turn in order climb back up the recursion ladder.=20 >=20 > However, each step of that climb is a re-entry into the caller where=20 > there may be remaining unfinished business. The solution having been=20 > found, that unfinished business is now known to be no more than garbage.= =20 > Nevertheless an elegant solution might be expected to clear garbage=20 > before that caller re-enters its own caller. >=20 >=20 > The only solution that I can see is to jump straight out of the tree.=20 > But that seems to lack elegance. The jump is made by raising an=20 > exception which has been declared in, and is handled by, the enclosing=20 > subprogram. The exception is 'silent' because the handler contains a=20 > null statement. >=20 > I fear that perhaps I am missing something but have no idea what. Without seeing an actual program or any code at all, I can't really tell, b= ut ... when a caller calls itself recursively, isn't there either a functio= n result or an OUT parameter that allows the callee to tell the caller whet= her it has succeeded? In which case the caller simply exits, and returns t= o *its* caller passing back the correct answer and if necessary a flag indi= cating that it's succeeded. I have no idea whether I've identified the pro= blem 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. -- Adam