Mathematical chess problem
From Wikipedia the free encyclopedia
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[edit]
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.
16 independent kings |
8 independent queens |
8 independent rooks | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
14 independent bishops |
32 independent knights | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Domination problems[edit]
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.
9 dominating kings |
5 dominating queens | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 dominating bishops |
12 dominating knights | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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.
12 kings attack all squares |
5 queens attack all squares | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10 bishops attacking all squares |
14 knights attacking all squares | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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[edit]
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[edit]
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.
Knight swap puzzle |
Bishop swap puzzle |
See also[edit]
Notes[edit]
- ^ Gik, p.11
- ^ "Independent Pieces tour!". Lichess. Retrieved 9 July 2022.
- ^ "mathrecreation: Mathematical Chessboard Puzzles". mathrecreation. Retrieved 9 July 2022.
- ^ 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, MR 0843468
- ^ Gik, p. 87
- ^ "Knight swap puzzle - Chess Forums".
References[edit]
- 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[edit]
- 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.