Scholarship

n-Queens Completion is NP-Complete

Update, 2021

Over the years since we published this research, many people have approached us having solved the n queens puzzle, either for one n like 8 or 1000, or having written an algorithm to solve it for different sizes.  Unfortunately this is not a major result in Computer Science and does not make one eligible to claim the $1M Clay prize. Many have been disappointed by this so we want to clarify why  this is the case. 

It is true that work on this problem could potentially result in the award but only if some exceptionally difficult conditions are met.

  • EITHER prove mathematically that NO possible algorithm could solve the n queens completion problem in polynomial time;
  • OR prove that there is an algorithm which is guaranteed to solve every instance of the n queens completion problem in polynomial time. Note that in this case the algorithm has to work on the completion version of the problem studied in our paper, not placing queens on an empty board; the algorithm has to give the correct answer on every possible instance given to it; and there has to be a mathematical proof that the algorithm’s runtime is bounded above by some polynomial in the size of the board.  However fast a given algorithm runs when tested, this is not sufficient because there are an infinite number of possible tests available, so a mathematical proof is required.
  • AND in either case, prove this at a level that is published in a respected academic source and is widely accepted by research experts as correct.

We are delighted that our work has led so many people to be interested in the problem of solving problems like the n queens puzzle that fascinates us.  But we also apologise for any impression we gave, unintentionally, that a solution to the n queens puzzle could lead to the award of the prize except under the extremely strenuous conditions listed above.

Ian Gent, 10 May 2021

Original Post from 2017:

Ian Gent, Christopher Jefferson and Peter Nightingale have shown that a classic chess puzzle is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30, 2017.

The n-Queens puzzle is a classic chess problem: given a chessboard of size n by n, can you place n queens so that no two queens attack each other?  That is, can you place the queens with no two queens are on the same row, column, or diagonal? The n-Queens puzzle has long been known to be simple to solve:  you can solve the problem for all n except 2 and 3, and solutions for all other n can be described in a few lines.  This very simplicity has led to repeated

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 2017

controversy in Artificial Intelligence (AI). The n-Queens puzzle is often used as a benchmark problem, but good results on the problem can always be challenged because the problem is so simple to solve without using AI methods.

The new work follows a challenge on Facebook on New Year’s Day, 2015, when a friend of Ian’s asked him how hard n-Queens is if some queens were already placed on the board.  It turns out, this version (dating from 1850) of the puzzle is only two years younger than the more famous n-Queens problem. The picture shows Peter (left) and Ian (right) with queens on the board at positions suggested by Nauck in 1850, the squares b4 and d5.  Can you put another 6 queens on the board so that the entire board is a solution of 8-Queens?  The general version with some number of queens preplaced on an n by n board is the n-Queens Completion puzzle.

 

With queens at b4 and d5, can you place 6 more queens to get a solution to the 8-queens puzzle? ©Stuart Nicol Photography, 2017

Ian, Christopher and Peter have shown that the n-Queens puzzle is in fact hard, not simple.  It belongs to the complexity classes NP-Complete and #P-Complete. Other NP-Complete problems include the “travelling salesperson problem”, finding cliques in graphs, and many other important problems, from scheduling to circuit layout. This puts n-Queens Completion at the centre of the most important theoretical problem in computer science — it has long been known that either all NP-complete problems are easy, or none of them are. Most computer scientists believe that this means there is no efficient algorithm possible for solving this problem, compared to the very simple techniques long known for n-Queens.
The importance of this work is that it provides researchers with a benchmark that can be used for evaluating AI techniques. Moreover, it helps to explain why so many AI techniques have been used on the n-Queens puzzle. Most techniques do most of their work with some queens partially placed, using some form of (hopefully intelligent) trial and error. In fact it turns out that many researchers – in order to solve a simple problem – have solved it by turning the simple problem of n-Queens into the hard problem of n-Queens Completion.
It does seem that AI researchers should not use n-Queens as a benchmark, but the very closely related n-Queens Completion puzzle is a valid benchmark. As well as the theoretical results, the paper shows how example instances can be generated which appear to be hard in practice. Some caution is still needed, though. It does seem to be quite hard to generate hard instances of n-Queens Completion.
The University has also issued an article on the same paper, under the title “Simple” chess puzzle holds key to $1m prize

School of Computer Science – PhD Scholarships

The School of Computer Science at the University of St Andrews offers funding for up to six students to undertake PhD research starting in the Fall of 2017 in any of the areas of research carried out by its academic faculty (which includes, but is not limited to, Artificial Intelligence and Symbolic Computation, Computer Systems Engineering, Human-Computer Interaction, and Programming Languages).

We are looking for highly motivated research students willing to be part of a diverse and supportive research community.

Applicants must hold a BSc or MSc in an area appropriate for their proposed topic of study (usually Computer Science, but not restricted to it). The Scholarship covers PhD fees and provides a tax-free maintenance stipend of £14,296 per year for 3.5 years. Exceptional students can apply for an additional £2,000 per year. International applications are welcome.

