Mathematical chess problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Mathematical chess problem is a mathematical problem which is formulated using a chessboard and chess pieces. These problems belong to recreational mathematics. The most known problems of this kind are Eight queens puzzle or Knight's Tour problems, which have connection to graph theory and combinatorics. Many famous mathematicians studied mathematical chess problems, for example, 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 NxN or rectangular boards.

Independence problems[edit]

Independence problems (or unguards) are a family of the following problems. Given a certain chess piece (queen, rook, bishop, knight or king) find the maximum number of such pieces, which can be placed on a chess board 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 Eight queens puzzle. Problems are further extended by asking how many possible solutions exist. Further generalization are the same problems for NxN boards.

The maximum number of independent kings on 8x8 chessboard is 16, queens - 8, rooks - 8, bishops - 14, knights - 32.[2] Solutions for kings and bishops are shown below. To get 8 independent rooks is sufficient to place them on one of main diagonals. A solution for 32 independent knights is to place them all on squares of the same color (e.g. place all 32 knights on dark squares).

a b c d e f g h
8
Chessboard480.svg
a7 white king
c7 white king
e7 white king
g7 white king
a5 white king
c5 white king
e5 white king
g5 white king
a3 white king
c3 white king
e3 white king
g3 white king
a1 white king
c1 white king
e1 white king
g1 white king
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
16 independent kings
a b c d e f g h
8
Chessboard480.svg
b8 white bishop
c8 white bishop
d8 white bishop
e8 white bishop
f8 white bishop
g8 white bishop
a1 white bishop
b1 white bishop
c1 white bishop
d1 white bishop
e1 white bishop
f1 white bishop
g1 white bishop
h1 white bishop
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
14 independent bishops

Domination problems[edit]

Another kind of mathematical chess problems is a domination problem (or covering). In these problems it is requested to find a minimum number of pieces of the given kind and place them on a chess board in such a way, that all free squares of the board are attacked by at least one piece. The minimal number of dominating kings is 9, queens - 5, rooks - 8, bishops - 8, knights - 12. To get 8 dominating rooks one can place them on one of main diagonals. Solutions for other pieces are provided on diagrams below.

a b c d e f g h
8
Chessboard480.svg
b8 white king
e8 white king
h8 white king
b5 white king
e5 white king
h5 white king
b2 white king
e2 white king
h2 white king
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
9 dominating kings
a b c d e f g h
8
Chessboard480.svg
f7 white queen
c6 white queen
e5 white queen
g4 white queen
d3 white queen
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
5 dominating queens
a b c d e f g h
8
Chessboard480.svg
d8 white bishop
d7 white bishop
d6 white bishop
d5 white bishop
d4 white bishop
d3 white bishop
d2 white bishop
d1 white bishop
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
8 dominating bishops
a b c d e f g h
8
Chessboard480.svg
f7 white knight
b6 white knight
c6 white knight
e6 white knight
f6 white knight
c5 white knight
f4 white knight
c3 white knight
d3 white knight
f3 white knight
g3 white knight
c2 white knight
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
12 dominating knights

The domination problems are also sometimes formulated as to find the minimal number of pieces, which attack all squares on the board, including occupied ones.[3] The solution for rooks is to place them all on one of files or ranks. The solutions for other pieces are given below.

a b c d e f g h
8
Chessboard480.svg
b7 white king
e7 white king
h7 white king
b6 white king
e6 white king
h6 white king
b3 white king
e3 white king
h3 white king
b2 white king
e2 white king
h2 white king
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
12 kings attack all squares
a b c d e f g h
8
Chessboard480.svg
g8 white queen
e6 white queen
d5 white queen
c4 white queen
a2 white queen
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
5 queens attack all squares
a b c d e f g h
8
Chessboard480.svg
b6 white bishop
d6 white bishop
e6 white bishop
g6 white bishop
c4 white bishop
d4 white bishop
e4 white bishop
f4 white bishop
c2 white bishop
f2 white bishop
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
10 bishops attacking all squares
a b c d e f g h
8
Chessboard480.svg
c7 white knight
e7 white knight
f7 white knight
c6 white knight
e6 white knight
c5 white knight
g5 white knight
c4 white knight
e4 white knight
b3 white knight
c3 white knight
e3 white knight
f3 white knight
g3 white knight
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
14 knights attacking all squares

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

Permutation problems[edit]

In permutation problems a starting position must be transformed into another.[5] This should be done by making legal chess moves, however capturing of enemy pieces is usually 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 others.

a4 black knight b4 black knight c4 black knight d4 black knight
a3 black knight b3 black knight c3 d3 black knight
a2 white knight b2 c2 white knight d2 white knight
a1 white knight b1 white knight c1 white knight d1 white knight
Knight permutation puzzle
a5 black bishop b5 black bishop c5 black bishop d5 black bishop
a4 b4 c4 d4
a3 b3 c3 d3
a2 b2 c2 d2
a1 white bishop b1 white bishop c1 white bishop d1 white bishop
Bishop permutation puzzle

Notes[edit]

  1. ^ Gik, p.11
  2. ^ Gik, p.98
  3. ^ Gik, p.101.
  4. ^ Gik, p. 87
  5. ^ Gik, p. 114.

References[edit]

See also[edit]

External links[edit]