29
$\begingroup$

Given an 8x8 chessboard, your goal is to "cover" each space on the board with the fewest possible number of pieces. A space is "covered" if there is a piece on it, or if a piece on the board can be moved to that space in one move.

A trivially easy solution would be that a board could be covered with 64 pieces. If you place a piece on every square, every square is obviously covered.

A less trivial solution is 8 - fill an entire row or column with rooks. Obviously, each rook can cover all spaces in its row or column, so the board is covered.

Can this be done with less than 8 pieces? If so, what is the minimum number of pieces required?

$\endgroup$
33
$\begingroup$

Yes. The minimum number of pieces required is 5.

5 queens can be places such that they cover every space on the board, as in the following example:

It only takes 5 queens to "cover" a full 8x8 chessboard. color coded version

There are 12 such arrangements, along with rotation and reflection of each of them.

Edit: The above proves that 5 queens is enough, but it doesn't prove that 4 queens isn't enough. According to this MathOverflow question and its answers, there is no easy logical or mathematical proof, but it has been proven by completely evaluating all possible arrangements of queens on a board. See this list to see the minimum number of required queens for any square board from $1\times1$ to $18\times18$.

$\endgroup$
  • $\begingroup$ How many of those arrangements also threaten the squares the queens are standing on? (if we look at the image you have above, the queens don't threaten each other's squares. if somehow one of them were captured after moving into this position, you'd no longer have a correct answer) $\endgroup$ – Kingrames Sep 13 '16 at 22:57
  • 1
    $\begingroup$ I realize you're following the rules of the question, and I'm not calling that into question. My above comment was just brainstorming. $\endgroup$ – Kingrames Sep 13 '16 at 23:05
  • $\begingroup$ That's a different, though still interesting, question. $\endgroup$ – Xynariz Sep 14 '16 at 4:26
  • $\begingroup$ 5 Queens, nice. Is it even possible when limited to the standard game pieces? $\endgroup$ – Glitch_Doctor Jan 12 '17 at 10:35
  • $\begingroup$ @Glitch_Doctor That'd be an interesting problem to pursue. Perhaps ask a question about it? $\endgroup$ – Xynariz Jan 20 '17 at 10:02
20
$\begingroup$

This type of chess puzzle is known as a domination problem, and as @Xynariz points out, only five queens are needed for the 8x8 board. It's also interesting to note that five queens are also sufficient for the 9x9, 10x10, and 11x11 boards, as shown by the following diagram taken from a Russian chess-puzzle book found here.

5 queens suffice

$\endgroup$
8
$\begingroup$

Agreed that 5 queens is the answer.But here's an easier solution to the problem,

Consider X as the positions of queens marked on the chessboard

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Yes, this is one of the 12 solutions mentioned in my answer above. I don't know if I'd call this an "easier solution", but it is definitely easier to remember. :) $\endgroup$ – Xynariz Sep 12 '16 at 19:28
0
$\begingroup$

Solution: place a queen on each of the five red dots shown below. All squares on the board are then covered by at least one of these queens.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ dude....just draw horizontal, vertical and diagonal lines along all the red dots(queens)....all squares are covered.... $\endgroup$ – nikhil Jan 12 '17 at 10:51
  • 2
    $\begingroup$ I'm wondering why somebody added a new answer to an almost-three-year-old question, while providing nothing not covered in other answers, while also not even bothering to explain their answer (though the edit helped significantly). $\endgroup$ – Xynariz Jan 20 '17 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.