It was januari 1994, nine years ago from when I wrote this, that I made a small set of webpages with the rules of
a few chess variants. This was the start of what now is The Chess Variant Pages,
chessvariants.com. To celebrate these nine years of chess variant webpages, we had a small
contest: we looked for the best solution to a problem, called The 9 Queens Problem.
The 9 Queens Problem
A predecessor: the 8 queens problem
There is a famous chess puzzle or problem, called the 8 queens problem, or
8 queens puzzle. In this puzzle, one should try to place eight queens on a chessboard,
such that none of these queens sees another one. In other words, we must
select eight squares of the eight by eight chessboard, such that no row, no column, and no
diagonal contains more than one selected square. Here is one of the solutions to this
8 queens problem:
The eight queens problem is a famous problem, and has a long history; it probably
is some centuries old. (Who can tell me the origin of this problem?)
The problem is also used in education: with many collegues, I use the problem as
an example when teaching the principles of backtracking in the algorithms class
for computer science students.
One queen more
It should be clear that it is impossible to place nine queens on a checkboard without
anyone seeing another one: for instance, as there are eight rows, there must be two queens
on a row when we have nine queens. But now, suppose that we are allowed to use
one or more pawns that shield the queens to each other? How many pawns do we need to
put nine queens on the board?
In other words: place nine queens and a number of pawns on a chessboard, such that,
whenever there are two queens on the same row, column, or diagonal, there is a pawn
between them. Find a solution that uses as few pawns as possible.
It is not hard to modify the solution of the eight queens problem that we see above to
one for the nine queens problem that uses three pawns.
But, what is the minimum number of pawns needed? Is there a solution
with only two pawns? Is there a solution with only one pawn?
The contest was: find a solution with the minimum number of pawns.
Solution
There is a solution with one pawn. One is already posted in the comment system :-(; more will be posted later here.
Winner
There were seven correct submissions to the contest. Randomly, a winner was selected from the contest: it is Gary K. Gifford. Congratulations, Gary!
The prize that Gary wins is the book:
303 Tactical Chess Puzzles
by Fred Wilson and Bruce Alberston
The solution and the winner will be published on this website in March 2004. The nine queens problem was
invented by Wim Bodlaender.
Webpage created: January 3, 2004.
Webpage made by Hans Bodlaender.