tutORial: The N-Queens Problem

An OR/MS Perspective on the N-Queen Problem

The N-Queens problem is a well know puzzle with a simple "closed form" solution.

Why should it be of interest to the OR/MS community?

Good question!

Firstly, in all likelihood, this puzzle stands the chance of soon becoming an integral part of the OR/MS folklore. Secondly, it poses a challenge to "traditional" OR/MS.

Concerning the first point, now that constraint programming is part of OR/MS, the N-Queen problem is also part of OR/MS for it has been constraint programming's flag-ship example from the outset.

As to the challenge, well let's see:


Assignment

  1. Formulate the N-queens problem as a conventional OR/MS optimization problem.
  2. Use one of traditional OR/MS software packages to solve the problem, for say N=30 queens.

In any case, the objective of this module is just to provide you with a user-friendly facility to experiment with the basic elements of this puzzle.

Contributed by

© The University of Melbourne 1994-2000.
Disclaimer and Copyright Information.
Conditions of use.
Date created: January 15, 2000
Date last modified: February 15, 2000
Authorised by: Moshe Sniedovich
Maintained by: Moshe Sniedovich, Department of Mathematics and Statistics.
Email: m.sniedovich@ms.unimelb.edu.au