Mathematical chess problem
Encyclopedia
Mathematical chess problem is a mathematical problem which is formulated using chessboard or chess pieces. These problems belong to recreational mathematics
Recreational mathematics
Recreational mathematics is an umbrella term, referring to mathematical puzzles and mathematical games.Not all problems in this field require a knowledge of advanced mathematics, and thus, recreational mathematics often attracts the curiosity of non-mathematicians, and inspires their further study...

. The most known problems of this kind are Eight queens puzzle
Eight queens puzzle
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal...

 or Knight's Tour
Knight's tour
The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...

 problems, which have connection to graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

 and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

. Many famous mathematicians studied mathematical chess problems, for example, Euler
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...

, Legendre
Adrien-Marie Legendre
Adrien-Marie Legendre was a French mathematician.The Moon crater Legendre is named after him.- Life :...

 and Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...

. 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 others. Also it is required to find a concrete piece placement for this maximum number of pieces. The most famous problem of this type is Eight queens puzzle
Eight queens puzzle
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal...

. Problems are further extended by asking how many possible solutions are 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. Solutions for kings and bishops are shown below. To get 8 independent rooks is sufficient to place them on one of main diagonals. Solution for 32 independent knights is to place them one squares of the same color (e.g. place all 32 knights on dark squares).

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 one can place them on one of main diagonals. Solutions for other pieces are provided on diagrams below.



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. The solution for rooks is to place them all on one of files or ranks. The solutions for other pieces are given below.


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
Knight's tour
The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...

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

Permutation problems

In permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 problems a starting position must be transformed into another. 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.
valign="top" |

External links

  • Chess by Weisstein, Eric W. from MathWorld
    MathWorld
    MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...

    .
  • Chess-Piece Arrangement Problems by George Jelliss (from The Games and Puzzles Journal).
  • Chessboard Tasks by Ed Pegg Jr.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK