Mathematical chess problem

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

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

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 it is sufficient to place them on any rank, one for each file. Solutions for other pieces are provided on diagrams below.

	a	b	c	d	e	f	g	h
8									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									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									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									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									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									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									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									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

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

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.

Knight permutation puzzle

Bishop permutation puzzle

Notes

↑ Gik, p.11
↑ Gik, p.98
↑ Gik, p.101.
↑ Gik, p. 87
↑ Gik, p. 114.

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.