Having 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
I'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).
Is 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.
Checking 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.
NP-hardness is about yes/no questions, and we already know thwre is an answer to all n-queens instances except 2 and 3 :)
It also can't really be #P (which is to do with hardness of counting), as that has to do with "input problem size", and N-queens with an empty grid doesn't have enough structure (as it's just a number) -- this is hard to explain in full in a short message :)
Technically the answer to the second question is "no" when n is given in binary. As a valid output is Omega(n log n) bits in length, we can't hope to construct a solution in time polynomial in the input size, i.e. time poly(log n).
However, when n is given in unary (meaning we have poly(n) time to find and output a solution), there is a 19th century German-language paper by Pauls that explicitly and efficiently constructs an n-queens solution for all n>3. So the unary version of the problem is in FP (the search version equivalent of P).
tl;dr a solution to n-queens can be found in deterministic poly(n) time.
So indeed the simpler techniques are the fastest by walltime on the solvable problems; typically shown as N=16 through N=20, or up to N=22 or N=24 if you have sufficient parallelisation available.
As you mention, it's not convincing that SAT will be faster in practice, and it's quite possible that it will not. However, if you wish to attack the upper bounds of what needs to be computed for an exact solution, then a SAT solver is no worse than these simple approaches, as in the worst case it could simply fall-back and use the simple logic as a branching heuristic, so it's all about where the gains from being smarter overtake the processing overheads.
In reality, a trivial SAT solver based on DPLL actually bears remarkable similarity to the simpler methods, and simply switching to the more straight-forward representation and weakening the propagation and heuristics brings the SAT solver inline with the fastest method. In other words, the simpler methods are a weak SAT solver that is fairly well optimised for N-Queens (at least for low N, but this includes N=27 so it's very practical).
As walltimes show, SAT has notable overhead, however if this can be shown to be close enough then this could be an avenue to solving higher N. At worst, using stronger SAT is simply a galactic algorithm that gets better "eventually" (or merely asymptotically). In practice, it may unlock more the ability to incoporate elements of the dynamic programming approach to strongly lower the time needed for larger N, bolstered by strong heuristics, finally going beyond churning through solutions as you described. Even if higher N are infeasible, it could be applicable to, say, verify the results of Q27.
I have a lot of respect for work such as proving that N-Queens Completion satisfiability is NP-complete, thank you for your contributions. The research I was involved in ended up proving a few things with regards to what SAT can achieve here, however we have not yet had the chance to publish. Hopefully some time soon.
To answer some of the people in sibling and child comments, determining Q(N), aka the number of solutions for N-Queens, is best considered from the perspective of counting the valid solutions to N-Queens Completion over an exhaustive set of starting points (in the simplest, starting with a Queen in a square on the top row), hence it is #P-complete, and full enumeration ends up NP-Hard (which refers to finding the next solution until Q(N) is determined). This is sidestepping the "empty board" concerns, and closer to the practical approach for distributed/parallel solvers. If you use the empty board then the satisfiability is linear in N and solving for Q(N) progresses upwards with exponential complexity (see Rivin and Zabih 1992 for the classic dynamic programming result, or Pratt 2016 for a similar complexity but in only polynomial space).
Unfortunately, this is one situation in which the literature is rather confusing, and "N-Queens" is used to mean anything from finding a single non-attacking board (often a challenge for AI students) to the "full" count of how many non-attacking boards (the likes of the Q27 project). There is also confusion over unary vs binary N, which in my experience has just ended up messing with people. Can't fault anyone for that. It's best if you use unary N for this, hence N is the problem size rather than lg(N). This is most consistent with literature and wider research, as only a few consider binary N. It's also what I use above.
For those wanting to learn more, see Bell and Stevens 2009, as their survey is pretty comprehensive.
J. Bell and B. Stevens, “A survey of known results and research areas for n-queens”, Discrete Mathematics, vol. 309, no. 1, 2009.
I. Rivin and R. Zabih, “A dynamic programming solution to the n-queens problem”, Information Processing Letters, vol. 41, no. 5, pp. 253–256, 1992.
K. Pratt, “Closed-Form Expressions for the n-Queens Problem and Related Problems”, 2016.
My 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.
I 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.
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.
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.
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. :)
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.
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.
Tip: 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.
One 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).
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.
Is 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.
Has 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?
Things 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.
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