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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,3e08c98d7ce85399
X-Google-Attributes: gid103376,public
From: "Robert I. Eachus" <eachus@mitre.org>
Subject: Re: Eight Queens problem (was Re: Kindness)
Date: 1999/09/14
Message-ID: <37DEC173.FA3D5083@mitre.org>#1/1
X-Deja-AN: 525149426
Content-Transfer-Encoding: 7bit
References: <37CC6844.AB898EEE@rational.com> <37CE93CD.799A225A@pwfl.com>
 <37CF0FE0.2B299477@acenet.com.au> <37CFF7DC.CFF9717C@pwfl.com>
 <1999Sep3.125818.1@eisner> <37D02CC0.BEF1BC69@mitre.org>
 <walke751-0409992215490001@ts001d42.nor-ct.concentric.net>
 <7qsqvb$974$1@nnrp1.deja.com>
X-Accept-Language: en
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: usenet@news.mitre.org
X-Trace: top.mitre.org 937345129 11593 129.83.41.77 (14 Sep 1999 21:38:49 GMT)
Organization: The MITRE Corporation
Mime-Version: 1.0
NNTP-Posting-Date: 14 Sep 1999 21:38:49 GMT
Newsgroups: comp.lang.ada
Date: 1999-09-14T21:38:49+00:00
List-Id: <comp.lang.ada>

Robert Dewar wrote:
 
> Well there is no magic in real life, so the normal
> implementation of AD is to make an arbitrary choice, and
> then if you get stuck later, go back and change it. This
> is called "back tracking", and basicaly the 8-queens
> problem is precisely an excercise in back tracking.
 
    The method used by Nico Lomuto's solution was to create a task for
each possible placement at each level, and the first task that
corresponded to a correct solution would stop the creation of new tasks
and cause all the waiting tasks, whether part of an incorrect or correct
solution, to terminate.  The problem is that doing this requires lots of
tasks, I believe Nico's program potentially created 8! (40,320) of
them.  Since Nico's program was written to show a clever use of the
terminate alternative it wouldn't run correctly even on systems that
waited during task creation for a task descriptor to become free--all
tasks waited for a solution to be found.

    Ah, the advantage of being a pack rat.  The original article was in
Ada Letters March-April 1983 pages II-5.62-75.  I think that the
application to the Eight Queens problem was published later as a
concrete example of the paper, but it would probably be much easier to
reconstruct it than find it.

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...