April 26, 2010 at 07:28Mathematician vs. Queen
The article is addressed to readers who are experienced in solving enumerator combinatorics, as well as those who like difficult programming tasks.
It's about a battle that has been going on for more than 150 years. Mathematicians have long started a war with chess pieces, and perhaps the queen is the most stubborn figure in this battle. Over the past 50 years, computers have come to the aid of mathematicians, but even this is not enough.
There are a large number of tasks associated with this most powerful figure. For example, the problem of queens dominance: what is the smallest number of queens that are required for them to control all the board's fields? In the general case, this is not about an 8 x 8 board (for which the answer is 5), but about a board of size nx n. Further generalization may be associated with the transition to three-dimensional space, where queens are placed on a cubic board (and beat in any of 26 directions). But we are considering a class of problems associated with listing the possible arrangements of queens.
The problem of placing queens on a chessboard is perhaps one of the most well-known difficult problems. In one of the possible variants, it sounds as follows: in how many ways can n queens be placed on a chessboard of size nxn so that they do not beat each other? This task is offered at the school in computer science lessons (for n = 8) and at employment; however, for sufficiently large values of the parameter n, this “exercise” is already a serious global problem.
Initially, the task was formulated as a regular 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 (by the way, there are 92 of them). She was engaged in many famous mathematicians, including Gauss. A generalization of the problem to an arbitrary board size was proposed back in 1850, and an active search for algorithms to solve it began in the 1960s, that is, with the rapid development of computer technology. Using the example of this problem, the work of such classical algorithmic approaches as return search, divide and conquer method, constraint programming, etc. was demonstrated. And the truth is surprising: the wording is so simple that even a first grader understands it, but trying to find a solution gives rise to a huge number of new ideas and methods.
Actually, why is such a task needed? What is the point to drive the unfortunate of queens on the board, and even compete to see who will make it possible for B on lshih values of n? In fact, there is a whole class of so-called “common problems” in science, not all of which have direct applications, but either they pay a lot of money to solve them, or trying to advance at least one step is impossible without developing a whole scientific theory or supplementing the already known section of science. So, solving the problem for n = 26, scientists developed a number of special methods in group theory, on which several people then defended their dissertations. The very solution of the so-called Q (26) was calculated on video cards on July 11, 2009. This is described in more detail on the authors page .
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 move forward, but sooner or later there will be a value n that no supercomputer can handle, and no one has yet been able to derive an explicit formula. We consider the strong hypothesis that there exists a constant C such that the number of arrangements is a quantity of order n! / C n. It is believed that this constant is approximately equal to 2.54, but now that the answer for n = 26 is known, the constant has been refined, and it is considered equal to 2.48. In any case, a significant breakthrough in this direction is not yet expected.
For this reason, it is of interest to try to solve a simpler problem: place 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 n 2. For k = 2, the answer is n (n-1) (n-2) (3n-1) / 6. About a month and a half ago, I was able 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 make it beautiful), one comrade from the Czech Republic also derived and published it in an un simplified form. The response step now can only be an explicit formula for k = 6. This is the formula we are trying to derive as part of 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 largest 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 as of May 10, 2010. At the moment, the competition is completed, the formula is received ].
It is proved that when the number of queens is fixed, and the board has a variable size, then the denominator of the generating function has (possibly complex) roots equal in absolute value to unity. This circumstance allows us to guess the generating function, knowing the answers for some successive n = 1,2,3 ... For example, for the five queens problem, I needed to count the answers to n = 38 (the denominator 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 border is equivalent to appearing from the opposite side). Also interesting are the options when each queen beats exactly one other queen. Familiar physicists claim 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 say, to make a beautiful and intuitive interface, and whether this will work efficiently is a secondary issue. In this case, this is not entirely correct. Solving such problems allows the scientific communities to show each other their skills, the level of their scientific school, as well as demonstrate other indicators of success. And the meaning of this is that when a problem of a similar type is genuinely useful for society, it is usually given to solve the most advanced team of scientists in this field. On the other hand, even if this or that task in itself has no practical value,
To understand how diverse and important this task is, just go to the encyclopedia of integer sequences I mentioned above 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 overlap with 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 have long started a war with chess pieces, and perhaps the queen is the most stubborn figure in this battle. Over the past 50 years, computers have come to the aid of mathematicians, but even this is not enough.
There are a large number of tasks associated with this most powerful figure. For example, the problem of queens dominance: what is the smallest number of queens that are required for them to control all the board's fields? In the general case, this is not about an 8 x 8 board (for which the answer is 5), but about a board of size nx n. Further generalization may be associated with the transition to three-dimensional space, where queens are placed on a cubic board (and beat in any of 26 directions). But we are considering a class of problems associated with listing the possible arrangements of queens.
The problem of placing queens on a chessboard is perhaps one of the most well-known difficult problems. In one of the possible variants, it sounds as follows: in how many ways can n queens be placed on a chessboard of size nxn so that they do not beat each other? This task is offered at the school in computer science lessons (for n = 8) and at employment; however, for sufficiently large values of the parameter n, this “exercise” is already a serious global problem.
Initially, the task was formulated as a regular 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 (by the way, there are 92 of them). She was engaged in many famous mathematicians, including Gauss. A generalization of the problem to an arbitrary board size was proposed back in 1850, and an active search for algorithms to solve it began in the 1960s, that is, with the rapid development of computer technology. Using the example of this problem, the work of such classical algorithmic approaches as return search, divide and conquer method, constraint programming, etc. was demonstrated. And the truth is surprising: the wording is so simple that even a first grader understands it, but trying to find a solution gives rise to a huge number of new ideas and methods.
Actually, why is such a task needed? What is the point to drive the unfortunate of queens on the board, and even compete to see who will make it possible for B on lshih values of n? In fact, there is a whole class of so-called “common problems” in science, not all of which have direct applications, but either they pay a lot of money to solve them, or trying to advance at least one step is impossible without developing a whole scientific theory or supplementing the already known section of science. So, solving the problem for n = 26, scientists developed a number of special methods in group theory, on which several people then defended their dissertations. The very solution of the so-called Q (26) was calculated on video cards on July 11, 2009. This is described in more detail on the authors page .
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 move forward, but sooner or later there will be a value n that no supercomputer can handle, and no one has yet been able to derive an explicit formula. We consider the strong hypothesis that there exists a constant C such that the number of arrangements is a quantity of order n! / C n. It is believed that this constant is approximately equal to 2.54, but now that the answer for n = 26 is known, the constant has been refined, and it is considered equal to 2.48. In any case, a significant breakthrough in this direction is not yet expected.
For this reason, it is of interest to try to solve a simpler problem: place 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 n 2. For k = 2, the answer is n (n-1) (n-2) (3n-1) / 6. About a month and a half ago, I was able 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 make it beautiful), one comrade from the Czech Republic also derived and published it in an un simplified form. The response step now can only be an explicit formula for k = 6. This is the formula we are trying to derive as part of 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 largest 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 as of May 10, 2010. At the moment, the competition is completed, the formula is received ].
It is proved that when the number of queens is fixed, and the board has a variable size, then the denominator of the generating function has (possibly complex) roots equal in absolute value to unity. This circumstance allows us to guess the generating function, knowing the answers for some successive n = 1,2,3 ... For example, for the five queens problem, I needed to count the answers to n = 38 (the denominator 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 border is equivalent to appearing from the opposite side). Also interesting are the options when each queen beats exactly one other queen. Familiar physicists claim 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 say, to make a beautiful and intuitive interface, and whether this will work efficiently is a secondary issue. In this case, this is not entirely correct. Solving such problems allows the scientific communities to show each other their skills, the level of their scientific school, as well as demonstrate other indicators of success. And the meaning of this is that when a problem of a similar type is genuinely useful for society, it is usually given to solve the most advanced team of scientists in this field. On the other hand, even if this or that task in itself has no practical value,
To understand how diverse and important this task is, just go to the encyclopedia of integer sequences I mentioned above 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 overlap with scientific (and not quite) problems that have nothing to do with chess.
List of sources