Treebeard's Stumper Answer
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?
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!)
- Most generally, how many ways can n queens be placed on a n x n chessboard? And what's the least number of queens (<= n) that can cover every square? Each of the remaining questions can also be generalized for n x n boards.
- We can ask the same questions about rooks, bishops, knights, and kings. (Pawns are excluded since they can only move in one direction.) What are the most peaceful pieces and the fewest warrior pieces for each chess piece?
- The five warrior queens question can be made more specific. Can you place five peaceful queens on a chessboard that attack every square, but not each other? Can you place five warrior queens on a chessboard that attack every square and each other?
- Graybear, Donna, and I all wondered if it's possible to cover the board with just four queens. It's not. But what's the least number of unattacked squares for four queens on an 8x8 board?
- The eight queens stumper can be turned inside out into the non-dominating queen stumper. Find an arrangement of n queens on a n x n chessboard that leaves the greatest number of unattacked squares.
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!
- My 8QUEENS and 5QUEENS BASIC programs are available from Treebeard's BASIC Vault with source code and DOS/WIN executables. The eight queens code is modified from C++ code I found on the Web by David Sleeper. Good ol' DOS BASIC (actually MS BASIC PDS 7.1) is still my favorite programming language for finding quick solutions!
- Eric Weisstein's World of Mathematics has good info on chess problems and links to solutions. This useful math reference is finally available on the Web without restriction. Follow the links.
- Sloane's On-Line Encyclopedia of Integer Sequences is a remarkable search engine for number sequences. You can enter a few numbers and it will return a list of matches to explore. There are many sequences involving chess, including A000170, A002562, A032522, A001366, A006494, A019317, A001366, A019319, A003192, A048987, A002465, A030978, A006075, and A006076.
- Particle's 8-Queens is an on-line animated solver for 8 x 8 chessboards. Peter Alfeld has a more general program for n x n boards, and so does the Combinatorial Object Server (COS). There's programming code and info here and here. There's a BiBTeX bibliography on this stumper. Mario Velucchi has a quirky postscript paper on the Non-Dominating Queens Problem
- These are classic stumpers, much older than the Web. Check out these classic books (with Amazon links):
- Henry Ernest Dudeney, Amusements in Mathematics (Dover, 1970, problems 300 & 301)
- Hugo Steinhaus, Mathematical Snapshots (3rd ed., Dover, 1999)
- Martin Gardner, Wheels, Life, and Other Mathematical Amusements (W H Freeman & Co, 1985, chapter 17) and The Unexpected Hanging (Univ of Chicago Pr., 1991, chapter 16)
- A. Gardiner, Mathematical Puzzling (Oxford University Press, 1987, chapter 26)
- These stumpers use a standard chessboard and pieces, but they're not really about chess. You can play real chess on the Web against other people. Check out the Free Internet Chess Server (FICS), Chesslovers.com, and Yahoo! Games for more links. Personally, I'd rather play at home with my kids!
Back to Stumper
Last modified .
Copyright © 2000 by Marc Kummel / email@example.com