News of the Week

A Royal Squeeze

+ See all authors and affiliations

Science  05 Sep 2008:
Vol. 321, Issue 5894, pp. 1283a
DOI: 10.1126/science.321.5894.1283a

MATHFEST 2008, 31 JULY-2 AUGUST, MADISON, WISCONSIN

In 1850, the great German mathematician Carl Friedrich Gauss took a shine to a funky little counting problem: How many ways can eight queens be placed on a chessboard so that no two queens attack one another (i.e., line up horizontally, vertically, or diagonally)? It's not obvious it can be done at all, but it turns out there are 92 solutions. Gauss didn't spot them all, proof in itself that the problem is a bit of a poser.

Modern computers can easily find all 92, but mathematicians have upped the ante so that even Deep Blue would scratch its silicon head, mainly by making the board larger. There are, for example, 2,207,893,435,808,352 ways of placing 25 nonattacking queens on a 25 × 25 chessboard, a computation completed 3 years ago at INRIA.

“There's a lot of interesting theory behind these questions,” notes Loren Larson, a chessboard problem expert in Northfield, Minnesota. “They're also nice programming exercises. They're good examples of backtracking algorithms,” also known as depth-first searches.

In a talk at MathFest, Doug Chatham of Morehead State University (MSU) in Kentucky described a variant he and collaborators have explored, in which pawns are allowed on the chessboard. The pawns interrupt the queens' line of sight, making it possible for more queens to fit on the board. How many more queens, they wondered, do the pawns make possible?

Chatham and crew—MSU colleagues Gerd Fricke and R. Duane Skaggs, Maureen Doyle of Northern Kentucky University in Highland Heights, Matthew Wolff of Pyramid Controls Inc. in Cincinnati, Ohio, and MSU student Jon Reitmann—have proved that each additional pawn permits an extra queen, provided the board is large enough. For example, with two pawns, it's possible to get 10 queens on a standard 8 × 8 board (see figure). In the current proof, fitting an extra k queens using k pawns on an N × N board requires N to be greater than 25k, Chatham notes, but adds, “We believe the actual minimum sizes are much smaller.”

Vivat regina.

Adding pawns makes a classic chessboard problem even more queenly.

CREDIT: D. CHATHAM ET AL.

There are no immediate applications for the queens-and-pawns problem, Chatham says, but the original nonattacking-queens problem has found uses in computer science for parallel memory schemes and in statistical physics for particle models with long-range interactions. “We hope to find similar applications for our problem,” he says.

Related Content

Navigate This Article