CIRCA

News

n-Queens Completion is NP-Complete


Ian Gent, Chris Jefferson and Peter Nightingale have shown that the n-Queens puzzle (given a chessboard of size n x n, place n queens so that no two queens attack each other) is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30. See these two articles: “Simple” chess puzzle holds key to $1m prize and n-Queens Completion is NP-Complete for further details.

Notes on Counting


Peter Cameron’s book “Notes on Counting: An Introduction to Enumerative Combinatorics” should be published by Cambridge University Press in June 2017, as part of the Australian Mathematical Society Lecture Series. For further details, see Peter Cameron’s blog.