In other words, the center and side squares are distinct - and as a result, the board lacks a symmetric structure that might make the problem simpler. But if you place your first queen along the side of the board instead, it threatens only 21 spaces, since the relevant diagonals are shorter. That leaves 27 spaces off-limits for your next queen. If you put your first queen near the center, it will be able to attack any space in its row, in its column, or along two of the board’s longest diagonals. To see why, again imagine constructing your own eight-queens configuration. This stems from the fact that not all spaces on the board are created equal. “One of the things that is notable about the problem is that, at least without thinking very hard about it, there doesn’t seem to be any structure,” said Eberhard. But the n-queens problem didn’t seem to have any. In this situation, mathematicians often hope to find some underlying pattern, or structure, that lets them break up the calculations into smaller pieces that are easier to handle. On a larger board, the amount of computation involved is staggering. Even on a relatively small board, the number of potential arrangements of queens can be huge. One barrier to solving the n-queens problem is that there are no obvious ways to simplify it. “He basically did this much more sharply than anyone has previously done it,” said Sean Eberhard, a postdoctoral fellow at the University of Cambridge. Though previous researchers have used computer simulations to guess at the result Simkin found, he is the first to actually prove it. Since then, mathematicians have produced a trickle of results on n-queens. By 1869, the n-queens problem had followed. The original problem on the 8-by-8 chessboard first appeared in a German chess magazine in 1848. So, on a million-by-million board, the number of ways to arrange 1 million non-threatening queens is around 1 followed by about 5 million zeros. Simkin proved that for huge chessboards with a large number of queens, there are approximately (0.143 n) nconfigurations. “It is very easy to explain to anyone,” said Érika Roldán, a Marie Skłodowska-Curie fellow at the Technical University of Munich and the Swiss Federal Institute of Technology Lausanne. This could be 23 queens on a 23-by-23 board - or 1,000 on a 1,000-by-1,000 board, or any number of queens on a board of the corresponding size. Instead of placing eight queens on a standard 8-by-8 chessboard (where there are 92 different configurations that work), the problem asks how many ways there are to place n queens on an n-by- n board. It is the earliest version of a mathematical question called the n-queens problem whose solution Michael Simkin, a postdoctoral fellow at Harvard University’s Center of Mathematical Sciences and Applications, zeroed in on in a paper posted in July. If you succeed once, can you find a second arrangement? A third? How many are there? If you have a few chess sets at home, try the following exercise: Arrange eight queens on a board so that none of them are attacking each other.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |