Harvard Mathematician Proves 150-Year Old Chess Puzzle (popularmechanics.com) 30
joshuark shares a report from Popular Mechanics: A mathematician from Harvard University has (mostly) solved a 150-year-old Queen's gambit of sorts: the delightful n queens puzzle. In newly self-published research (meaning it has not yet been peer-reviewed), Michael Simkin, a postdoctoral fellow at Harvard's Center of Mathematical Sciences and Applications, estimated the solution to the thorny math problem, which is based loosely on the rules of chess. The queen is largely understood to be the most powerful piece on the board because she can move in any direction, including diagonals. So how many queens can fit on the chess board without falling into each other's paths? The logic at play here is similar to a sudoku puzzle, dotting queens on the board so that they don't intersect.
Picture a classic chess board, which is an eight-by-eight matrix of squares. The most well-known version of the puzzle matches the board because it involves eight queens -- and there are 92 solutions in this case. But the "n queens problem" doesn't stop there; that's because its nature is asymptotic, meaning its answers approach an undefined value that reaches for the infinite. Up until now, experts have explicitly solved for all the natural numbers (the counting numbers) up to 27 queens in a 27-by-27 board. However, there is no solution for two or three, because there's no possible positioning of queens that satisfies the criteria. But what about numbers above 27?
Consider this: for eight queens, there are just 92 solutions, but for 27 queens, there are over 200 quadrillion solutions. It's easy to see how solving the problem for numbers higher than 27 becomes extremely unwieldy or even impossible without more computing power than we have at the moment. That's where Simkin's work enters the arena. His work approached the topic through a sharp mathematical estimate of the number of solutions as n increases. Ultimately, he arrived at the following formula: (0.143n)n. In other words, there are approximately (0.143n)n ways that you can place the queens so that none are attacking one another on an n-by-n chessboard.
Picture a classic chess board, which is an eight-by-eight matrix of squares. The most well-known version of the puzzle matches the board because it involves eight queens -- and there are 92 solutions in this case. But the "n queens problem" doesn't stop there; that's because its nature is asymptotic, meaning its answers approach an undefined value that reaches for the infinite. Up until now, experts have explicitly solved for all the natural numbers (the counting numbers) up to 27 queens in a 27-by-27 board. However, there is no solution for two or three, because there's no possible positioning of queens that satisfies the criteria. But what about numbers above 27?
Consider this: for eight queens, there are just 92 solutions, but for 27 queens, there are over 200 quadrillion solutions. It's easy to see how solving the problem for numbers higher than 27 becomes extremely unwieldy or even impossible without more computing power than we have at the moment. That's where Simkin's work enters the arena. His work approached the topic through a sharp mathematical estimate of the number of solutions as n increases. Ultimately, he arrived at the following formula: (0.143n)n. In other words, there are approximately (0.143n)n ways that you can place the queens so that none are attacking one another on an n-by-n chessboard.
Well.... (Score:1)
(0.143n)n (Score:4, Informative)
Re: (Score:2)
Harvard (Score:1)
Tuition is listed on their website as 51,901$ per year, I wonder how many years he worked on this (sure not full time, but lets be real, on "company" time) puzzle.
Re:Harvard (Score:4, Interesting)
The point of this isn't really just to solve a classic problem. The point is that we know the problem is a tough problem that has stumped mathematicians for many years, so any solution will likely require new techniques. So while the story is all wrapped in new progress on a classic problem, the real story is a new mathematical approach that hadn't been tried (at least in that context) before, which may have broader applications to other problems.
Oh, and the dollar sign goes before the number.
Re: (Score:1)
I never understood why anyone would use the dollar sign, or why different currencies have the same sign. — I do not know whether “$5” is 5 U.S.D., C.D. S.D., Au.D. andsoforth, so I'd rather just say that.
Why would one ever use the name of an already existing currency when explicitly shifting to a new one. When Suriname abandoned the Surinamese guilder due to hyperinflation, it switched to the Surinamese Dollar, which they could have named anything including obvious things such as the
Re:Harvard (Score:5, Interesting)
I never understood why anyone would use the dollar sign, or why different currencies have the same sign.
Currency symbols are used preceding the number in order to prevent fraud in paper ledgers. Without a preceding symbol in the ledger, it is too easy to prepend additional digits and change the ledger relatively undetectably. Use of the symbol in text is a carryover from the accounting practice.
Re: (Score:2)
I've never heard that explanation, but it makes complete sense. Thanks!
Re: (Score:2)
$5.00 -> $5,000.00
Ohhh look at me. $4,995.00 bonus.
Re: (Score:3, Interesting)
$5.00 -> $5,000.00
Generally, and certainly for USD, most if not all ledgers are right-aligned.
There is thus no space available to extend a number to the right, without it being obvious and trivially easy to detect and flag.
This is indeed the reason for placing the $ at the left, so that the numbers are constrained from both ends.
Ohhh look at me. $4,995.00 bonus.
You will have to earn your bonus the honest way.
Re: (Score:2)
Re: (Score:2)
I think some bias may be showing here. Wikipedia's list of currency symbols [wikipedia.org] shows an unaccompanied $ only for the Argentine peso and the Mexican peso, and lists the US dollar as US$.
Re: (Score:2)
If it is a simple dollar sign, it means the US dollar. All of the others should be preceded by a letter or letters (i.e,. C$ for the Canadian dollar).
Wrong. Totally wrong. If it Is a simple dollar sign, then it means what a single dollar means in your location. If you are in Hong Kong, then $100 means 100 Hong Kong dollars. If you are in Canada, then $100 means 100 Canadian dollars. If you are in the USA, bad luck. In countries where the local currency isn't "dollar" it's ambiguous and shouldn't be used.
Re: (Score:2)
It does not mean that at all. In signs in Australia “$5” is simply used to mean five Australian dollars.
I can understand such in a physical location in a country that uses the currency, but not on the internet. Newspaper articles in, say, Dutch also never use the word “dollar” without a country in front of it as it would be too ambiguous which.
Re: (Score:2)
Tuition is listed on their website as 51,901$ per year, I wonder how many years he worked on this (sure not full time, but lets be real, on "company" time) puzzle.
Not sure I see the relevance of tuition to the research. In the first-place post-doctoral fellows usually do not teach. In the second place what does what a mathematician does for research have to do the instruction of undergraduates, which is a totally separate affair.
Re: (Score:2)
He is a postdoc, so not long. Most university do not let you stay as a postdoc more than 5 years. And usually it is more like 2.
Most likely, this is funded by external grants or donations and not by tuition.
Why is it way off for n=8 ? (Score:1)
Re: (Score:1)
Re: (Score:2)
It's an asymptotic estimate. It's way off for all of the exactly known values except n=0, but the claim is about large n and 27 is still small.
Re: (Score:2)
Hmmm. I assume that the next step would be to ask if the constant can be replaced with some function of n such that it is correct for small n as well.
Re: (Score:2)
Re: (Score:2)
Have I miscalculated? For n=27 the precise value is 2.34907967154122528 x 10^17 [oeis.org], whereas (0.144 * 27)^27 = 8.367754284969007 x 10^15, so it's two orders of magnitude out rather than "good enough to quite a few decimal places".
Re: (Score:2)
Have I miscalculated? For n=27 the precise value is 2.34907967154122528 x 10^17 [oeis.org], whereas (0.144 * 27)^27 = 8.367754284969007 x 10^15, so it's two orders of magnitude out rather than "good enough to quite a few decimal places".
As ever, it's good to RTFA at https://arxiv.org/pdf/2107.134... [arxiv.org]
... 1.9449 such that as n approaches infinity ..."
The theorem states "There exists a constant 1.94
These reflect lower and upper bounds for n when n is a very large number.
27 isn't a very large number.
Re: (Score:2)
Or, to quote my first comment in this thread, "the claim is about large n and 27 is still small." You were the one who claimed that it was already a good estimate at n=22.
Re: (Score:2)
I'm not sure how that negates the point. If you're not using a constant but rather some function that mimics the underlying mechanisms that tend towards that specific constant for very large numbers of cases, you'd get as good or better estimates for precisely the same range of problems as you would by using that specific constant without knowing why. Magic numbers tend not to be magic. Either there's an underlying reason for them to be what they are, or they're only true in specific cases.
However, by repla
Harvard student (Score:1)
Solved! (Score:2)
A mathematician from Harvard University has (mostly) solved a 150-year-old Queen's gambit
He got a date with a cute nerd girl?
The Smartest Form of Dumb (Score:2)
Okay, I get that this is mathematically impressive somehow, maybe. But the most queens you can ever have on a chess board is 9 per side, or 18 total, and in order to get that, you'd pretty much have to have two players taking the piss to do it on purpose. And a chess board has 64 squares - anything with more or less is not a chess board. None of this has any practical application or artistic merit whatsoever. And you're telling me that people have been wasting time on this for 150 years?