In how many ways can chess pieces be arranged without threatening any other piece on the board? How can they be arranged so as to threaten as many squares as possible? What is fairy chess and what does all of this have to do with a million dollar prize reward?
The origin of the game of Chess is unknown, but legend has it that it was invented in India. A Chessboard consists of 64 squares, colored alternately in black and white. The game is designed for two players, one playing with white pieces and the other playing black pieces. The game of chess, its board and pieces, serve to this day, as a perfect setting for puzzles and problems in the fields of mathematics and computer science.
The Eight Queens puzzle is an example of a classic puzzle that is based on a chessboard and uses the rules of movement of the queen. In order to solve the puzzle it is necessary to place eight chess queens on a chessboard in such a manner that no pair of two queens threaten each other. In other words, two queens cannot share the same row, column or diagonal. Many mathematicians have examined this problem, amongst them the acclaimed 19th century German mathematician, Carl Friedrich Gauss. In 1874, the mathematician and astronomer James Whitbread Lee Glaisher proved that this puzzle has only 12 basic solutions.
One out of the 12 existing solutions for the Eight Queens puzzle | Illustration: Dr. Yossi Elran
Similar to many other cases, the eight queens puzzle was merely the opening shot for a flood of similar related puzzles. In how many ways can five queens be placed on a five-by-five board, so as not to threaten each other? Or, more generally, in how many ways can n queens be placed on an nXn board? Another extension of the puzzle involves placement of other chess pieces so that they do not threaten each other. For example, place eight rooks on a chessboard, without any of them threatening any other. Similar puzzles can be solved with 14 bishops or 16 kings. In 2004, the computer scientist Roger Hui published a proof that the smallest total number of queens and knights that can be placed on a chessboard without threatening each other is five queens and five knights, having found 16 different solutions for this puzzle.
Other puzzles present the reverse challenge of placing the smallest possible amount of pieces, such that they threaten all the squares on the board.
The eight queens puzzle and its various extensions represent classic problems in computer science and are used, among other things, for the testing of new algorithms developed by scientists. Why has this puzzle gained such wide publicity? Mainly due to the cultural background out of which it developed. The 19th century, pre-computer age, was characterized by a boom of puzzles and riddles based on common games, such as playing cards and chess. These games were the perfect settings for the classical books 'Alice's Adventures in Wonderland' and ‘Through the Looking-Glass’ written by mathematician Charles Dodgson, better known by his pen name Lewis Carroll, which were published at the time. The riddles that appeared around these games were notable for being easy and simple to phrase, but difficult to solve. These puzzles were discussed not only within the walls of academia, but also in European salons, gaining widespread popularity.
The grand prize
Academic interest in the eight queens puzzle has grown since, mainly due to the fact that a linear extension of the board (by constant multiplication) makes the difficulty of finding all possible computerized solutions grow exponentially (by orders of magnitude).
For example, the time required to solve a puzzle for a 100 square board is roughly 33 times the time required for a board nearly half that size (49 squares), whereas the time required to solve a puzzle for a board approximately twice that size (196 squares) is 657 times longer! With the maximum computing power available today, all of the solutions for a 28x28 board have not been found yet. The time required for solving this puzzle using a powerful computer is currently estimated to be 2000 years!
A problem in which the difficulty of the solution grows exponentially while the settings change linearly, is termed an NP-Complete problem (this definition is not entirely accurate and is used here only for clarity and readability). Optimization of the solution of NP-Complete problems currently represents one of the main goals in computer science. Is it even possible to efficiently solve NP-Complete problems, compared to problems with a linearly growing difficulty of solution? This remains an open question and represents one of the seven Millennium Problems in mathematics. No one has been able to solve this problem to date, and whoever does solve it will win a $ 1 million dollar reward from the Clay Mathematics Institute (CMI).
The oddest piece in the game. The squares to which the knight can move to are marked by x | Illustration Dr. Yossi Elran
Horsing around
Another connection between mathematics and chess deals with the oddest piece in the game - the knight. The knight can skip over other pieces and can, in a single journey, move to one out of eight squares that are one square away in one direction (either horizontal or vertical) and then to two squares in the perpendicular direction.
The Knight’s tour problem consists of the following question: is it possible for the knight to move through all of the squares on a board while landing on each square only once? This is a very ancient problem, which was first mentioned by the Arab Chess player Al Adli ar Rumi in 840 AD. In his book, “Kitab ash-shatranj” (“Book of Chess”), Al Adli presents two possible solutions for this problem.
Many mathematicians have tried their hands at solving this problem, only to find that it has numerous solutions, although none to date has been able to find exactly how many. It was only in 1997 that Australian mathematician Brendan McKay was able to solve a slightly simpler problem, which requires that during his final move the knight will land on the original square from which he began his journey. McKay found that in this case the problem has no less than 1,658,420,855,433 possible solutions (not counting symmetric solutions). Interestingly, McKay originally became famous for being one of the statisticians to mathematically refute the claims made by Michael Drosnin, author of the book “The Bible Code”, which states that clues of historic events are encoded in the Hebrew Bible.
Mathematicians have proposed many and diverse methods for finding different possible knight routes. One of the first to do so was the mathematician and chess player Heinrich Christian von-Warnsdorf, in the 19th century. According to his method, in each move, the knight should advance to the square that requires the least number of possible squares to advance to.
One of the possible solutions for the ‘Knight’s tour’ puzzle | Source: Tobias Pfanner, Wikipedia, common knowledge,
Fairies and Camels
The world of chess also includes games that extend the original game to new directions.
For example, Janggi Chess is a Korean version of the game with slightly different rules. Alice Chess - is a version that is played on two boards. Fairy Chess is played with additional new pieces, some ancient and some modern inventions. An example for such a piece is the Archbishop, also known as Princess or Cardinal. It is a combination of a Bishop and a Knight and in each move the player can choose whether to move it as a Bishop or as a Knight. The Camel is a piece that moves like an elongated Knight - it moves one square in one direction (horizontal or vertical) and three more squares in a perpendicular direction (jumping 1,3 instead of 1,2 like the Knight).
The number of mathematical problems that are based on a chessboard and its pieces is immense. Due to space considerations we could only bring a small taste of the immense wealth that exists in this field. However, you are welcome to add your puzzles in the comment section…