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,
	MSGID_RANDY 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 Dewar <robert_dewar@my-deja.com>
Subject: Re: Eight Queens problem (was Re: Kindness)
Date: 1999/09/05
Message-ID: <7qsqvb$974$1@nnrp1.deja.com>#1/1
X-Deja-AN: 521201400
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>
X-Http-Proxy: 1.0 x33.deja.com:80 (Squid/1.1.22) for client 166.72.70.239
Organization: Deja.com - Share what you know. Learn what you don't.
X-Article-Creation-Date: Sun Sep 05 04:18:56 1999 GMT
X-MyDeja-Info: XMYDJUIDrobert_dewar
Newsgroups: comp.lang.ada
X-Http-User-Agent: Mozilla/4.04 [en] (OS/2; I)
Date: 1999-09-05T00:00:00+00:00
List-Id: <comp.lang.ada>

In article
<walke751-0409992215490001@ts001d42.nor-ct.concentric.net>,
  walke751@concentric.net.invalid (Daryle Walker) wrote:
> [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.]


You will find it very instructive to try using the above
algorithm by hand.

What you will find is that step 1 is wrong, it makes a
difference *which* square you choose. You can get stuck
if you make wrong choices.

What you need here is sometimes called "angelic
non-determinism", i.e. make the "right" choice by
some magic method.

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.

It is instructive, but not trivial, to try to work out
how to do this yourself :-)


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.