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
quickly generalized 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.
The "Nine Queens Problem" Contest
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 .
One Extra Queen
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. For more details, see
http://people.moreheadstate.edu/fs/d.chatham/queenssep.pdf.
Many Extra Queens
More generally, we can prove the following theorem: 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 on that proof,
see
http://people.moreheadstate.edu/fs/d.chatham/QueensSep2.pdf .
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.
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", to appear in the Journal of
Combinatorial Mathematics and Combinatorial Computing.
Pictures
If you want to see some solutions to the N+k Queens Problem, look at the
following files:
nopawn.pdf: A PDF file with pictures of the
fundamental solutions to the N+0
Queens Problem :) for N=4,5,6,7,8,9, and 10.
onepawn.pdf: A PDF file with pictures of the
fundamental solutions to the N+1
Queens Problem for N=6,7,8,9, and 10.
twopawn.pdf: A PDF file with pictures of the
fundamental solutions to the N+2
Queens Problem for N=7,8,9, and 10.
threepawn.pdf: A PDF file with pictures of
the fundamental solutions to the N+3
Queens Problem for N=8,9, and 10.
Programs
Here are some recreational scripts involving the N+k Queens Problem:
play9queens.html: A Javascript to play with. The goal is to come up with a solution to the 8+1
Queens Problem.
play10queens.html: Another Javascript.
The goal is to come up with a solution to the 8+2 Queens Problem.
play11queens.html: Another Javascript.
The goal is to come up with a solution to the 8+3 Queens Problem.
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, Duane Skaggs, and Jeff Ward.
Thanks also to the students who have assisted us, including Kelly Gripshover,
Joe Harless, Casey Hufford, John Miller, Jon Reitmann, Amber Rogers, 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, and Morehead State
University Faculty Research Grant 225229.
