Information on the n Queens problem

The problem is to find all ways of placing n non-taking queens on a n by n board. A queen attacks all cells in its same row, column, and either diagonal. Therefore, the objective is to place n queens on an n by n board in such a way that no two queens are on the same row, column or diagonal. Below we show a solution on a standard 8 by 8 chessboard.

The number of solutions for n = 1,2,...,15, is 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184.

This problem is an example in itself of the backtracking technique.

The n-queens problem is an old one that has been around for more than a century. Originally known as the 8-Queens problem, it has been studied by many famous mathematicians over the years, including the great German mathematician Karl Friedrich Gauss (1777-1855). The problem was generalized to n by n boards in 1850 by Franz Nauck. Since the 1960's, with rapid developments in computer science, this problem has been used as an example of backtracking algorithms, permutation generation, the divide and conquer paradigm, program development methodology, constraint satisfaction problems, integer programming, and specification.

The queens problem is really a puzzle but, surprisingly, there are some practical applications such as parallel memory storage schemes, VLSI testing, traffic control, and deadlock prevention. The problem is also illustrative of more practical problems whose solutions are permutations, of which there are many. One such problem is the travelling salesperson problem: Find the shortest route on a map that visits each city exactly once and returns to the starting city. Here the permutation is the list of cities that are visited, except for the first.

Furthermore, the solution technique, backtracking is very important, and is best learnt on simple examples such as the queens problem.

There is just one input choice which has already been selected for you. Specify n, the number of queens to be placed on the chessboard. At most 9 queens are allowed. Two output options are available: permutation and chessboard. You may set the number of solutions that are output. At most 200 (the default) are allowed in the case of permutation output. In the case of chessboard output at most 10 solutions are allowed; you can specify more than 10, but only 10 will be output.

The algorithm used by AMOF to solve the n-queens problem is well-known and found in many programming texts. The general technique used is called backtracking, the same technique used by AMOF to solve pentomino puzzles.

The n-queens problem can be used to teach problem solving skills to students at all grade levels.

A useful manipulative for the queens problem is a chessboard. The pawns can be used to represent the eight queens. Try to produce a solution on your own; it's not as easy as you might think! For younger students try a simpler example by drawing a 4 by 4 grid and use 4 coins for the queens.