The Initial *n*-Queens problem

Let *n* be a positive
integer. The *n*-queens problem asks, ÒCan *n *non-attacking queens be placed on an n by n
chessboard?Ó

Many mathematicians, computer scientists, and game
enthusiasts have studied variations on this question over the past two
centuries. The origins of the *n*-queens problem can be traced back to a German chess
composer living in 1841. In the *Berliner
Schachzeitung*, Max Bezzel asks if 8
non-attacking queens can be placed on a standard chessboard. In the 1850's this problem was attacked
by notably by Gauss with all 92 solutions being published by Nauck. Questions about the general case were
quickly asked, and Pauls gives the first set of solutions for the general *n*-queens problem in two articles published in 1874 in
a chess newspaper. Generalizations
to the* n*-queens problem include studying
the problem on chessboards of different shapes and dimensions and finding
non-attacking solutions using other chess pieces and combinations of chess
pieces.

The program on this website attacks a question posed by Bell
and Stevens in their 2009 survey paper.
ÒGiven a queen already put on some square, when can *n-1* other queens always be placed to give a solution,
and if this is not possible, for what* n* is it possible?Ó In fact
we generalize, given an initial arrangement of* k *non-attacking queens, when can *n-k* queens be placed on the board to give a
non-attacking *n*-queens
solution? We may generalize again,
given an initial arrangement of *k*
non-attacking queens, rooks, and bishops, what is the maximum number of these
pieces that may be also placed on the board to give rise to a non-attacking
arrangement?

Directions:

- Enter
*n*, the size of the chessboard, and press enter. A blank n-by-n chessboard will appear. - Input the desired initial arrangement. Click on the box you want to place a queen. The box should turn green. Double click to place a rook turning the box blue. Triple click to place a bishop. The box will turn red. When youÕve placed all the initial pieces, press enter.

Solutions will appear in a list on the right side of the screen. Values will appear in all the boxes of the chessboard. These numbers tell you the number of non-attacking solutions which contain the initial arrangement and that box.

Try it out HERE. This program was written by Gregory Rabo.

A brief description of the backtracking algorithm used above is here.

If youÕd like to try out the original version using only queens try this also written by Greg.

This research supported by NSF-STEP award number 0856593.

Theorems and Conjectures coming soon!

Copyright Gregory Rabo and Tricia Muldoon Brown