wu :: forums « wu :: forums - How many queens? » Welcome, Guest. Please Login or Register. Jun 30th, 2022, 10:05am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, Eigenray, ThudnBlunder, Icarus, towr, Grimbal, SMQ)    How many queens? « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: How many queens?  (Read 12222 times)
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 How many queens?   « on: Nov 5th, 2003, 7:53pm » Quote Modify

(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.)
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: How many queens?   « Reply #1 on: Nov 6th, 2003, 9:17am » Quote Modify

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?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How many queens?   « Reply #2 on: Nov 6th, 2003, 9:28am » Quote Modify

I had wondered that myself, but there's a solution in both cases, so I just assumed normal chess-rules.. (not a real solution yet though, just a few examples for smaller chessboards)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
visitor
Guest

 Re: How many queens?   « Reply #3 on: Nov 6th, 2003, 2:41pm » Quote Modify Remove

Wading in cautiously, my first attempt at a solution came up with 16 queens. I hope the real answer is not an order of magnitude higher than that.
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: How many queens?   « Reply #4 on: Nov 6th, 2003, 5:23pm » Quote Modify

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).
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How many queens?   « Reply #5 on: Nov 7th, 2003, 3:09am » Quote Modify

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..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
visitor
Guest

 Re: How many queens?   « Reply #6 on: Nov 7th, 2003, 7:31am » Quote Modify Remove

Okay, I found 17. Are we there yet?
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: How many queens?   « Reply #7 on: Nov 7th, 2003, 3:59pm » Quote Modify

Good, but not yet. (18 isn't the answer either).
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: How many queens?   « Reply #8 on: Nov 8th, 2003, 8:54am » Quote Modify

Here's my try:
[smiley=blacksquare.gif]
20 queens: a2,a4,a5,a7; b1,b8; c1,c8; d1,d8; e1,e8; f1,f8; g1,g8; h2,h3,h6,h7.
[smiley=blacksquare.gif]

 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: How many queens?   « Reply #9 on: Nov 12th, 2003, 7:46pm » Quote Modify

That can still be bettered, barely.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How many queens?   « Reply #10 on: Nov 13th, 2003, 12:50am » Quote Modify

ha, 21 then
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: How many queens?   « Reply #11 on: Nov 13th, 2003, 9:39am » Quote Modify

Yes - 21 is the max - but how do you accomplish it? And how do you prove it is max?
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: How many queens?   « Reply #12 on: Nov 13th, 2003, 10:49am » Quote Modify

on Nov 13th, 2003, 9:39am, Icarus wrote:
 Yes - 21 is the max - but how do you accomplish it? And how do you prove it is max?

Thanks for clarifying. I would try to build the optimal configuration and look at its properties.

BTW, Icarus, can you tell whether the 21-queens configuration resembles mine?
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: How many queens?   20queens.PNG « Reply #13 on: Nov 13th, 2003, 6:09pm » Quote Modify

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).
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
SWF
Uberpuzzler

Posts: 879
 Re: How many queens?   « Reply #14 on: Nov 17th, 2003, 7:08pm » Quote Modify

on Nov 7th, 2003, 3:09am, towr wrote:
 I'd say n=5 is allready impossible..

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.

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How many queens?   « Reply #15 on: Nov 24th, 2009, 7:38am » Quote Modify

on Nov 24th, 2009, 6:57am, Hippo wrote:
Probably spam that was promptly delete by a moderator.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Vondell
Junior Member

Gender:
Posts: 78
 Re: How many queens?   « Reply #16 on: Nov 24th, 2009, 4:29pm » Quote Modify

Nah, I had posted a question which I answered myself not much longer afterward, so I deleted it.
 IP Logged

Why is it that people ask for my two cents worth, and then only offer me a penny for my thoughts?
That deal sucks!
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: How many queens?   « Reply #17 on: Nov 25th, 2009, 2:05am » Quote Modify

on Nov 17th, 2003, 7:08pm, SWF 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.

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.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: How many queens?   « Reply #18 on: Nov 25th, 2009, 5:54am » Quote Modify

on Nov 25th, 2009, 2:05am, Grimbal 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.

...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.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: How many queens?   « Reply #19 on: Nov 29th, 2009, 7:55am » Quote Modify

Well, yes... the question was about a regular chess board.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: How many queens?   « Reply #20 on: Jan 6th, 2010, 7:57am » Quote Modify

on Nov 29th, 2009, 7:55am, Grimbal wrote:
 Well, yes... the question was about a regular chess board.

The question was about a regular chess board and n=4

on Nov 5th, 2003, 7:53pm, Icarus wrote:
 Generalize to arbitrary size boards, and attacking n other queens, for n other than 4.

My comment was for the generalised version where the arbitrary size board need not be bounded.
 IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: How many queens?   « Reply #21 on: Jan 9th, 2010, 7:55am » Quote Modify

on Nov 5th, 2003, 7:53pm, Icarus wrote:
 Generalize to arbitrary size boards, and attacking n   other other queens, for n than 4.)

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.

 « Last Edit: Jan 9th, 2010, 7:56am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: How many queens?   « Reply #22 on: Jan 9th, 2010, 10:45am » Quote Modify

on Jan 6th, 2010, 7:57am, rmsgrey wrote:
 My comment was for the generalised version where the arbitrary size board need not be bounded

OK, sorry.  Indeed, my answer was meant for the case of a regular (or at least finite) board.
 IP Logged
lopez
Newbie

Posts: 10
 Re: How many queens?   « Reply #23 on: Jul 12th, 2012, 3:07am » Quote Modify

There are only two queens in a single game
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: How many queens?   « Reply #24 on: Jul 12th, 2012, 4:59am » Quote Modify

on Jul 12th, 2012, 3:07am, lopez wrote:
 There are only two queens in a single game

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.
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »