Mathematical chess problem

Last updated

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.

Contents

Independence problem

An independence problem (or unguard [2] ) 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. [3] [4]

An 8×8 chessboard can have 16 independent kings, 8 independent queens, 8 independent rooks, 14 independent bishops, or 32 independent knights. [5]

abcdefgh
8
Chessboard480.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
8
77
66
55
44
33
22
11
abcdefgh
16 independent kings
abcdefgh
8
Chessboard480.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
8 independent queens
abcdefgh
8
Chessboard480.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
8 independent rooks
abcdefgh
8
Chessboard480.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
8
77
66
55
44
33
22
11
abcdefgh
14 independent bishops
abcdefgh
8
Chessboard480.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
32 independent knights

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.

abcdefgh
8
Chessboard480.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
8
77
66
55
44
33
22
11
abcdefgh
9 dominating kings
abcdefgh
8
Chessboard480.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
5 dominating queens
abcdefgh
8
Chessboard480.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
8
77
66
55
44
33
22
11
abcdefgh
8 dominating bishops
abcdefgh
8
Chessboard480.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
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. [6] 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.

abcdefgh
8
Chessboard480.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
Chess klt45.svg
8
77
66
55
44
33
22
11
abcdefgh
12 kings attack all squares
abcdefgh
8
Chessboard480.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
Chess qlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
5 queens attack all squares
abcdefgh
8
Chessboard480.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
Chess blt45.svg
8
77
66
55
44
33
22
11
abcdefgh
10 bishops attacking all squares
abcdefgh
8
Chessboard480.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
Chess nlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
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. [7]

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. [8]

Chess swap problems

In chess swap problems, the whites pieces swap with the black pieces. [9] 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.

Chess ndl45.svg Chess ndd45.svg Chess ndl45.svg Chess ndd45.svg
Chess ndd45.svg Chess ndl45.svg Chess d45.svg Chess ndl45.svg
Chess nll45.svg Chess d45.svg Chess nll45.svg Chess nld45.svg
Chess nld45.svg Chess nll45.svg Chess nld45.svg Chess nll45.svg
Knight swap puzzle
Chess bdd45.svg Chess bdl45.svg Chess bdd45.svg Chess bdl45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess bld45.svg Chess bll45.svg Chess bld45.svg Chess bll45.svg
Bishop swap puzzle

See also

Notes

  1. Gik, p.11
  2. MacKinnon, David. "Chessdom". GitHub. Retrieved October 20, 2024.
  3. "Independent Pieces tour!". Lichess. Retrieved 9 July 2022.
  4. "mathrecreation: Mathematical Chessboard Puzzles". mathrecreation. Retrieved 9 July 2022.
  5. Gik, p.98
  6. Gik, p.101.
  7. 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
  8. Gik, p. 87
  9. "Knight swap puzzle - Chess Forums".

References