Quanta has an article “Mathematician Answers Chess Problem About Attacking Queens“. I thought at first that the headline was a bit strange as we in Constraint Programming, and others, have been solving the n-Queens problem for many years now: how to place n queen chess pieces on an nxn board such that they don’t attack each other. However, the headline is referring not to the problem of finding solutions per se, but to the question of how many solutions there are for any n, for which there has not been any precise answer (other than finding them all). Michael Simkin of Harvard hasn’t actually found a precise answer either, but he has apparently made good progress on narrowing it down. According to the Quanta article “Simkin proved that for huge chessboards with a large number of queens, there are approximately (0.143n)ⁿ configurations”.

This also reminded me that there are ways of constructing solutions for the n-Queens problem without search, e.g. Constructions for the Solution of the m Queens Problem, which I conveniently ignore because the problem of searching for a solution has been so useful for both teaching and research in CP. More generally, one can go down quite a rabbit hole with the n-Queens problem, not surprising for a problem that was first published, as the 8-Queens problem, in 1848, and studied by Gauss. There is an n-Queens bibliography online with 336 entries.

Abstracting methods developed for a specific application is, of course, a good “meta-heuristic” for seeking new, more general methods for Constraint Programming. For well-studied problems like n-Queens or graph coloring, I suspect that there is a good deal that is still lurking in the older literature, or appearing in new publications, that could be mined to advance CP.