The following problems (and solutions) come from a Master of Basic Science project by University of Colorado at Denver student Kris Kulpa.
In a domination problem you are asked for the minimum number of playing
pieces (kings, queens, bishops or rooks) that can be placed on a given
size board so that each "unoccupied" square is attacked by at least one
piece. (Pieces may or may not attack one another).
For example, you can dominate a 3x7 board with 3 rooks (place one in
each row, any column).
For domination problems, rooks are easy, on an nxm
board you need the minimum of n and m. For other pieces, the question is
More difficult problems of this type:
- Dominate a 3x12 board with 8 knights.
- Dominate a 4x5 board with 4 knights.
- Dominate a 3x6 board with 2 kings.
- Dominate a 4x9 board with 6 kings.
- Dominate a 5x7 board with 3 queens.
- Dominate a 6x8 board with 4 queens.
More thoughtful questions:
- Dominate a 6x8 board with 8 knights.
- Dominate a 3x14 board with 11 knights.
- Dominate a 5x12 board with 4 queens.
- Dominate a 5x12 board with 10 bishops.
1. What is the minimum number of queens needed to dominate boards of
sizes 3x3, 3x4, 3x5, 3x6 and 3x7? Find a pattern in the number of queens
needed and the size of the board, so that you can predict the number of
queens needed for a 3x10 or a 3x20 board. Give an explanation of why your
answer is correct. How did you go about getting your answer?
2. What is the minimum number of knights needed to dominate a 2x3, 2x5,
2x7 and 2x10 board? Find a pattern involving the number of knights needed
and the size of the 2xn board. Give an explanation of why your answer is
A total domination is a domination as above but with the added
restriction that every piece must be attacked by another piece.
- Totally dominate a 4x9 board with 4 queens.
- Totally dominate a 4x9 board with 10 knights.
- Totally dominate a 5x8 board with 4 queens.
- Totally dominate a 4x6 board with 6 knights.
- Totally dominate a 5x5 board with 6 bishops.
1. 6 knights are needed to totally dominate a 3x5 board. Find an
arrangement of 6 knights that does this and explain why you think it can
not be done with fewer than 6 knights.
- Totally dominate a 5x9 board with 4 queens.
- Totally dominate a 6x7 board with 4 queens.
2. Find the minimum number of kings needed to totally dominate a 3x5,
3x8, 3x9 and 3x11 board. Give a written explanation of why your answers
are correct. Can you find a pattern in the number of kings needed and the
size of the board?
Solutions to most of these problems are available here.
Further information on these types of chessboard problems can be found in the articles:
1. E.J. Cockayne, "Chessboard Domination Problems", Discrete Mathematics, 86(1990), pp. 13-20.
2. M. Gardner, Mathematical Magic Show, W.H. Freeman & Co. , New York, 1977, pp. 127, 194-202.