Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
4 February 2000

Peaceful Queens and Warriors

It's been fun eavesdropping in Jesse's afternoon chess class at Dunn Middle School. And I get to ask a classic chess stumper. Chess queens can move in a straight line any distance up, down, across, or diagonally. Can you arrange eight peaceful queens on a chessboard so that no queen can attack any other? Eight peaceful queens will threaten every square on the board, but it's overkill. What's the smallest number of warrior queens that can threaten every square? (Hint: It's ok to experiment with pawns or checkers. Think how the knight moves!)


DMS students playing chess in the science room.

It's hard to place eight peaceful queens on a chessboard so that no queen is under attack! But you will find an answer if you stick with it. There are 92 solutions that are rotations and reflections of the 12 unique answers shown below. The most peaceful queens is eight, and I'm sure the fewest warrior queens that can attack every square is five. Spencer's solution is also shown below. Note that one of his five queens is attacking another. Can you find a different solution where the queens are all peaceful? And another where the queens are all under attack? (Spoiler below!)

Here are the 12 unique arrangements of eight peaceful queens on an 8 x 8 chessboard. The last one is my favorite because of its symmetry. There are 8 variations of each basic form due to rotations and reflections. So how come there are only 92 solutions rather than 12 x 8 = 96 solutions?
 
We found the second stumper more difficult even though there are 4,860 solutions based on 638 unique arrangements! Here is Spencer's first arrangement of five warrior queens who attack every square. Note the two queens to the right are attacking each other. Can you find other arrangements where the warrior queens are all peaceful or all under attack?

Notes:

The 8 Queens Problem is a classic stumper, and I was surprised (and pleased) that the kids at school didn't know it. Pleased, because I could ask it as a new stumper! It's surprisingly difficult to place eight peaceful queens on a chessboard. I took 15 minutes from my drafting class and set a dozen kids at solving it. Thomas, Kevin, and Max found solutions after about five minutes, but everyone else gave up.

Graybear sent this comment (along with good answers), which speaks for me too:

Ah! A couple of oldies but goodies! They remind me of my youth when I read a lot of Martin Gardner, Sam Loyd, and other brain teaser books. I had fun re-establishing the solutions. Of course, when you consider rotations and mirror images, there are many solutions...
I found the five warrior queens problem more difficult and more interesting. It's mysterious seeing how the squares that aren't in any queen's rank or file are covered by unexpected diagonals. Maybe this seems harder because it's more difficult to check solutions. Donna and her daughtor Sarah found a useful method:
Our method involves placing goldfish (the crackers) on the squares that are controlled by the placement of each queen, leaving a visual image of uncovered squares. This works well, until our curious cat "Tuffy" becomes obsessed with swatting the goldfishies off the chessboard!!! Cheers!
GO stones also work, and my cat doesn't care.

After finding a few solutions to each stumper, I worked at two BASIC computer programs and let my computer go the work. I'm amazed that anyone found comprehensive solutions before home computers! My 8QUEENS and 5QUEENS programs quickly find all the solutions, but they don't (yet) consider rotations and reflections to find only the unique solutions.

My programs find 92 ways of arranging eight peaceful queens and 4,860 ways of arranging five warrior queens to attack every square. It takes longer to arrange five warrior queens. There's an elegant recursive way to check arrangements of eight queens since we know there can only be one queen on each rank and file. But with five queens, it's necessary to check every arrangement of five queens. There are 64 x 63 x 62 x 61 x 60 = 914,941,440 different arrangements if order matters. But order doesn't matter since the queens are all the same. Any arrangement of five queens can be re-arranged in 5 x 4 x 3 x 2 x 1 = 120 ways (that's 5! or 5 factorial), so there are really only 914,941,440 / 120 = 7,624,512 positions to check.

That's the familiar formula for the number of ways to pick n things m at a time, if order doesn't matter: 

           n!          64!         64!      64 x 63 x 62 x 61 x 60
    p = --------- = ---------- = -------- = ---------------------- = 7,624,512 positions
        m! (n-m)!   5! (64-5)!   5! x 59!      5 x 4 x 3 x 2 x 1

For another example, if there are 20 choices of pizza toppings, and you can pick any 3, then there are 
           n!          20!         20!      20 x 19 x 18
    p = --------- = ---------- = -------- = ------------- = 1,140 combinations
        m! (n-m)!   3! (20-3)!   3! x 17!     3 x 2 x 1

It takes my new computer a few minutes to check all positions of five queens. You can click on the previous links to see the results, or download the programs (with BASIC source code and DOS/WIN executable) and do it yourself.

These chessboard stumpers can be generalized in several ways for other chess pieces and different sized boards. (My answers are here!)

I had fun with these old stumpers. I played with them a lot before looking for help on the Web. Here are some useful links to explore after you've paid some dues!

Back to Stumper

Last modified .

Copyright © 2000 by Marc Kummel / mkummel@rain.org