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; for example, 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 rectangular boards.

Contents

Independence problems

Independence problems' pictorial view 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 an 8×8 chessboard is 16, queens - 8, rooks - 8, bishops - 14, knights - 32. [2] 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
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 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 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 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

Another kind of mathematical chess problems is a domination problem (or covering). This is a special case of the vertex cover problem. 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.

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

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

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

Chess swap problems

In chess swap problems, the whites pieces swap with the black pieces. [6] 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. Gik, p.98
  3. Gik, p.101.
  4. 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
  5. Gik, p. 87
  6. "Knight swap puzzle - Chess Forums".

Related Research Articles

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.

Baroque chess is a chess variant invented in 1962 by Robert Abbott. In 1963, at the suggestion of his publisher, he changed the name to Ultima, by which name it is also known. Abbott later considered his invention flawed and suggested amendments to the rules, but these suggestions have been substantially ignored by the gaming community, which continues to play by the 1962 rules. Since the rules for Baroque were first laid down in 1962, some regional variation has arisen, causing the game to diverge from Ultima.

Queen (chess) Chess piece

The queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally or diagonally, combining the power of the rook and bishop. Each player starts the game with one queen, placed in the middle of the first rank next to the king. Because the queen is the strongest piece, a pawn is promoted to a queen in the vast majority of cases.

Chess piece Game piece for playing chess

A chess piece, or chessman, is a game piece that is placed on a chessboard to play the game of chess. It can be either white or black, and it can be one of six types: king, queen, rook, bishop, knight, or pawn.

Pawn (chess) Chess piece

The pawn is the most numerous and weakest piece in the game of chess. It may move one vacant square directly forward, it may move two vacant squares directly forward on its first move, and it may capture one square diagonally forward. Each player begins a game with eight pawns, one on each square of the 2nd rank relative to their perspective.

Chess problem A chess composition whose solution is a mate or other clear objective

A chess problem, also called a chess composition, is a puzzle set by the composer using chess pieces on a chess board, which presents the solver with a particular task. For instance, a position may be given with the instruction that White is to move first, and checkmate Black in two moves against any possible defence. A chess problem fundamentally differs from over-the-board play in that the latter involves a struggle between black and white, whereas the former involves a competition between the composer and the solver. Most positions which occur in a chess problem are 'unrealistic' in the sense that they are very unlikely to occur in over-the-board play. There is a good deal of specialized jargon used in connection with chess problems; see glossary of chess problems for a list.

This glossary of chess explains commonly used terms in chess, in alphabetical order. Some of these terms have their own pages, like fork and pin. For a list of unorthodox chess pieces, see Fairy chess piece; for a list of terms specific to chess problems, see Glossary of chess problems; for a list of named opening lines, see List of chess openings; for a list of chess-related games, see List of chess variants.

A fairy chess piece, variant chess piece, unorthodox chess piece, or heterodox chess piece is a chess piece not used in conventional chess but incorporated into certain chess variants and some chess problems. Compared to conventional pieces, fairy pieces vary mostly in the way they move, but they may also follow special rules for capturing, promotions, etc. Because of the distributed and uncoordinated nature of unorthodox chess development, the same piece can have different names, and different pieces the same name in various contexts. Most are symbolised as inverted or rotated icons of the standard pieces in diagrams, and the meanings of these "wildcards" must be defined in each context separately. Pieces invented for use in chess variants rather than problems sometimes instead have special icons designed for them, but with some exceptions, many of these are not used beyond the individual games for which they were invented.

This page explains commonly used terms in chess problems in alphabetical order. For a list of unorthodox pieces used in chess problems, see Fairy chess piece; for a list of terms used in chess is general, see Glossary of chess; for a list of chess-related games, see List of chess variants.

A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game.

Hexagonal chess Set of chess variants played on a board with hexagonal cells

Hexagonal chess refers to a group of chess variants played on boards composed of hexagon cells. The best known is Gliński's variant, played on a symmetric 91-cell hexagonal board.

Board representation (computer chess)

Board representation in computer chess is a data structure in a chess program representing the position on the chessboard and associated game state. Board representation is fundamental to all aspects of a chess program including move generation, the evaluation function, and making and unmaking moves as well as maintaining the state of the game during play. Several different board representations exist. Chess programs often utilize more than one board representation at different times, for efficiency. Execution efficiency and memory footprint are the primary factors in choosing a board representation; secondary considerations are effort required to code, test and debug the application.

Checkmate pattern Chess patterns

In chess, several checkmate patterns occur frequently enough to have acquired specific names in chess commentary. The diagrams that follow show these checkmates with White checkmating Black.

Outline of chess Overview of and topical guide to chess

The following outline is provided as an overview of and topical guide to chess:

Wolf chess Chess variant

Wolf chess is a chess variant invented by Dr. Arno von Wilpert in 1943. It is played on an 8×10 chessboard and employs several fairy pieces including wolf and fox – compound pieces popular in chess variants and known by different names.

Chesquerque Variant of chess

Chesquerque is a chess variant invented by George R. Dekle Sr. in 1986. The game is played on a board composed of four Alquerque boards combined into a square. Like Alquerque, pieces are positioned on points of intersection and make their moves along marked lines ; as such, the board comprises a 9×9 grid with 81 positions (points) that pieces can move to.

Cross chess Chess variant

Cross chess is a chess variant invented by George R. Dekle Sr. in 1982. The game is played on a board comprising 61 cross-shaped cells, with players each having an extra rook, knight, and pawn in addition to the standard number of chess pieces. Pieces move in the context of a gameboard with hexagonal cells, but Cross chess has its own definition of ranks and diagonals.

Falcon–hunter chess

Falcon–hunter chess is a chess variant invented by Karl Schultz in 1943, employing the two fairy chess pieces falcon and hunter. The game takes several forms, including variations hunter chess and decimal falcon–hunter chess added in the 1950s.

In mathematics, a queen's graph is a graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a legal move the queen can make—a horizontal, vertical or diagonal move by any number of squares. If the chessboard has dimensions , then the induced graph is called the queen's graph.

References