Check out Atomic Chess, our featured variant for November, 2024.

Contest: The 9 Queens Problem

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
    A review and more information on the book can be read at: http://www.chessvariants.com/books.dir/303chesspuzzles.html.

    Final remarks

    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.