News for hackers. Stuff that matters.
Re:Mathematician answers chess problem about attacking queens by slingnow on Tuesday September 21, 2021 @11:10AM (#28605801)
Very cool result, and yet not one simple example of a chessboard with 8 queens in the discussed configuration. Boggles the mind.
Re:Mathematician answers chess problem about attacking queens by mcherm on Tuesday September 21, 2021 @11:27AM (#28605994)
Good point. Anyone reading these comments and wondering about it should check out https://en.wikipedia.org/wiki/Eight_queens_puzzle .
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.
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.

Re:Mathematician answers chess problem about attacking queens by ableal on Tuesday September 21, 2021 @01:58PM (#28607749)
Many moons ago I was browsing in the school library, just wandering around the stacks to see what was there, and came across a shelf of The Journal of Graph Theory, or some similarly named publication.

I picked up one sample. The cover listed a few articles, with many Hungarian-sounding names among the authors. The insides had plenty of mathematical formulas, but nary a picture of a graph - not a single one.