Eight Queens Puzzle - Related Problems

Related Problems

• Higher dimensions

Find the number of non-attacking queens that can be placed in a d-dimensional chess space of size n. More than n queens can be placed in some higher dimensions (the smallest example is four non-attacking queens in a 3 × 3 × 3 chess space), and it is in fact known that for any k, there are higher dimensions where nk queens do not suffice to attack all spaces.

• Using pieces other than queens

On an 8×8 board one can place 32 knights, or 14 bishops, 16 kings or eight rooks, so that no two pieces attack each other. Fairy chess pieces have also been substituted for queens. In the case of knights, an easy solution is to place one on each square of a given color, since they move only to the opposite color. The solution is also easy for rooks and kings. Eight rooks can be placed along a long diagonal (amongst thousands of other solutions), and 16 kings are placed on the board by dividing it into 2 by 2 squares and placing the kings at equivalent points on each square.

• Costas array

In mathematics, a Costas array can be regarded geometrically as a set of n points lying on the squares of a nxn chessboard, such that each row or column contains only one point, and that all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct. Thus, an order-n Costas array is a solution to an n-rooks puzzle.

• Nonstandard boards

Pólya studied the n queens problem on a toroidal ("donut-shaped") board and showed that there is a solution on an n×n board if and only if n is not divisible by 2 or 3. In 2009 Pearson and Pearson algorithmically populated three-dimensional boards (n×n×n) with n2 queens, and proposed that multiples of these can yield solutions for a four-dimensional version of the puzzle.

• Domination

Given an n×n board, the domination number is the minimum number of queens (or other pieces) needed to attack or occupy every square. For n=8 the queen's domination number is 5.

• Nine queens problem

Place nine queens and one pawn on an 8×8 board in such a way that queens don't attack each other. Further generalization of the problem (complete solution is currently unknown): given an n×n chess board and m > n queens, find the minimum number of pawns, so that the m queens and the pawns can be set up on the board in such a way that no two queens attack each other.

• Queens and knights problem

Place m queens and m knights on an n×n board so that no piece attacks another.

• Magic squares

In 1992, Demirörs, Rafraf, and Tanik published a method for converting some magic squares into n queens solutions, and vice versa.

• Latin squares

In an n×n matrix, place each digit 1 through n in n locations in the matrix so that no two instances of the same digit are in the same row or column.

• Exact cover

Consider a matrix with one primary column for each of the n ranks of the board, one primary column for each of the n files, and one secondary column for each of the 4n-6 nontrivial diagonals of the board. The matrix has n2 rows: one for each possible queen placement, and each row has a 1 in the columns corresponding to that square's rank, file, and diagonals and a 0 in all the other columns. Then the n queens problem is equivalent to choosing a subset of the rows of this matrix such that every primary column has a 1 in precisely one of the chosen rows and every secondary column has a 1 in at most one of the chosen rows; this is an example of a generalized exact cover problem, of which sudoku is another example.