5 ms·

Very cool result, and yet not one simple example of a chessboard with 8 queens in the discussed configuration. Boggles the mind.

mcherm 5y ago
Good point. Anyone reading these comments and wondering about it should check out https://en.wikipedia.org/wiki/Eight_queens_puzzle https://en.wikipedia.org/wiki/Eight_queens_puzzle .
taeric 5y ago
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.
- babel_ 5y ago
  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.
  - taeric 5y ago
    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 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. :)
  - noneeeed 5y ago
    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.
ableal 5y ago
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.

mcherm 5y ago

Good point. Anyone reading these comments and wondering about it should check out https://en.wikipedia.org/wiki/Eight_queens_puzzle https://en.wikipedia.org/wiki/Eight_queens_puzzle .

taeric 5y ago

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.

babel_ 5y ago
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.
- taeric 5y ago
  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 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. :)
- noneeeed 5y ago
  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.

ableal 5y ago

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.