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.

Peter Cameron awarded the 2017 LMS Senior Whitehead Prize


Congratulations to Peter Cameron on being awarded the 2017 Senior Whitehead Prize of the London Mathematical Society! The prize is awarded for ‘exceptional research contributions across combinatorics and group theory, his fertile imagination and encouragement of others having sparked activity in many fields’. He became the third person to win both a Junior and Senior Whitehead Prize. Please read further details in the LMS announcement and in this post in Peter Cameron’s blog.