The n queens problem is not a story about the European royalty, but a chess mathematical task. The classic question in the N-Queens-Problem is: Can you place eight queens on a chess board in such a way that none of them can beat another? And if so, how many positions of this kind exist? So that no two queens may be on the same row, line or diagonal. The color of the queens is irrelevant here.
In total there are 92 solutions for the classic 8×8 chessboard with 8 queens. These can possibly be reduced to 12, 6 or 4 basic solutions, from which the 92 solutions can be “unfolded” again by transformations. If you enlarge the chessboard (NxN) and increase the proportionate number of queens (N), the computational complexity increases drastically. For example: If N=23, the number of possible solutions is an incredible 24,233,937,684,440 (24 trillion).
If the classical n queens problem is not challenging enough for you, you might consider to look at the “Torus Problem”. Here the “chessboard” is regarded as a torus, a mathematical object from geometry (see picture). The number of possible solutions is thereby reduced many times over.
One of the clever minds dealing with the Torus Problem is Matthias Engelhardt, an employee of Lino GmbH. He has already calculated the T25, T29 and T31 values, i.e. the possible solutions for 31 queens on the hypothetical torus chessboard. He is currently working on the result for T35 and will probably set the world record for the highest solved Torus Problem again – unless a previously unknown competitor turns up and is faster!
The connection between Lino GmbH and the n queens problem can be found in the way the solution is determined. The n queens problem represents a so-called Constraint Satisfaction Problem (CSP). These CSPs are the core of all configurators, including the Tacton Configurator Engine. The task of CSPs is to find a state that fulfills all established conditions (constraints). It is common for these to be processed using a backtracking procedure.
Backtracking means: the computer tries all possible solutions and again their different branches until it finds a solution. This process is so complex and time-consuming that the n queens problem has become a benchmark, i.e. a comparative value, for the performance of computers.
Engelhardt’s project has been supported since April 2020 by Lino GmbH, which makes server capacity available during off-peak times so that results can be achieved even faster. Otherwise Engelhardt’s private computer is working on it. The search takes place in the background, it hardly interferes with normal work on the computer and can be interrupted if necessary and continued later.
Engelhardt suspects an asymptotic formula on the number of torus solutions. This formula contains several times the Stirling’s formula for n factorial. With the help of Engelhardt’s formula it is possible to predict the result for a certain number of queens approximately. It can “predict” the number of solutions up to 95% exactly: For T35, this formula yields 9.66 quadrillion.
Matthias Engelhardt has been working for Lino GmbH as Senior System Developer and Specialist since 2012. He studied mathematics at the University of Erlangen-Nuremberg and the University of Constance before working as a developer for Siemens and the IT company Tacton Systems in Stockholm, among others. Today he is a consulting expert in the Lino Team and in his spare time he deals with complex mathematical questions, mainly the n queens problem.