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=0.6 required=5.0 tests=BAYES_40,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: walke751@concentric.net.invalid (Daryle Walker)
Subject: Eight Queens problem (was Re: Kindness)
Date: 1999/09/04
Message-ID: <walke751-0409992215490001@ts001d42.nor-ct.concentric.net>#1/1
X-Deja-AN: 521186862
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>
Organization: Concentric Internet Services
Newsgroups: comp.lang.ada
Date: 1999-09-04T00:00:00+00:00
List-Id: <comp.lang.ada>

In article <37D02CC0.BEF1BC69@mitre.org>, "Robert I. Eachus"
<eachus@mitre.org> wrote:

>Larry Kilgallen wrote:
>  
>> Another group I read has a contest going (obviously known to those who
>> really follow the group) for the most creative non-answer to homework
>> problems.  Something that goes into great detail but cannot possibly
>> be true is the ideal.
> 
>    I prefer a perfectly correct answer (not the one intended by the
>instructor of course), that references material that the student may not
>encounter for years.  For example, I could program the eight queens
>problem with eight interacting tasks as a demonstration of rendesvous. 
>(Nico Lomuto wrote a neat eight queens program years ago which generated
>a new set of tasks for possible position in the next row.  I wonder if
>there are now machines that can run it.)

What is this Eight Queens Problem?  I've heard of it only in passing; I
never had to do it as an assignment (BTW, I've been out of school for 2
years).  I'm guessing it's how to place eight queen chess pieces on a
chess board without any of them threatening another.  Where can I find
more information about it?  What is Nico Lomuto's Ada-task solution?

[For those who haven't heard of chess, a chess board has a grid of 64
squares in a 8-by-8 square.  A queen piece can attack any enemy piece that
can be directly intercepted via a row, column, or 45-degree diagonal.]

[Just from a minimal description, I can guess a solution:
   1. Put a queen on a random square
   2. Mark the queen's square, squares on the same row and column,
      and squares diagonally connected, invalid
   3. Repeat the previous steps for the next 7 queens
      (using valid squares only, of course)
 I got the feeling that there's some gotchas to this newbie approach,
 like all good CS problems have.]

-- 
Daryle Walker
Video Game, Mac, and Internet Junkie
walke751 AT concentric DOT net