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:

  1. Enter n, the size of the chessboard, and press enter.  A blank n-by-n chessboard will appear.
  2. 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!

 

Home

 

 

Copyright Gregory Rabo and Tricia Muldoon Brown