

Title: How many queens? Post by Icarus on Nov 5^{th}, 2003, 7:53pm (What's this? A chess puzzle from Icarus? Not quite...) How many queens can be placed on a chess board so that each threatens exactly 4 others? Generalize to arbitrary size boards, and attacking n other queens, for n other than 4. (For n>0, the problem is due to Scott Kim. n=0 is a classic problem.) 

Title: Re: How many queens? Post by Barukh on Nov 6^{th}, 2003, 9:17am A clarification question: If two queens are at the same line, but separated by a 3rd queen, are they at the threat to each other? 

Title: Re: How many queens? Post by towr on Nov 6^{th}, 2003, 9:28am I had wondered that myself, but there's a solution in both cases, so I just assumed normal chessrules.. (not a real solution yet though, just a few examples for smaller chessboards) 

Title: Re: How many queens? Post by visitor on Nov 6^{th}, 2003, 2:41pm Wading in cautiously, my first attempt at a solution came up with [hide] 16 [/hide]queens. I hope the real answer is not an order of magnitude higher than that. 

Title: Re: How many queens? Post by Icarus on Nov 6^{th}, 2003, 5:23pm Queens only threaten each other if there are no intervening pieces. (However the other problem may be interesting as well). 16 is a trivially easy solution for the n=3 problem (just place two rows of 8 on opposite sides of the board)  of couse it is not maximum there either. The solution for n=4 is higher than 16, but not by an order of magnitude. After all, there are only 64 available positions, and it is fairly obvious most of them will need to be empty! Some related questions (I know  you haven't got this one, but thinking about these cases might spark some ideas for this one): What happens for n=8? What happens for n=4 if you replace "queen" with "rook" or "bishop"? (or "king" or "knight", but those two are less closely related to the queen problem). 

Title: Re: How many queens? Post by towr on Nov 7^{th}, 2003, 3:09am with n=8 the field has to be empty (every queen needs to be surrounded on all sides, but that's impossible at the edge) I'd say n=5 is allready impossible.. 

Title: Re: How many queens? Post by visitor on Nov 7^{th}, 2003, 7:31am Okay, I found 17. Are we there yet? 

Title: Re: How many queens? Post by Icarus on Nov 7^{th}, 2003, 3:59pm Good, but not yet. (18 isn't the answer either). 

Title: Re: How many queens? Post by Barukh on Nov 8^{th}, 2003, 8:54am Here's my try: [smiley=blacksquare.gif] [hide]20 queens: a2,a4,a5,a7; b1,b8; c1,c8; d1,d8; e1,e8; f1,f8; g1,g8; h2,h3,h6,h7.[/hide] [smiley=blacksquare.gif] ::) 

Title: Re: How many queens? Post by Icarus on Nov 12^{th}, 2003, 7:46pm That can still be bettered, barely. 

Title: Re: How many queens? Post by towr on Nov 13^{th}, 2003, 12:50am ha, [hide]21[/hide] then :P 

Title: Re: How many queens? Post by Icarus on Nov 13^{th}, 2003, 9:39am Yes  21 is the max  but how do you accomplish it? And how do you prove it is max? 

Title: Re: How many queens? Post by Barukh on Nov 13^{th}, 2003, 10:49am on 11/13/03 at 09:39:15, Icarus wrote:
Thanks for clarifying. I would try to build the optimal configuration and look at its properties. BTW, Icarus, can you tell whether the 21queens configuration resembles mine? 

Title: Re: How many queens? Post by Icarus on Nov 13^{th}, 2003, 6:09pm According to Martin Gardner, someone name William Marshall did an exhaustive computer search and found 40 solutions  not counting reflections and rotations  for 21 queens. He also provided a nice elementary proof (which Gardner did not reproduce) that 21 was the max for an 8x8 board. Gardner only showed one solution, which shows some similarities to yours, but also some differences. In particular, a 21 queen position obviously cannot be symmetric. He also gave a 20 queen solution which differs from yours in the positions of two queens (after a rotation  his was open to the top). 

Title: Re: How many queens? Post by SWF on Nov 17^{th}, 2003, 7:08pm on 11/07/03 at 03:09:31, towr wrote:
I agree than n>4 is not possible: A queen in a corner can attack no more than 3 other queens, and a queen on an edge can attack no more than 5. If n>3 the corner cannot have a queen on it. Since the corner is is vacant, the edge square next to can only attack 4 queens, so if n>4 that square must be empty. Similarly for the edge square next to it and so on to the end of the row. Now repeat from first square on next row. A queen there can attack a maximum of 3 queens since the row above it is vacant... Therefore, for n>4 zero queens can be placed on the board satisfying the conditions. 

Title: Re: How many queens? Post by towr on Nov 24^{th}, 2009, 7:38am on 11/24/09 at 06:57:06, Hippo wrote:


Title: Re: How many queens? Post by Vondell on Nov 24^{th}, 2009, 4:29pm Nah, I had posted a question which I answered myself not much longer afterward, so I deleted it. 

Title: Re: How many queens? Post by Grimbal on Nov 25^{th}, 2009, 2:05am on 11/17/03 at 19:08:25, SWF wrote:
Or more directly: Consider the topmost row with a queen on it. Consider the leftmost queen on that row. That queen can attack only in 4 directions. So n>4 cannot have a queen on the board. 

Title: Re: How many queens? Post by rmsgrey on Nov 25^{th}, 2009, 5:54am on 11/25/09 at 02:05:15, Grimbal wrote:
...assuming that the topmost row and leftmost queen on that row are identifiable  an infinite number of queens can each threaten 5 others on a board that extends infinitely east and west  and a board without boundaries can support infinitely many each attacking 8 others. 

Title: Re: How many queens? Post by Grimbal on Nov 29^{th}, 2009, 7:55am Well, yes... the question was about a regular chess board. 

Title: Re: How many queens? Post by rmsgrey on Jan 6^{th}, 2010, 7:57am on 11/29/09 at 07:55:29, Grimbal wrote:
The question was about a regular chess board and n=4 on 11/05/03 at 19:53:25, Icarus wrote:
My comment was for the generalised version where the arbitrary size board need not be bounded. 

Title: Re: How many queens? Post by ThudanBlunder on Jan 9^{th}, 2010, 7:55am on 11/05/03 at 19:53:25, Icarus wrote:
Letting order of the board be k For n= 2, max = 2k  2 for k > 2 For n = 3, max = largest even number less than or equal to (12k  4)/5 For n = 4, max = 3k  3 for k > 5 For n = 1, k = 9 n = 2, k = 5 n = 2, k = 6 n = 4, k = 6 there are unique solutions. 

Title: Re: How many queens? Post by Grimbal on Jan 9^{th}, 2010, 10:45am on 01/06/10 at 07:57:10, rmsgrey wrote:
OK, sorry. Indeed, my answer was meant for the case of a regular (or at least finite) board. 

Title: Re: How many queens? Post by lopez on Jul 12^{th}, 2012, 3:07am There are only two queens in a single game 

Title: Re: How many queens? Post by rmsgrey on Jul 12^{th}, 2012, 4:59am on 07/12/12 at 03:07:41, lopez wrote:
There can be up to 18 queens in a single game. Disclaimer: I have not evolved a line of play to demonstrate this, nor proved that such a line must exist  it's possible to promote all sixteen pawns during the course of a game (requiring at least eight captures of pieces by pawns) but it may not be possible to promote all sixteen pawns and juggle all eighteen queens without producing a stalemate or checkmate position on the way. 

Title: Re: How many queens? Post by Acequotes on Oct 6^{th}, 2012, 1:07am There are only 4 queens in a single game :) 

Title: Re: How many queens? Post by peoplepower on Oct 6^{th}, 2012, 5:09am Not correct, the position after black's move 23 in this real game has 5 queens. http://www.chessgames.com/perl/chessgame?gid=1282607 Disconcerted by NN? Here's another (black's 69th move). http://www.chessgames.com/perl/chessgame?gid=1316514 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 