Mathematical chess problem
A mathematical chess problem is a mathematical problem which is formulated using a chessboard and chess pieces. These problems belong to recreational mathematics. The most well-known problems of this kind are the eight queens puzzle and the knight's tour problem, which have connection to graph theory and combinatorics. Many famous mathematicians studied mathematical chess problems, such as, Thabit, Euler, Legendre and Gauss.[1] Besides finding a solution to a particular problem, mathematicians are usually interested in counting the total number of possible solutions, finding solutions with certain properties, as well as generalization of the problems to N×N or M×N boards.
Independence problem
An independence problem (or unguard[citation needed]) is a problem in which, given a certain type of chess piece (queen, rook, bishop, knight or king), one must find the maximum number that can be placed on a chessboard so that none of the pieces attack each other. It is also required that an actual arrangement for this maximum number of pieces be found. The most famous problem of this type is the eight queens puzzle. Problems are further extended by asking how many possible solutions exist. Further generalizations apply the problem to NxN boards.[2][3]
An 8×8 chessboard can have 16 independent kings, 8 independent queens, 8 independent rooks, 14 independent bishops, or 32 independent knights.[4] Solutions for kings, bishops, queens and knights are shown below. To get 8 independent rooks is sufficient to place them on one of main diagonals.
|
Script error: No such module "Chessboard". |
Script error: No such module "Chessboard". |
Script error: No such module "Chessboard". |
|
Script error: No such module "Chessboard". |
Script error: No such module "Chessboard". |
Domination problems
A domination (or covering) problem involves finding the minimum number of pieces of the given kind to place on a chessboard such that all vacant squares are attacked at least once. It is a special case of the vertex cover problem. The minimum number of dominating kings is 9, queens is 5, rooks is 8, bishops is 8, and knights is 12. To get 8 dominating rooks, it is sufficient to place one on each file. Solutions for other pieces are provided on diagrams below.
| Script error: No such module "Chessboard". | Script error: No such module "Chessboard". |
| Script error: No such module "Chessboard". | Script error: No such module "Chessboard". |
The domination problems are also sometimes formulated as requiring one to find the minimal number of pieces needed to attack all squares on the board, including occupied ones.[5] For rooks, eight are required; the solution is to place them all on one file or rank. The solutions for other pieces are given below.
| Script error: No such module "Chessboard". | Script error: No such module "Chessboard". |
| Script error: No such module "Chessboard". | Script error: No such module "Chessboard". |
Domination by queens on the main diagonal of a chessboard of any size can be shown equivalent to a problem in number theory of finding a Salem–Spencer set, a set of numbers in which none of the numbers is the average of two others. The optimal placement of queens is obtained by leaving vacant a set of squares that all have the same parity (all are in even positions or all in odd positions along the diagonal) and that form a Salem–Spencer set.[6]
Piece tour problems
These kinds of problems ask to find a tour of certain chess piece, which visits all squares on a chess board. The most known problem of this kind is Knight's Tour. Besides the knight, such tours exists for king, queen and rook. Bishops are unable to reach each square on the board, so the problem for them is formulated to reach all squares of one color.[7]
Chess swap problems
In chess swap problems, the whites pieces swap with the black pieces.[8] This is done with the pieces' normal legal moves during a game, but alternating turns is not required. For example, a white knight can move twice in a row. Capturing pieces is not allowed. Two such problems are shown below. In the first one the goal is to exchange the positions of white and black knights. In the second one the positions of bishops must be exchanged with an additional limitation, that enemy pieces do not attack each other.
| Template:Chess diagram 4x4 | Template:Chess diagram 4x5 |
See also
Notes
- ↑ Gik, p.11
- ↑ "Independent Pieces tour!". https://lichess.org/study/qh6KRVKE/texPCF3W.
- ↑ "mathrecreation: Mathematical Chessboard Puzzles". http://www.mathrecreation.com/2018/04/mathematical-chessboard-puzzles.html.
- ↑ Gik, p.98
- ↑ Gik, p.101.
- ↑ Cockayne, E. J.; Hedetniemi, S. T. (1986), "On the diagonal queens domination problem", Journal of Combinatorial Theory, Series A 42 (1): 137–139, doi:10.1016/0097-3165(86)90012-9
- ↑ Gik, p. 87
- ↑ "Knight swap puzzle - Chess Forums". https://www.chess.com/forum/view/fun-with-chess/knight-swap-puzzle.
References
- Evgeni J Gik (1986). Schach und Mathematik. Moskau, Verlag MIR und Leipzig, Urania-Verlag. ISBN 978-3930640379. (in German). Some chapters of the book are available online: Евгений Гик "Шахматы и математика" and as DJVU file (in Russian).
External links
- Chess by Weisstein, Eric W. from MathWorld.
- Chess-Piece Arrangement Problems by George Jelliss (from The Games and Puzzles Journal).
- Chessboard Tasks by Ed Pegg Jr.
 |  |
