Board index › Topical Discussion › Computers, Math, Science, and Technology

Chess board problem.

Page 1 of 2 [ 18 posts ]  Go to page 1, 2  Next

Previous topic | Next topic

ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

21 Jan 2011, 9:57 am

What is the minimum number of queens that can be placed on a standard 8 x 8 chess board such that all unoccupied squares are attacked by at least one queen and no two queens attack each other.

ruveyn



MidlifeAspie
Veteran
Veteran

User avatar

Joined: 1 Nov 2010
Age: 47
Gender: Male
Posts: 3,016

21 Jan 2011, 12:59 pm

Two, unless you are playing with a different set of rules than the ones I was taught :)



Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 34
Gender: Male
Posts: 12,518
Location: Room 101

21 Jan 2011, 1:05 pm

Six will suffice. The answer is not unique, but one solution is queens on a1, b3, c5, d7, e4, and h6


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

21 Jan 2011, 1:28 pm

Orwell wrote:
Six will suffice. The answer is not unique, but one solution is queens on a1, b3, c5, d7, e4, and h6


It can be done with five.

ruveyn



kxmode
Supporting Member
Supporting Member

User avatar

Joined: 14 Oct 2007
Gender: Male
Posts: 2,613
Location: In your neighborhood, knocking on your door. :)

21 Jan 2011, 1:45 pm

ruveyn wrote:
What is the minimum number of queens that can be placed on a standard 8 x 8 chess board such that all unoccupied squares are attacked by at least one queen and no two queens attack each other.


Image



Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 34
Gender: Male
Posts: 12,518
Location: Room 101

21 Jan 2011, 6:14 pm

ruveyn wrote:
Orwell wrote:
Six will suffice. The answer is not unique, but one solution is queens on a1, b3, c5, d7, e4, and h6


It can be done with five.

ruveyn

I didn't spend much time looking at it; just threw some pieces on a board. Six was an easy upper bound to determine. I'll give it another look.


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

21 Jan 2011, 6:30 pm

MidlifeAspie wrote:
Two, unless you are playing with a different set of rules than the ones I was taught :)


Two queens is not sufficient.

ruveyn



flipflopjenkins
Snowy Owl
Snowy Owl

User avatar

Joined: 4 Jul 2008
Age: 44
Gender: Male
Posts: 168

21 Jan 2011, 6:48 pm

ruveyn wrote:
Orwell wrote:
Six will suffice. The answer is not unique, but one solution is queens on a1, b3, c5, d7, e4, and h6


It can be done with five.

ruveyn


In that case, the answer for an n x n board seems to be ... (drumroll) ... [n/2] + 1, where [n/2] is n/2 rounded down to the nearest integer.

This works at least for 3 < n < 9.

Watch this space.



Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 34
Gender: Male
Posts: 12,518
Location: Room 101

22 Jan 2011, 9:21 pm

OK, I still haven't attempted a rigorous approach to this, but just placing queens on the board, I find several arrangements where 5 queens are able to attack all but 1 square.


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


Titangeek
Veteran
Veteran

User avatar

Joined: 22 Aug 2010
Age: 30
Gender: Male
Posts: 7,696
Location: somewhere in the vicinity of betelgeuse

24 Jan 2011, 12:09 am

kxmode wrote:
ruveyn wrote:
What is the minimum number of queens that can be placed on a standard 8 x 8 chess board such that all unoccupied squares are attacked by at least one queen and no two queens attack each other.


Image


:lol:


_________________
Always be yourself, express yourself, have faith in yourself, do not go out and look for a successful personality and duplicate it.
- Bruce Lee


CrinklyCrustacean
Veteran
Veteran

User avatar

Joined: 22 Mar 2009
Age: 40
Gender: Male
Posts: 1,284

24 Jan 2011, 12:14 am

It depends how many other pieces are on the board.



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

24 Jan 2011, 10:18 am

Orwell wrote:
OK, I still haven't attempted a rigorous approach to this, but just placing queens on the board, I find several arrangements where 5 queens are able to attack all but 1 square.


If you give up, then look at
http://mathworld.wolfram.com/QueensProblem.html

ruveyn



Orwell
Veteran
Veteran

User avatar

Joined: 8 Aug 2007
Age: 34
Gender: Male
Posts: 12,518
Location: Room 101

24 Jan 2011, 12:21 pm

Interesting.

Do you play chess?


_________________
WAR IS PEACE
FREEDOM IS SLAVERY
IGNORANCE IS STRENGTH


ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

24 Jan 2011, 1:24 pm

Orwell wrote:
Interesting.

Do you play chess?


I prefer Go.

ruveyn



kxmode
Supporting Member
Supporting Member

User avatar

Joined: 14 Oct 2007
Gender: Male
Posts: 2,613
Location: In your neighborhood, knocking on your door. :)

24 Jan 2011, 7:10 pm

ruveyn wrote:
What is the minimum number of queens that can be placed on a standard 8 x 8 chess board such that all unoccupied squares are attacked by at least one queen and no two queens attack each other.


The answer is 8.

Image



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

24 Jan 2011, 8:00 pm

kxmode wrote:
ruveyn wrote:
What is the minimum number of queens that can be placed on a standard 8 x 8 chess board such that all unoccupied squares are attacked by at least one queen and no two queens attack each other.


The answer is 8.

Image


8 is the maximum, not the minimum. (for an 8 x 8 board).

5 queens can be placed such that no two queens attack each other and every unoccupied square is attacked by at least one queen. Four queens won't do. No matter how one places four queen on an 8 x 8 board so that no two queens attack each other there are unoccupied squares which are not attacked by any queen.

ruveyn