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

[Lee Cullens]

So there is no misunderstanding, the trial positioning would be 
applicable to all levels, not just the first. In other words, solving 
for each of the remaining Queens in turn is the same as for the first 
Queen, except for the eighth Queen where no lower level positioning 
need be considered,


On Apr 13, 2005, at 1:04 PM, Lee Cullens wrote:

> 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
>