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.)
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:
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 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 .
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 ) from 1 to n:
This means if one multiplies all possible combinations of elements (excluding when i = j), a particular sequence does not form a solution when
So to find a solution for the n-queens puzzle, one needs a sequence that is a permutation of 1 to n such that
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:
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:
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 |