5 ms·
Mathematician answers chess problem about attacking queens
- slingnow 5y agoVery cool result, and yet not one simple example of a chessboard with 8 queens in the discussed configuration. Boggles the mind.
- mcherm 5y agoGood 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 agoI 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 agoThis 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 agoMakes 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 agoYeah, 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 agoMany 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.
- NikolaeVarius 5y agoCool. Now I want to see Chess grandmasters playing a variant where every piece is a queen, save for the King.
- deleted 5y ago[deleted]
- whymauri 5y agoStockfish gives +13 for white, with forced mate in 8 if: axf7, Qf8xf7 -> mate in 8. Most other lines, white has first mover advantage leading to trades and winning endgame. The longest/best lines for black at depth 15 leads to white gaining a mate in 10 or 12 advantage.
- thom 5y agoThings appear to even out quite nicely if white gives black queen odds (specifically the one on h1). EDIT: leaving Stockfish longer has proven me wrong, sadly. Would love to know if someone can find a configuration with the maximum number of queens that settles out at a reasonably even score.
- tromp 5y agoThere's a nice bitmap based approach for enumerating n-queen placements described at https://blog.cloudboost.io/bitwise-n-queens-in-a-tweet-9251ef0e4379 https://blog.cloudboost.io/bitwise-n-queens-in-a-tweet-9251e...
- epivosism 5y agoOEIS Sequence for the n queens problem https://oeis.org/A000170 https://oeis.org/A000170
- implements 5y agoTip: If you’re trying it by hand place the first Queen in a middle column, and the next one underneath two places offset, etc - it’s much quicker than starting in a corner, and gives you a good feel for what makes finding a solution difficult.
- sir_eliah 5y agoI enjoyed this problem a lot when reading SICP book: https://billthelizard.blogspot.com/2011/06/sicp-242-243-n-queens-problem.html https://billthelizard.blogspot.com/2011/06/sicp-242-243-n-qu... Lisp'y example is as usual pretty elegant.
- babel_ 5y agoHaving done academic research into N-Queens, I'll say that this is result is a remarkable step forward and, once vetted, is generations' worth of advancement in establishing the upper and lower bounds of the problem with remarkable precision. Here's to the next few generations taking this technique and not only applying it elsewhere, but also applying it to exactly solving for higher N than 27. It'll be fascinating to see if this supersedes symmetry breaking as done with the Q27 project in allowing us to dispatch far more efficiently the reasonable starting configurations to a highly parallelised #SAT solver, and allows us to come up with branching heuristics that are actually viable (as the research I was involved with showed most simply added overhead and little benefit for an overall negative effect). Edit: here's the arxiv so you can read the actual results, since Quanta makes it surprisingly awkward to look for. https://arxiv.org/abs/2107.13460 https://arxiv.org/abs/2107.13460
- CJefferson 5y agoI'm not convinced a SAT solver will ever be that useful in practice, as finding (huge!) numbers of solutions to N-queens tends to be easy -- so a simpler (specialised) technique will usually churn through solutions faster. While it is true that completing a solution to N-queens is NP-complete (I was an author on the paper that proved that), you need fairly big instances before the problem gets "hard" in practice (at least, as far as we showed).
- kevinwang 5y agoIs counting the number of solutions for a given n known to be NP-hard? And is finding any solution for a given n known to be in P? I saw a paper that found solutions up to 500,000 using a probabilistic method but wasn't sure if it was definitively proven to be in P or not.
- CJefferson 5y agoChecking if a partially filled in n-queens problem has a solution at all is NP complete. It might be there is an easy way of counting solutions for an empty grid, but usually the way we count solutions is divide and conquer, by giving different computers partially filled in grids.
- jedberg 5y agoMy first introduction to the n-Queens problem was the game The 7th Guest. One of the mini-games was placing eight queens on the board, but they didn't tell you what you had to do. They just gave you a board and eight queens to place. As you placed one, any others that you had placed that were now in danger would disappear. Eventually you figured out that you had to get all eight on there. My friend and I spent about an hour trying to figure it out when we were 16 or so. He's a mathematician studying elliptic curves now.
- showerst 5y agoDespite being just a kid I specifically remember this puzzle too, and talking about how cool it was with others at the time.
- mrkramer 5y agoGod save the Queen!
- frogpelt 5y agoOh no my queen!
- mehrzad 5y agoFeeling slightly peeved that they call a square a space.
- exdsq 5y agoAphyr solved this in an interview with types years ago https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview
- nixpulvis 5y agoI quick re-skim of this leads me to believe the OP solution would be considerably faster and more tractable for large N. That said, it doesn't appear to be an exact solution, as a classical recursive enumeration would be. I was personally really hoping to learn about a new geometric trick to exploit for a complete solution. I even took out a chess set again and everything, lol. Or am I misunderstanding something here?
- exdsq 5y agoSorry I was being sarcastic, it's the same N-Queens problem but just done in a really really obscure way along with a great story.
- paulpauper 5y agoI wish this went into more detail about how it was proved.
- dane-pgp 5y agoIs there a name for the problem of trying to place as many queens on a chess board as possible without checking (or stalemating) the opposing king? The number is more than 9, which is the most a player could have in a normal game, so it's even less relevant to the game of chess than the N-queens problem, but it seems like the problems might be related.
- kadoban 5y agoOne thing I find cool about n-queens: there's actually a _much_ better algorithm for finding arbitrary valid n-queens arrangements than the well-known backtracking one. You can find answers up to arbitrarily huge boards, into the millions. (backtracking gets impractical not a lot after the traditional 8). http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4685 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.46... This paper describes it. Tl;dr though: randomly place queens such that none are on the same row or column, then do kind of a gradient search swapping the rows (but not columns) of queens that reduce the number of conflicts the most.
- galaxyLogic 5y agoHas anyone tried a game where each player starts with 8 queens and start by taking turns placing their queens on the board in unfilled positions, after which normal chess-rules apply?