Misplaced Pages

Mathematical chess problem

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Problems in mathematics concerning chessboard or the sport chess

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. 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) 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.

An 8×8 chessboard can have 16 independent kings, 8 independent queens, 8 independent rooks, 14 independent bishops, or 32 independent knights. 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.

abcdefgh
8a7 white kingc7 white kinge7 white kingg7 white kinga5 white kingc5 white kinge5 white kingg5 white kinga3 white kingc3 white kinge3 white kingg3 white kinga1 white kingc1 white kinge1 white kingg1 white king8
77
66
55
44
33
22
11
abcdefgh
16 independent kings
abcdefgh
8f8 white queend7 white queeng6 white queena5 white queenh4 white queenb3 white queene2 white queenc1 white queen8
77
66
55
44
33
22
11
abcdefgh
8 independent queens
abcdefgh
8h8 white rookg7 white rookf6 white rooke5 white rookd4 white rookc3 white rookb2 white rooka1 white rook8
77
66
55
44
33
22
11
abcdefgh
8 independent rooks
abcdefgh
8b8 white bishopc8 white bishopd8 white bishope8 white bishopf8 white bishopg8 white bishopa1 white bishopb1 white bishopc1 white bishopd1 white bishope1 white bishopf1 white bishopg1 white bishoph1 white bishop8
77
66
55
44
33
22
11
abcdefgh
14 independent bishops
abcdefgh
8b8 white knightd8 white knightf8 white knighth8 white knighta7 white knightc7 white knighte7 white knightg7 white knightb6 white knightd6 white knightf6 white knighth6 white knighta5 white knightc5 white knighte5 white knightg5 white knightb4 white knightd4 white knightf4 white knighth4 white knighta3 white knightc3 white knighte3 white knightg3 white knightb2 white knightd2 white knightf2 white knighth2 white knighta1 white knightc1 white knighte1 white knightg1 white knight8
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
8b8 white kinge8 white kingh8 white kingb5 white kinge5 white kingh5 white kingb2 white kinge2 white kingh2 white king8
77
66
55
44
33
22
11
abcdefgh
9 dominating kings
abcdefgh
8f7 white queenc6 white queene5 white queeng4 white queend3 white queen8
77
66
55
44
33
22
11
abcdefgh
5 dominating queens
abcdefgh
8d8 white bishopd7 white bishopd6 white bishopd5 white bishopd4 white bishopd3 white bishopd2 white bishopd1 white bishop8
77
66
55
44
33
22
11
abcdefgh
8 dominating bishops
abcdefgh
8f7 white knightb6 white knightc6 white knighte6 white knightf6 white knightc5 white knightf4 white knightc3 white knightd3 white knightf3 white knightg3 white knightc2 white knight8
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. 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
8b7 white kinge7 white kingh7 white kingb6 white kinge6 white kingh6 white kingb3 white kinge3 white kingh3 white kingb2 white kinge2 white kingh2 white king8
77
66
55
44
33
22
11
abcdefgh
12 kings attack all squares
abcdefgh
8g8 white queene6 white queend5 white queenc4 white queena2 white queen8
77
66
55
44
33
22
11
abcdefgh
5 queens attack all squares
abcdefgh
8b6 white bishopd6 white bishope6 white bishopg6 white bishopc4 white bishopd4 white bishope4 white bishopf4 white bishopc2 white bishopf2 white bishop8
77
66
55
44
33
22
11
abcdefgh
10 bishops attacking all squares
abcdefgh
8c7 white knighte7 white knightf7 white knightc6 white knighte6 white knightc5 white knightg5 white knightc4 white knighte4 white knightb3 white knightc3 white knighte3 white knightf3 white knightg3 white knight8
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.

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.

Chess swap problems

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

a4 black knightb4 black knightc4 black knightd4 black knight
a3 black knightb3 black knightc3d3 black knight
a2 white knightb2c2 white knightd2 white knight
a1 white knightb1 white knightc1 white knightd1 white knight
Knight swap puzzle
a5 black bishopb5 black bishopc5 black bishopd5 black bishop
a4b4c4d4
a3b3c3d3
a2b2c2d2
a1 white bishopb1 white bishopc1 white bishopd1 white bishop
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

External links

Category:
Mathematical chess problem Add topic