Re: [Tutor] Re: Interesting anomaly with the Eight Queens problem
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, [EMAIL PROTECTED] 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 [EMAIL PROTECTED] [EMAIL PROTECTED] Tel: (810) 343-0571 Fa x: (866) 895-3082 "Your best bet for online family-friendly resources" = ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
RE: [Tutor] Re: Interesting anomaly with the Eight Queens problem
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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Lee Cullens Sent: Wednesday, April 13, 2005 11:04 AM To: [EMAIL PROTECTED] Cc: tutor@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, [EMAIL PROTECTED] 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 > [EMAIL PROTECTED] > [EMAIL PROTECTED] > > Tel: (810) 343-0571 > Fa x: (866) 895-3082 > > "Your best bet for online family-friendly resources" > = > > ___ > Tutor maillist - Tutor@python.org > http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
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, [EMAIL PROTECTED] 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 [EMAIL PROTECTED] [EMAIL PROTECTED] Tel: (810) 343-0571 Fa x: (866) 895-3082 "Your best bet for online family-friendly resources" = ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