We especially encourage female applicants and underrepresented minorities to apply. Admission is competitive but candidate selection takes into account the motivation, skills and previous experience of the candidates. If you are interested, please get in contact with us by e-mail even if you are not sure of your eligibility or strength as a candidate (write an e-mail to pg-admin-cs@st-andrews.ac.uk Subject: Informal PhD Inquiry). We will facilitate contact with a member of research staff in your area of interest (for a list of existing faculty and areas of research see http://www.cs.st-andrews.ac.uk/prospective-pg/postgraduate-supervisors).

For further information, including the step-by-step procedure on how to apply please check our postgraduate-research web page (http://www.cs.st-andrews.ac.uk/prospective-pg/research-degrees). The closing date for applications is March 31st 2017 and we will make decisions on studentship allocation by April 30th 2017. Before preparing a full application we recommend that you contact us by e-mail at pg-admin-cs@st-andrews.ac.uk.

Funded PhD Research Studentships Closing Date 12th February

The School of Computer Science at the University of St Andrews has funding for students to undertake PhD research in any of the general research areas in the school:

http://www.cs.st-andrews.ac.uk/research

We are looking for highly motivated research students with an interest in these exciting research areas. Our only requirements are that the proposed research would be good, we have staff to supervise it, and that you would be good at doing it. 

We have funded studentships, including industrial sponsored studentships, available for students interested in working towards a PhD. The studentships offer costs of fees and an annual tax-free maintenance stipend of about £14,057 per year for 3.5 years. Students should normally have or expect at least an upper-2nd class Honours degree or Masters degree in Computer Science or a related discipline.

For further information on how to apply, see our postgraduate web pages (http://www.cs.st-andrews.ac.uk/prospective-pg). A non-exclusive list of potential PhD projects is provided at http://www.cs.st-andrews.ac.uk/phd-projects. The closing date for applications is February 12th 2016 and we will make decisions on studentship allocation by March 4th 2016. Informal enquiries can be directed to pg-admin-cs@st-andrews.ac.uk or to potential supervisors.

PhD Scholarship in Data Science

Potential PhD students with a strong background in Computer Science are encouraged to apply for this three-year studentship funded by the Research Council of the European Commission (ERC). The student will work within an interdisciplinary team of researchers from Computer Science and Geography in the WORKANDHOME project (ERC Starting Grant 2014), which investigates how home-based businesses are shaping society and space.

The student will examine the Computer Science challenges within this research project. The exact scope of the PhD project is open to discussion but we anticipate that the successful candidate will be working broadly on Data Science topics, potentially covering one or more of the following areas: cloud computing, social network analysis and agent-based modelling. This is a unique opportunity to work at the cutting edge of systems research. Come join us in St Andrews.

Funding Notes: The studentship will cover UK/EU tuition fees and an annual tax-free stipend of approximately £13,000. Funding will be for three years of full-time study, starting asap.

Applications: It is expected that applicants should have or expect to obtain a UK first-class honours degree (or its equivalent from non-UK institutions) in Computer Science but the minimal standard that we will consider is a UK upper-second class Honours degree or its equivalent.

For further information on how to apply, see our postgraduate web pages. All interested candidates should contact Dr Adam Barker in the first instance to discuss your eligibility for the scholarship and a proposal for research.

PhD Scholarship in Data Science

Potential PhD students with a strong background in Computer Science are encouraged to apply for this three-year studentship funded by the Research Council of the European Commission (ERC). The student will work within an interdisciplinary team of researchers from Computer Science and Geography in the WORKANDHOME project (ERC Starting Grant 2014), which investigates how home-based businesses are shaping society and space.

The student will examine the Computer Science challenges within this research project. The exact scope of the PhD project is open to discussion but we anticipate that the successful candidate will be working broadly on Data Science topics, potentially covering one or more of the following areas: cloud computing, social network analysis and agent-based modelling. This is a unique opportunity to work at the cutting edge of systems research. Come join us in St Andrews.

Funding Notes: The studentship will cover UK/EU tuition fees and an annual tax-free stipend of approximately £13,000. Funding will be for three years of full-time study, starting date ideally in September/October 2015.

Applications: It is expected that applicants should have or expect to obtain a UK first-class honours degree (or its equivalent from non-UK institutions) in Computer Science but the minimal standard that we will consider is a UK upper-second class Honours degree or its equivalent.

For further information on how to apply, see our postgraduate web pages. The closing date for applications is June 30th 2015. All interested candidates should contact Dr Adam Barker in the first instance to discuss your eligibility for the scholarship and a proposal for research.

Funded PhD Research Studentships

The School of Computer Science at the University of St Andrews has funding for students to undertake PhD research in any of the general research areas in the school:

http://www.cs.st-andrews.ac.uk/research

We are looking for highly motivated research students with an interest in these exciting research areas Our only requirements are that the proposed research would be good, we have staff to supervise it, and that you would be good at doing it. 

We have up to 6 funded studentships, including industrial sponsored studentships, available for students interested in working towards a PhD. The studentships offer costs of fees and an annual tax-free maintenance stipend of about £13,863 per year for 3.5 years. Exceptionally well qualified and able students may be awarded an enhanced stipend of an additional £2,000 per year. Students should normally have or expect at least an upper-2nd class Honours degree or Masters degree in Computer Science or a related discipline.

For further information on how to apply, see our postgraduate web pages (http://www.cs.st-andrews.ac.uk/prospective-pg). The closing date for applications is December 15th 2014 and we will make decisions on studentship allocation by February 27th 2015. Informal enquiries can be directed to pg-admin-cs@st-andrews.ac.uk or to potential supervisors.

Funded PhD Research Studentship in Constraint Programming

Dr Chris Jefferson at the School of Computer Science is offering funding for a student to undertake PhD research in Constraint Programming.

He is looking for a highly motivated research student with an interest in Artificial Intelligence and Algorithms. The studentship offers costs of fees for UK or EU students and an annual tax-free maintenance stipend of about £13,726 per year for 3.5 years. It might also be possible to fund non-EU students on an equivalent basis, so students of any nationality are encouraged to apply. Students should normally have or expect at least an upper-2nd class Honours degree or Masters degree in Computer Science or a related discipline.

Research topics of interest to Dr Jefferson include the automatic generation of propagation algorithms (http://caj.host.cs.st-andrews.ac.uk/pubs/statelessprop.pdf), the automated creation of combinatorial puzzles (http://caj.host.cs.st-andrews.ac.uk/pubs/combination.pdf), or advances in Computational Group Theory. Dr Jefferson is also interested in any student suggested projects in the area of Constraint Programming.

For further information on how to apply, see our postgraduate web pages (http://www.cs.st-andrews.ac.uk/prospective-pg).

Candidates should address general queries to pg-admin-cs@st-andrews.ac.uk, or specific queries on the research topics to caj21@st-andrews.ac.uk. The application process will require an interview (by phone or voice-conference if appropriate).

The closing date for applications is June 5th 2014 and we aim to make decisions on studentship allocation by June 20th 2014.

Funded PhD Research Studentships

The School of Computer Science  has funding for students to undertake PhD research in any of the general research areas in the school:

http://www.cs.st-andrews.ac.uk/research

We are looking for highly motivated research students with an interest in these exciting research areas Our only requirements are that the proposed research would be good, we have staff to supervise it, and that you would be good at doing it. 

We have up to 8 funded studentships, including industrial sponsored studentships, available for students interested in working towards a PhD. The studentships offers costs of fees and an annual tax-free maintenance stipend of about £13,726 per year for 3.5 years. Exceptionally well qualified and able students may be awarded an enhanced stipend of an additional £2,000 per year. Students should normally have or expect at least an upper-2nd class Honours degree or Masters degree in Computer Science or a related discipline.

For further information on how to apply, see our postgraduate web pages (http://www.cs.st-andrews.ac.uk/prospective-pg). The closing date for applications is March 31st 2014 and we will make decisions on studentship allocation by May 31st 2014. (Applications after March 31st may be considered, at our discretion.) Informal enquiries can be directed to pg-admin-cs@st-andrews.ac.uk or to potential supervisors.

Dr Adam Barker Awarded Royal Society Fellowship

Dr Adam Barker has been awarded a prestigious Royal Society Industry Fellowship. The scheme aims to enhance knowledge transfer in science and technology in the UK, and provides an outstanding opportunity to demonstrate the benefits of how industry and academia can work effectively together to drive innovation.

Adam will be spending 50% of his time for two years on a collaborative project at Cloudsoft in TechCube, a world-class startup space in Edinburgh. Adam will be working on multi-cloud application management with Dr Alex Heneveld, Co-Founder and Chief Technology Officer (CTO) and his team. He will be contributing towards Brooklyn – an open-source, policy-driven control plane for distributed applications, and the OASIS Cloud Application Management for Platforms (CAMP) standard.

PhD Studentships – Sponsored by Time Warner Cable and Adobe

The School of Computer Science has secured support from two major companies, Time Warner Cable and Adobe, and is able to offer two fully funded PhD studentships in exciting areas of research with important applications. Both studentships are fully funded for EU applicants (covering fees, and a stipend of at least £13.5K p/a) for up to 42 months, the expected duration of the PhD. Non EU applicants may apply but may be liable for an additional approximately £11K p/a in fees.

Applicants should normally have (or expect to obtain this academic year) a 2:1 or (preferably) first class Honours Bachelors degree or equivalent in Computer Science, Computer Engineering, Software Engineering, Electrical Engineering, or a closely related topic, or a MSc (distinction preferred) in one of these subjects.

The two research topics available are:

Continue reading