Eight queens puzzle

The eight queens puzzle is the problem of putting eight chess queenss on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. (Piece colour is ignored, and any piece is assumed to be able to attack any other.) That is to say, no two queens should share the same row, column, or diagonal.

Table of contents

1 History 2 Solutions 3 Related problems 4 The eight queens puzzle as an example problem for algorithm design 5 Example program in Python 6 See also 7 External links 7.1 Links to solutions

History

Over the years, many mathematicians, including Gauss have worked on this puzzle, which is a special case of the generalized problem of placing n "non-dominating" queens on an n by n chessboard, posed as early as 1850 by Franz Nauck. In 1874, S. Gunther proposed a method of finding solutions by using determinants, and J.W.L. Glaisher refined this approach.

This puzzle was used in the popular early 1990s computer game, The 7th Guest.

Solutions

The eight queens problem has 92 distinct solutions, or 12 distinct solutions if symmetry operationss such as rotations and reflections of the board are taken into consideration (via Burnside's lemma.)

Related problems

• Nine queens problem

Setup nine queens and one pawn on 8x8 board in such a way, that queens don't attack each others. Further generalization of the problem (solution is currently unknown): Given NxN chess board and M>N queens. Find the minimum number of pawns, so that queens and pawns can be setup on the board in such a way, that queens don't attack each other.

• Integer sequence

Paul Muljadi showed that if all 64 squares of the chess board are numbered consecutively from 1 to 64, all 92 distinct solutions can be represented by 92 integer sequences, where each queen placement represents a term.

For example, in the above diagram, the integer sequence is