Mathematician vs. Queen
The article is addressed to readers who have experience in solving problems of enumerated combinatorics, as well as those who like difficult programming problems.
It's about a battle that has been going on for more than 150 years. Mathematicians long ago started a war with chess pieces, and perhaps the most stubborn figure in this battle is the queen. The last 50 years computers have come to the aid of mathematicians, but this is not enough.
')
There are a large number of tasks associated with this very strong figure. For example, the queen dominance problem: what is the smallest number of queens that are required to keep all the board fields under control? In general, this is not about a 8 x 8 board (for which the answer is 5), but about a board of size nx n. A further generalization can be associated with the transition to three-dimensional space, where queens are placed on a cubic board (and are beaten in any of the 26 directions). But we are considering a class of problems associated with the enumeration of possible arrangements of queens.
The task of placing queens on a chessboard is perhaps one of the most well-known inaccessible problems. In one of the possible variants, it sounds as follows: in how many ways can you place n queens on a chessboard of nxn size so that they do not beat each other? This task is offered both at school in computer science lessons (for n = 8) and when applying for a job; However, for sufficiently large values ​​of the parameter n, this “exercise” is already a serious global problem.
Initially, the task was formulated as an ordinary puzzle: you need to place 8 queens on a standard 8 x 8 board so that they do not beat each other and present all such arrangements (there are, by the way, only 92). She was engaged in many famous mathematicians, including Gauss. The generalization of the problem to an arbitrary size of the board was proposed back in 1850, and the active search for algorithms for its solution began in the 1960s, that is, with the rapid development of computer technology. Using the example of this task, the work of such classical algorithmic approaches as search with return, divide and conquer method, constraint programming, etc. was demonstrated. Indeed, it is surprising: the formulation is so simple that it is understandable for a first grader, but trying to find a solution gives rise to a great many new ideas and methods.
Actually, why do we need such a task? What is the point in driving the unfortunate queens around the board, and even compete in who will do it faster for the best possible values ​​of n? In fact, in science there is a whole class of so-called “common problems”, not all of which have direct applications, but to solve them, they either pay a lot of money or try to go one step further without developing a whole scientific theory or adding to the already known section of science. So, solving the problem for n = 26, the scientists developed a number of special methods in group theory, which then were defended by several people. The decision itself of the so-called Q (26) was calculated on video cards on July 11, 2009. For more information, see the authors page (eng).
The sequence Q (n) is registered in the encyclopedia of integer sequences under the number A000170 (eng).
Attempts to solve the problem further rest on the computing power of existing machines. In principle, on a computer like Roadrunner (with a performance of more than one petaflops), you can go further, but sooner or later there will be such a value n that no supercomputer can cope with, and no one has yet been able to display the explicit formula. A strong hypothesis is considered that there is a constant C, such that the number of arrangements is a value of order n! / C n . It is believed that this constant is approximately equal to 2.54, but now, when the answer for n = 26 is known, the constant has been clarified, and it is considered to be equal to 2.48. In any case, no significant breakthrough in this direction can be expected.
For this reason, of interest is the attempt to solve a simpler problem: arrange k queens on the board nxn, where k is a fixed number independent of n. For example, when k = 1, then the number of arrangements is obviously equal to n 2 . For k = 2, the answer is n (n-1) (n-2) (3n-1) / 6. About a month and a half ago I managed to derive an explicit formula for k = 5 (for k = 3 and k = 4, the formulas were already known), however, while I simplified this formula (I wanted to do it nicely), one comrade from the Czech Republic also brought it out and published in unforced form. The response step can now only be an explicit formula for k = 6. This is the formula we are trying to bring in the competition on one of my sites. Its detailed description and current results are here . At the moment, the competition is more like a competition: who will find the answer for the greatest possible value of n. A great way to test your strength, as practice shows that almost no one gets to n = 15. Unfortunately, of course. [ Update 10.05.2010. At the moment the competition has been completed, the formula has been received ].
It is proved that when the number of queens is fixed, and the board has a variable size, the denominator of the generating function has (possibly, complex) roots equal in absolute value to one. This circumstance allows us to guess the generating function, knowing the answers for some consecutive n = 1,2,3 ... For example, for the five queens problem, I needed to count the answers to n = 38 (the denominator degree is 37). For six queens, apparently, the degree will be slightly less than 80 (follows from my empirical considerations).
There are other variants of the problem, for example, when the board is not square, but rectangular or in the shape of a torus (that is, the queen’s exit beyond the board’s boundary is equivalent to its appearance from the opposite side). Also interesting are the options when each queen beats exactly one other queen. Familiar physicists say that such problems have real physical applications, but they are unknown to me.
Many people working in industry (or in another area less related to basic research) continue to consider this kind of exercise a waste of time. It is more useful - they believe - to make a beautiful and intuitive interface, and whether it will work efficiently is a minor issue. In this case, it is not entirely correct. Solving such problems allows the scientific community to show each other their skills, the level of their scientific school, and also to demonstrate other indicators of success. And the point of this is that when a problem of a similar type that is really useful for society arises, it is usually given to solve the most advanced team of scientists in this field. On the other hand, even if this or that problem itself has no practical value, its solution allows us to develop new methods in mathematics and programming.
To understand how many-sided and important this task is, it is enough to go to the encyclopedia of integer sequences mentioned by me and type the word "Queen" in the search. You will be offered more than 250 tasks where the queen meets. Moreover, some of these tasks surprisingly echo the scientific (and not quite) problems that have nothing to do with chess.
List of sources
It's about a battle that has been going on for more than 150 years. Mathematicians long ago started a war with chess pieces, and perhaps the most stubborn figure in this battle is the queen. The last 50 years computers have come to the aid of mathematicians, but this is not enough.
')
There are a large number of tasks associated with this very strong figure. For example, the queen dominance problem: what is the smallest number of queens that are required to keep all the board fields under control? In general, this is not about a 8 x 8 board (for which the answer is 5), but about a board of size nx n. A further generalization can be associated with the transition to three-dimensional space, where queens are placed on a cubic board (and are beaten in any of the 26 directions). But we are considering a class of problems associated with the enumeration of possible arrangements of queens.
The task of placing queens on a chessboard is perhaps one of the most well-known inaccessible problems. In one of the possible variants, it sounds as follows: in how many ways can you place n queens on a chessboard of nxn size so that they do not beat each other? This task is offered both at school in computer science lessons (for n = 8) and when applying for a job; However, for sufficiently large values ​​of the parameter n, this “exercise” is already a serious global problem.
Initially, the task was formulated as an ordinary puzzle: you need to place 8 queens on a standard 8 x 8 board so that they do not beat each other and present all such arrangements (there are, by the way, only 92). She was engaged in many famous mathematicians, including Gauss. The generalization of the problem to an arbitrary size of the board was proposed back in 1850, and the active search for algorithms for its solution began in the 1960s, that is, with the rapid development of computer technology. Using the example of this task, the work of such classical algorithmic approaches as search with return, divide and conquer method, constraint programming, etc. was demonstrated. Indeed, it is surprising: the formulation is so simple that it is understandable for a first grader, but trying to find a solution gives rise to a great many new ideas and methods.
Actually, why do we need such a task? What is the point in driving the unfortunate queens around the board, and even compete in who will do it faster for the best possible values ​​of n? In fact, in science there is a whole class of so-called “common problems”, not all of which have direct applications, but to solve them, they either pay a lot of money or try to go one step further without developing a whole scientific theory or adding to the already known section of science. So, solving the problem for n = 26, the scientists developed a number of special methods in group theory, which then were defended by several people. The decision itself of the so-called Q (26) was calculated on video cards on July 11, 2009. For more information, see the authors page (eng).
The sequence Q (n) is registered in the encyclopedia of integer sequences under the number A000170 (eng).
Attempts to solve the problem further rest on the computing power of existing machines. In principle, on a computer like Roadrunner (with a performance of more than one petaflops), you can go further, but sooner or later there will be such a value n that no supercomputer can cope with, and no one has yet been able to display the explicit formula. A strong hypothesis is considered that there is a constant C, such that the number of arrangements is a value of order n! / C n . It is believed that this constant is approximately equal to 2.54, but now, when the answer for n = 26 is known, the constant has been clarified, and it is considered to be equal to 2.48. In any case, no significant breakthrough in this direction can be expected.
For this reason, of interest is the attempt to solve a simpler problem: arrange k queens on the board nxn, where k is a fixed number independent of n. For example, when k = 1, then the number of arrangements is obviously equal to n 2 . For k = 2, the answer is n (n-1) (n-2) (3n-1) / 6. About a month and a half ago I managed to derive an explicit formula for k = 5 (for k = 3 and k = 4, the formulas were already known), however, while I simplified this formula (I wanted to do it nicely), one comrade from the Czech Republic also brought it out and published in unforced form. The response step can now only be an explicit formula for k = 6. This is the formula we are trying to bring in the competition on one of my sites. Its detailed description and current results are here . At the moment, the competition is more like a competition: who will find the answer for the greatest possible value of n. A great way to test your strength, as practice shows that almost no one gets to n = 15. Unfortunately, of course. [ Update 10.05.2010. At the moment the competition has been completed, the formula has been received ].
It is proved that when the number of queens is fixed, and the board has a variable size, the denominator of the generating function has (possibly, complex) roots equal in absolute value to one. This circumstance allows us to guess the generating function, knowing the answers for some consecutive n = 1,2,3 ... For example, for the five queens problem, I needed to count the answers to n = 38 (the denominator degree is 37). For six queens, apparently, the degree will be slightly less than 80 (follows from my empirical considerations).
There are other variants of the problem, for example, when the board is not square, but rectangular or in the shape of a torus (that is, the queen’s exit beyond the board’s boundary is equivalent to its appearance from the opposite side). Also interesting are the options when each queen beats exactly one other queen. Familiar physicists say that such problems have real physical applications, but they are unknown to me.
Many people working in industry (or in another area less related to basic research) continue to consider this kind of exercise a waste of time. It is more useful - they believe - to make a beautiful and intuitive interface, and whether it will work efficiently is a minor issue. In this case, it is not entirely correct. Solving such problems allows the scientific community to show each other their skills, the level of their scientific school, and also to demonstrate other indicators of success. And the point of this is that when a problem of a similar type that is really useful for society arises, it is usually given to solve the most advanced team of scientists in this field. On the other hand, even if this or that problem itself has no practical value, its solution allows us to develop new methods in mathematics and programming.
To understand how many-sided and important this task is, it is enough to go to the encyclopedia of integer sequences mentioned by me and type the word "Queen" in the search. You will be offered more than 250 tasks where the queen meets. Moreover, some of these tasks surprisingly echo the scientific (and not quite) problems that have nothing to do with chess.
List of sources
Source: https://habr.com/ru/post/91988/
All Articles