Observations on the n-queens problem

Posted on October 4, 2009 by Jason Dyer

One of the more (in)famous puzzles of the last 150 years is:

Given an 8 x 8 chessboard and 8 queens, how can you place the queens so they do not attack each other? (A queen stands on a single square and can attack horizontally, vertically, or diagonally any number of spaces.)

(Solutions are here.)

The question can be generalized to n queens and an n x n board. The number of solutions possible have been enumerated for up to a 25×25 board, but there is no known formula for counting the number of solutions and in recent years it’s essentially remained an algorithms problem.

However, I’ve been curious if any dents of a more combinatoric angle can be made, and I have made two observations. Likely these duplicate existing literature somewhere, but they were new to me.

I. n-queens as a double product

Suppose we number the lower left corner of the board by column and then row:

chessgrid

Hence the queen in the top row is (5,8).

When listing the placement of queens, we can simplify our notation by sorting by rows and just listing the columns the queens are in. The diagram above would be: 1, 6, 8, 3, 7, 4, 2, 5.

To be precise: represent the placement of n queens in an n x n grid with the sequence q_1, ..., q_n where the elements contain the columns, and the index of each element is same as the row. With the example above the queen in the top row would be q_8=5.

If we force our sequence to use each integer from 1 to n only once (a permutation), then clash on rows and columns are not a problem; the only time two queens threaten each other are when they are on the same diagonal.

This occurs when the difference between the rows equals the difference between the columns, that is, for some i and j (where i \neq j) from 1 to n:

\left | i-j \right | = \left | q_i-q_j \right |

alternately when

\left | i-j \right |- \left | q_i-q_j \right |= 0

This means if one multiplies all possible combinations of elements (excluding when i = j), a particular sequence q_1, ..., q_n does not form a solution when

\prod_{i, j = 1, {i \neq j}}^{n}( \left | i-j \right |- \left | q_i-q_j \right |)=0

So to find a solution for the n-queens puzzle, one needs a sequence q_1, ..., q_n that is a permutation of 1 to n such that

\prod_{i, j = 1, {i \neq j}}^{n}( \left | i-j \right |- \left | q_i-q_j \right |) \neq 0

II. n-queens solutions as a tree

Suppose one assigned a placement for the queen on the first row, followed by the second row, all the way up to the nth row. Excluding impossible configurations, here is a tree representing solving the 4 x 4 version of the n-queens problem:

nqueentree

I excluded (3,1) and (4,1) since they form symmetrical solutions with (2,1) and (1,1).

Note we can consider the depth of the nodes of this tree to be the row portion of the coordinate, so the diagram can be simplified:

nqueentree2

The solutions are shown by the nodes at a depth of n. (In this case, 1, and the symmetrical solution makes 1 more for a total of 2.)

Filed under: Mathematics |

« »

Leave a comment