Re:Mathematician answers chess problem about attacking queens
by taeric on Tuesday September 21, 2021 @11:54AM
(#28606344)
I would love to see runtime comparisons to put this in perspective for folks. Exact results from exhaustive search are known for values of up to 30ish, I think. And algorithms for values lower than 16ish are quite fast. Balloons quickly, though.
[ Parent
| on HN ]
Re:Mathematician answers chess problem about attacking queens
by babel_ on Tuesday September 21, 2021 @12:17PM
(#28606595)
This work only established new (remarkably exact) bounds, it was not, as the quanta article poorly describes, answering the problem in the exact sense. Their "all but solved it" is a little disingenous, as indeed it balloons quickly. Very quickly.
Exact results are only known to N=27 right now. With a single core, computing the exact result for N=16, aka Q(16), takes about 8s (using the fastest single-core method known to me). Going up to Q(17) extends that to roughly 61s, and Q(18) is over 6 and a half minutes. Q(27) took its group about a year with a large FPGA cluster.
Re:Mathematician answers chess problem about attacking queens
by taeric on Tuesday September 21, 2021 @12:41PM
(#28606869)
Makes sense. I haven't checked lately how fast the version I played with was. I do still like the visualization I put up at https://taeric.github.io/DancingLinks.html. if you run the snippet to add for n of 14, it is fun watching the queen march across the middle. :)
Re:Mathematician answers chess problem about attacking queens
by noneeeed on Tuesday September 21, 2021 @02:47PM
(#28608368)
Yeah, the description of it being "solved" was confusing to me when reading it. I was expecting them to have found some kind of exact process for generating all the valid patterns or something.
It's still great.