Harvard mathematician answers 150-year-old chess problem
news.harvard.edu
news.harvard.edu
The problem of determining an efficient algorithm for every n, on the other hand, is just hopeless, which means that it is not interesting for the purpose I described above. Studying "small" n (up to 40, say) is not useless, though, if it leads to algorithmic breakthroughs (in SAT solving, for example). It is, however, an "orthogonal" problem, in the sense that it requires a completely different set of techniques.
To illustrate my point: If the answer for n = 50 appeared out of nowhere, would people care about the number itself? I bet people would be much more interested in how it was done.
I agree, you don't have the mentality of a mathematician.
[1] https://www.quantamagazine.org/mathematician-answers-chess-p...
Related (N-Queens is NP-hard, 4 years ago): https://news.ycombinator.com/item?id=15168867
- a mathematician
Knowing mathematics though, it's quite likely that this result is valid only for some regimes of N, for example assymptotically
We show that there exists a constant α = 1.942±3×10−3 such that Q(n) = ((1 ± o(1))ne^−α)^n
Dunno what o(1) is.
For example x^2 is in O(x^2) but is not in o(x^2).
Whenever you see big-O/little-O/theta notation there is always an implied dependent variable, even for o(1)/O(1)/Theta(1).
L(m, n) ~ A * B^{m+n} * L^{mn(1 + O(mφm))}
The paper discusses an upper bound and a lower bound, but not a singular formula.