In 1848, Max Bezzel first posed the Eight Queens Problem: Place eight queens on a chessboard so that no two queens attack each other. This problem was generalized in 1869 to the N-Queens problem (N mutually non-attacking queens on an N-by-N chessboard).
In 1995, Michael Anshel of the City University of New York presented the following problem to an Artificial Intelligence seminar : if we remove some of the squares of the chessboard, can we place more than N queens on the "partial chessboard" that remains? In 1998, Anshel's student, Kaiyan Zhao, defended her doctoral thesis entitled "The Combinatorics of Chessboards," which considered "The Queens Problem on a Partial Chessboard". Among other things, Zhao proved that three pawns are necessary and sufficient to allow six nonattacking queens on a five-by-five board.
In 2004, the Chess Variant Pages sponsored a contest that posed the following question (credited to Wim Henk Boedlander): We can put nine mutually non-attacking queens on an eight-by-eight board if we put some pawns on the board to block queen attacks. How few pawns are necessary? The answer turns out to be 1, as you can see in the picture below. The Nine Queens Problem contest can be found at http://www.chessvariants.org/problems.dir/9queens.html .
The contest participants soon asked about generalizations, such as "How many pawns would it take on a larger board?" It turns out that for N > 5, we need to put only one pawn on the board in order to allow us to place N+1 nonattacking queens on the board. More generally, for each k > 0, if N is large enough we can place N + k queens and k pawns on an N-by-N board so that none of the queens attack each other. For more details, see our papers listed below .
Open Problems
Here is a partial list of unsolved problems related to the N+k Queens Problem:
For a particular N and k, how many ways are there to place N + k queens and k pawns on an N-by-N board so that no two queens attack each other? We've done some computer searches and come up with some numbers, but we haven't got a closed-form formula. (Then again, no formula has been found yet for the number of solutions to the N-Queens problem.)
Where can the pawns go?
What happens if we look at non-square boards?
On a standard chessboard, if you want to place queens on the board so that every square is attacked or occupied, the minimum number of queens you need is five. If we wanted to increase or decrease that number, how many pawns would we need to place on the board, and where? (And how many pawns would we need on other-sized boards to increase or decrease the number of queens needed to dominate those boards?)
What happens to other graph-theoretic parameters when we place pawns on a chessboard?
What happens if we use pieces other than queens, such as bishops or rooks or even nonstandard pieces like the amazon (combination of queen and knight)?
Some partial answers are available in the papers placed on this site.
Resources and Links
Talks
Here are slides from some of our talks related to this subject:
SeparationNumbersEKU.pdf : I gave a colloquium talk to the Department of Mathematics and Statistics at Eastern Kentucky University on September 29, 2006.
tenn_pres.ppt and finalcap.ppt : Matthew Wolff's talks, the first was given at the 19th Annual Cumberland Conference and the second was his senior capstone presentation. These presentations discuss how we used Knuth's Dancing Links algorithm to develop a faster parallel program for counting the number of solutions to the N+k Queens Problem. (Note: The files are in MS-PowerPoint format.)
WahleSUMS.ppt: On October 13, 2007, Nick Wahle gave a talk at the Shenandoah Undergraduate Mathematics and Statistics Conference on transit graphs, a generalization of chessboard graphs. This file is in MS-PowerPoint format.
HuffordSUMS.ppt: On October 13, 2007, Casey Hufford gave a talk at the SUMS conference on book embeddings of chessboard graphs with some results on the effect of placing a pawn on the board.. This file is in MS-PowerPoint format.
MillerMCCC.ppt: On October 13, 2007 (apparently a busy day for us), John Miller gave a talk at The Twenty-first Midwest Conference on Combinatorics, Cryptography and Computing comparing the performance of algorithms that count the number of solutions to the N+k Queens problem. This file is in MS-PowerPoint format.
Reflections.ppt: I gave a talk on August 1, 2008 at the MAA Mathfest in Madison, Wisconsin on symmetric solutions to the N+k Queens problem. This file is in MS-Powerpoint format.
Papers
Here are preprints of papers we've written:
queenssep.pdf : "The Queens Separation Problem" published in Volume 69 of Utilitas Mathematica in March 2006. Note: Table 2 in this paper is faulty. See the next paper or go here for correct numbers.
QueensSep2.pdf: "Independence and Domination Separation on Chessboard Graphs", published in Volume 68 (2009) of the Journal of Combinatorial Mathematics and Combinatorial Computing.
cmj204-210.pdf: "Reflections on the N + k Queens Problem", published in the May 2009 issue of The College Mathematics Journal.
dlxMCCC.pdf: "Algorithm Performance for Chessboard Separation Problems", published in Volume 70 (2009) of the Journal of Combinatorial Mathematics and Combinatorial Computing.
JDLXFinalCopy.doc: " JDLX: Visualization of Dancing Links", a paper on a Java applet demonstrating the DLX algorithm presented on September 26, 2008 at the 2008 Midwest Regional Conference of the Consortium for Computing Sciences in Colleges.
Here is an educational Java applet by Maureen Doyle, Amber Rogers, and Bernadina Rawe illustrating the DLX algorithm as applied to the N-Queens Problem: JDLX.jar. (We used a DLX algorithm to count the number of solutions to the N+k Queens Problem.)
Solution Counts
If you want the number of solutions to the N+k Queens Problem for certain small N and k, try one of these links:
solution_counts.html: Table providing (for some values of N and k) the number of ways to place N + k queens and k pawns on an N-by-N board so that no queens attack each other.
amazon_solution_counts.html: Table providing (for some values of N and k) the number of ways to place N+k amazons and k pawns on an N-by-N board so that no amazons attack each other
http://en.wikipedia.org/wiki/Alternating_sign_matrix: Take a N+k Queens (or Rooks) solution, replace the pawns with -1's, the queens (rooks) with 1's and the empty squares with 0's, and you get an alternating sign matrix. The Wikipedia article includes links to some interesting papers.
Thanks to the colleagues who have collaborated in this research, including Robin Blankenship, Maureen Doyle, Gerd Fricke, Walter Kosters, Duane Skaggs, and Jeff Ward. Thanks also to the students who have assisted us, including Kelly Gripshover, Craig Hamilton, Joe Harless, Casey Hufford, Robert Jeffers, John Miller, Jon Reitmann, Amber Rogers, Brian Salyer, Luke Thompson, Nick Wahle, and Matt Wolff.
The research described in this website was partially supported by NSF KY-EPSCoR Research Enhancement Grant UKRF 3046884400-07-419, NASA KY-EPSCoR grant NCC5-571, Morehead State University Faculty Research Grant 225229, and many MSU Undergraduate Research Fellowships.
