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?
Answer
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:
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$.
No comments:
Post a Comment