August 2008
<<July August September>>
This month's puzzle is a variant of the famous 8-queens problem (see http://en.wikipedia.org/wiki/Eight_queens).
The original problem is to place as many queens as possible on an 8x8 chess board such that no queen will threaten another (a queen threatens all the squares in its row, column, and both diagonals).
In our version we need to place as many queens as possible on an NxN board, such that each queen will threaten at most *one* other queen. We ask to prove an upper bound and give a solution matching it for the standard 8x8 board as well as for a 30x30 board. The solution should be sent as pairs of x,y coordinates.
Thanks to Vladimir Sedach for suggesting the question.
UPDATE 8/11/08: As some of you wrote to us, it seems that our problem above is ill defined since we did not say if a queen A can block queen B from threatening queen C; However, it is easy to see that it does not matter in our case since queen A threatens more than one queen (both queens B and C) which is not allowed.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
08/01/2008 @ 09:00 AM EST
Solution:
09/01/2008 @ 09:00 AM EST
List Updated:
09/01/2008 @ 03:00 PM EST
People who answered correctly:
Frank Yang (08.05.2008 @05:06 PM EDT)
Hongcheng Zhu (08.06.2008 @08:07 AM EDT)
Eugene Vasilchenko (08.06.2008 @11:57 AM EDT)
Balakrishnan V (08.06.2008 @08:54 PM EDT)
John Tromp (08.07.2008 @11:45 AM EDT)
Andreas Eisele (08.09.2008 @07:23 AM EDT)
Joe DeVincentis (08.09.2008 @11:13 AM EDT)
Steffen Wolf (08.11.2008 @05:25 AM EDT)
Harald Bögeholz + Andreas Stiller (08/12/2008 02:45 PM EDT)
Nyles Heise (08/13/2008 12:33 AM EDT)
John G Fletcher (08/14/2008 12:38 AM EDT)
Danny Antonetti (08/14/2008 12:58 AM EDT)
Máté Bartalos (08/15/2008 08:17 AM EDT)
Li Zou (08/15/2008 12:53 AM EDT)
Michael Brand (08/15/2008 04:55 PM EDT)
Gary M. Gerken (08/20/2008 09:57 AM EDT)
Josh Bowman (08/21/2008 12:15 PM EDT)
Bojan Basic (08/21/2008 11:16 AM EDT)
Dan Dima (08/22/2008 12:03 PM EDT)
David Papp (08/24/2008 10:39 PM EDT)
Zhou Guang (08/24/2008 11:24 PM EDT)
Michael Schaaf (08/25/2008 02:22 PM EDT)
Albert Stadler (08/27/2008 01:54 PM EDT)
Matt Gara (08/28/2008 01:42 AM EDT)
Raphael Finkel (08/28/2008 09:39 AM EDT)
Nagy Zoltan (08/30/2008 05:53 PM EDT)
Jesse Kolman (09/01/2008 02:30 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.