From: Robert Dewar <robert_dewar@my-deja.com>
Subject: Re: Eight Queens problem (was Re: Kindness)
Date: 1999/09/05
Date: 1999-09-05T00:00:00+00:00 [thread overview]
Message-ID: <7qsqvb$974$1@nnrp1.deja.com> (raw)
In-Reply-To: walke751-0409992215490001@ts001d42.nor-ct.concentric.net
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.
next prev parent reply other threads:[~1999-09-05 0:00 UTC|newest]
Thread overview: 45+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-08-31 0:00 Kindness Mark Lundquist
1999-09-02 0:00 ` Kindness Marin David Condic
1999-09-03 0:00 ` Kindness Geoff Bull
1999-09-03 0:00 ` Kindness Marin David Condic
1999-09-03 0:00 ` Kindness Larry Kilgallen
1999-09-03 0:00 ` Kindness tmoran
1999-09-03 0:00 ` Kindness Marin David Condic
1999-09-03 0:00 ` Kindness Robert I. Eachus
1999-09-04 0:00 ` Eight Queens problem (was Re: Kindness) Daryle Walker
1999-09-05 0:00 ` Robert Dewar [this message]
1999-09-14 0:00 ` Robert I. Eachus
1999-09-06 0:00 ` Vladimir Olensky
1999-09-06 0:00 ` Robert Dewar
1999-09-07 0:00 ` bourguet
1999-09-08 0:00 ` Robert Dewar
1999-09-08 0:00 ` bourguet
1999-09-08 0:00 ` Robert Dewar
1999-09-08 0:00 ` Ted Dennison
[not found] ` <37D55622.69B27515@rational.com>
1999-09-07 0:00 ` Homework " Larry Kilgallen
1999-09-08 0:00 ` Ted Dennison
1999-09-08 0:00 ` Homework Mark Lundquist
1999-09-03 0:00 ` Kindness Robert Dewar
1999-09-03 0:00 ` Kindness Aidan Skinner
1999-09-03 0:00 ` Kindness Marin David Condic
1999-09-06 0:00 ` Kindness Bill Findlay
1999-09-06 0:00 ` Kindness Robert Dewar
1999-09-07 0:00 ` Kindness Marin David Condic
1999-09-07 0:00 ` Kindness Bill Findlay
1999-09-03 0:00 ` Kindness Larry Kilgallen
1999-09-04 0:00 ` Kindness Aidan Skinner
1999-09-06 0:00 ` Kindness Geoff Bull
1999-09-05 0:00 ` Kindness Aidan Skinner
1999-09-02 0:00 ` Kindness Larry Kilgallen
1999-09-03 0:00 ` Kindness Robert Dewar
1999-09-03 0:00 ` Kindness Andy Askey
1999-09-05 0:00 ` Kindness Robert Dewar
1999-09-07 0:00 ` Kindness Andy Askey
1999-09-07 0:00 ` Kindness Bill Findlay
1999-09-02 0:00 ` Kindness Jerry Petrey
1999-09-02 0:00 ` Kindness Nick Roberts
1999-09-03 0:00 ` Kindness Matthew Heaney
1999-09-09 0:00 ` Kindness James William Zuercher
1999-09-10 0:00 ` Kindness Mark Lundquist
1999-09-10 0:00 ` Kindness Robert Dewar
1999-09-10 0:00 ` Kindness Robert Dewar
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox