Eight Queens Puzzle

The \(n\) Queens Puzzle asks in how many ways \(n\) queens can be placed on a \(n\times n\) chessboard such that they do not threaten each other. The sequence is also listed in the Online Encyclopedia of Integer Sequences. We are going to write a recursive procedure in Maple to do the counting for us.

The main idea is to place one queen at a time somewhere on the board where no other pieces can attack her. If this s possible, then we might find a solution. Else, we need to find a different place for the previous queen.

With this basic method there are \(n^2\) possibilities for placing each queen. We reduce this number (and obtain a more efficient representation of our data) by observing that there can only be one queen in each column of the board. (Two queens on the same column would threaten each other.) With this in mind, we will always place the first queen in the first column, the second queen in the second column and so on.

We will use a vector \(v\) of length \(n\) to represent our board. If \(v_j = i\), then this means that there is a queen in the \(j\)-th column and \(i\)-th row. We will also keep a counter on how many columns are already successfully filled (ie, how many queens are already successfully placed).

The main procedure is simply called Queens and has as its only input the size \(n\) of the board. It calls the loopQueens procedure which will do the actual work; passing it the parameter \(n\), the information that we need to place a queen in column \(1\), and an empty board.

Queens := n -> loopQueens(n, 1, Vector(n, 1)):

The loopQueens procedure does the actual counting. Its parameters are the size \(n\) of the board, the column in which we currently need to put a queen, and a (partially filled) board. It computes in how many ways we can complete the board; that is, in how many ways we can place queens in the remaining columns \(i,\ldots,n\) without any two threatening each other. (We can assume that the configuration on the partially filled board is valid.)

If \(i > n\), then we must already have filled up all the columns. Thus, we have found exactly one valid configuration, and we simply return that number.

Otherwise, we try to place a queen in the \(i\)-th column. For this, we consider all possible rows \(a = 1,\ldots,n\). If a queen can be placed in the \(i\)-th column and \(a\)-th row, then we might be able to eventually find valid configurations. In that case, we apply the procedure loopQueens recursively with the altered board and asking it to fill the remaining columns. We also increase the solution counter \(s\) by the number of solutions found during the recursive call. Else, if the queen cannot go in row \(a\), then we do not change the solution counter \(s\). Initially, the solution counter is simply set to \(0\).

Instead of writing the method that we just described out as a loop, we are using Maple's foldl function.

loopQueens := proc(n :: posint, i :: posint, board :: Vector(posint)) :: integer:
    if i > n then
        1
    else
        foldl(proc(s,a)
                  if safeAdding(i, a, board) then
                      s + loopQueens(n, i+1, addQueen(i, a, board))
                  else
                      s
                  end if
              end proc,
              0, $1..n)
    end if:
end proc:

In order to complete the implementation, we need to define a few utility functions. The first function simply changes the board by placing a queen at the given spot.

(A short function like this could also be directly embedded into the larger procedure loopQueens; however, it often increases the readability of an implementation to use functions with easily understandable names instead.)

addQueen := proc(i :: posint, j :: posint, board :: Vector(posint))
    :: Vector(posint):
    board[i] := j:
    board
end proc:

The second utility function tests whether a queen can be safely placed at column \(i\) and row \(j\) on a given, partially filled board.

The assumption here is, that the board is already filled in a valid way up to the \((i-1)\)-th column. Thus, we simply need to check whether the new queen makes the configuration invalid or not. We already know, that there cannot be another queen in the same column due to our way of representing the board. We still need to check rows and diagonals.

We consider the columns \(s = 1,\ldots,i-1\) on after the other. Assume that in column \(s\) there is a queen on row \(t\). Then the new queen cannot be in the same row (ie, we need \(j \neq t\)). In order to check the diagonals, we need that \(i - s\) and \(j - t\) as well as \(i - s\) and \(t - j\) are different. (We can check both at the same time using the absolute value.)

Again, instead of explicitly writing out the loop, we use one of Maple's built-in functions. The andmap functions checks whether a predicate (here given by an anonymous procedure) holds for every entry in a given list.

safeAdding := proc(i :: posint, j :: posint, board :: Vector(posint)) :: boolean:
    andmap(proc(s) local t:
               t := board[s]:
               j <> t and abs(i-s) <> abs(j-t)
           end proc, [$1..i-1])
end proc:

Finally, we run our procedure with boards of different sizes.

map(Queens, [$1..10]);

This yields the following table:

his matches the values listed in the Online Encyclopedia of Integer Sequences.