[Tutor] Re: Interesting anomaly with the Eight Queens problem

[Kooser, Ara S]

If you go here http://en.wikipedia.org/wiki/Eight_queens_puzzle Down at
the bottom page is a very short python program that gives the solutions
to the eight queens problem in a very neat manner.

Ara




"There is something to be learned from a rainstorm. When meeting with a
sudden shower, you try not to get wet and run quickly along the road.
But doing such things as passing under the eaves of houses, you still
get wet. When you are resolved from the beginning, you will not be
perplexed, though you still get the same soaking." - Yamamoto Tsunetomo


-----Original Message-----
From: tutor-bounces at python.org [mailto:tutor-bounces at python.org] On
Behalf Of Lee Cullens
Sent: Wednesday, April 13, 2005 11:04 AM
To: jsoares at Safe-mail.net
Cc: tutor at python.org
Subject: Re: [Tutor] Re: Interesting anomaly with the Eight Queens
problem


John

The type of problem you mention and the extent of positioning you go to 
could result in an incomplete solution.  In very general terms one 
would need to place the first Queen then find an appropriate position 
for the second, and each of the remaining Queens in turn until either 
there are no appropriate positions to be found or all eight Queens have 
been positioned.  If all eight Queens can not be positioned, then the 
first Queen would be moved and the remaining Queen positioning worked 
through again.

This is a "made for recursion" type of problem, but could be done with 
nested loops.

The "Trying everything" approach can , of course, be a very lengthy 
process.  I seem to remember a more sophisticated model for this type 
of problem (I think somehow related to linear algebra) but can't recall 
the specifics at the moment.  Maybe one of the more academic (an 
younger) members of this list can point you in such a direction.

Lee C

On Apr 13, 2005, at 12:15 PM, jsoares at Safe-mail.net wrote:

> I read through Magnus Hetland's book and noticed the Eight Queens
> problem, which I had solved some time ago using Visual Basic.
>
> This time, I wanted to use a non-recursive solution. I randomly place
> each queen on board coordinates running from 0,0(top left hand corner 
> of board) to 7,7(lower right hand corner of board)
>
> Here's the interesting part: I can only get eight queens safely on the
> board perhaps every one in 20 runs. At least 12 or 13 of those times, 
> I can place seven queens, while five or six times, I can only place 
> six queens or even five!
>
> Once a queen is safely placed, I establish her "territory". Once this
> is done, when I try to place a subsequent queen, I check for all 
> placed queen's territories. Once I place six or seven queens, I have 
> to give the program a lot more tries to try to find a safe square. And

> it can't always be done.
>
> Does this sound right? Does trying to place each queen randomly cause
> this anomaly?
>
> I can post my code(beginner code!) if anyone is interested in seeing
> it.
>
> Best,
>
> John
>
> =================================
> John Soares, Webmaster
> Family Safe Surfinghttp://www.family-safe-surfing.net
> jsoares at family-safe-surfing.net
> jsoares at safe-mail.net
>
> Tel: (810) 343-0571
> Fa x: (866) 895-3082
>
> "Your best bet for online family-friendly resources" 
> =================================
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org 
> http://mail.python.org/mailman/listinfo/tutor

_______________________________________________
Tutor maillist  -  Tutor at python.org
http://mail.python.org/mailman/listinfo/tutor