37
$\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?

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
42
$\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. OEIS sequence A075458 gives the minimum number of required queens for any square board from $1\times1$ to $18\times18$.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Sep 13, 2016 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
    Commented Sep 13, 2016 at 23:05
  • $\begingroup$ That's a different, though still interesting, question. $\endgroup$
    – Xynariz
    Commented Sep 14, 2016 at 4:26
  • $\begingroup$ 5 Queens, nice. Is it even possible when limited to the standard game pieces? $\endgroup$
    – Glitch_Doctor
    Commented Jan 12, 2017 at 10:35
  • $\begingroup$ @Glitch_Doctor That'd be an interesting problem to pursue. Perhaps ask a question about it? $\endgroup$
    – Xynariz
    Commented Jan 20, 2017 at 10:02
24
$\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

Improve this answer
$\endgroup$
11
$\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

Improve this answer
$\endgroup$
1
  • 2
    $\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
    Commented Sep 12, 2016 at 19:28
1
$\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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ dude....just draw horizontal, vertical and diagonal lines along all the red dots(queens)....all squares are covered.... $\endgroup$
    – nikhil
    Commented Jan 12, 2017 at 10:51
  • 7
    $\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
    Commented Jan 20, 2017 at 10:03

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