Problem of the Month
(January 2009)
This month we consider a pair of problems involving chess pieces (no pawns) and polyominoes.
1. Given a polyomino P, what is the smallest number of chess pieces that can be put on a rectangular chessboard so that the unoccupied unattacked squares form P? What are the answers for some polyominoes?
2. Given a polyomino P and a chess piece, what is the smallest number of copies of P that can be arranged so that the chess piece can visit each square exactly once and return to its starting square? We insist that the copies of P be non-overlapping, and that the cycle of chess moves not leave the polyominoes. What are the answers for some polyominoes and chess pieces? Does one copy of P always suffice for queens? For each chess piece, what is the smallest polyomino that requires n copies for a cycle? Are there polyomino - chess piece pairs that are impossible?
ANSWERS
1.
For each polyomino we have shown the fewest number of pieces, and for the same number of pieces, the smallest area chessboard. Here are the best known results.
Small Polyominoes
Pentominoes
Hexominoes
 |  | 
(Berend van der Zwaag) | 
(Berend van der Zwaag)
|
| 6 | 
|
|
Heptominoes
| 1 |  | 
|
| 3 |  |  | 
(Berend van der Zwaag) | 
(Berend van der Zwaag)
|
(Berend van der Zwaag) | 
(Gavin Theobald)
|  | 
(Berend van der Zwaag)
|
 | 
(Gavin Theobald) | 
(Gavin Theobald)
|
 | 
(Berend van der Zwaag) | 
(Gavin Theobald)
|
| 7 | 
|
|
2.
Evidently, in 2004, Livio Zucca and Gabriele Carelli investigated this question for paths rather than cycles. Their results are shown here.
Here are the best known results for cycles:
Small Polyominoes with Knights
| 2 |  | 
(Berend van
der Zwaag)
|
| 3 | 
(Berend van
der Zwaag) | 
|
| 6 | 
(Gabriele Carelli)
|
|
Pentominoes with Knights
| 2 | 
(Livio Zucca)
| 
(Livio Zucca) | 
(Livio Zucca) | 
(Berend van
der Zwaag)
|
| 4 | 
(Livio Zucca)
| 
(Livio Zucca) | 
(Livio Zucca)
| 
(Livio Zucca)
| 
(Livio Zucca) | 
(Livio Zucca)
| 
(Livio Zucca)
|
| 6 | 
|
|
Anti Solg was interested in solutions with holes.
Livio Zucca found the best known solutions for knights for most of the hexominoes. Gabriele Carelli improved two of them. Livio Zucca also found the best known solutions for knights for most of the heptominoes. These can be done with 2 copies, and these apparently need 4 or 6 copies. Gabriele Carelli improved three of them. Can any more be improved?
Livio Zucca also found all the 10-gons and 12-gons that only require 1 copy.
Berend van der Zwaag asked which polyominoes had completely disconnected solutions for knight tours. Here are the smallest known:
Smallest Known Completely Disconnected Knight Solutions
 |  | 
(Gabriele Carelli)
|  |  | 
(Gabriele Carelli)
|
|
Here are the smallest known polyominoes requiring n copies for other chess pieces:
Smallest Known Polyominoes Needing n Copies for Kings
2
| 3
(Bryce Herdt)
| 4
| ∞
(Bryce Herdt)
|
Smallest Known Polyominoes Needing n Copies for Rooks
2
| 3
(Bryce Herdt)
| 4
| ∞
(Bryce Herdt)
|
Smallest Known Polyominoes
Needing n Copies for Queens
2
(Bryce Herdt)
| ∞
(Bryce Herdt)
|
Smallest Known Polyominoes
Needing n Copies for Knights
1
| 2
| 3
(Berend van
der Zwaag)
| 4
| 6
(Gabreiele Carelli)
| ∞
(Bryce Herdt)
|
Bryce Herdt considered the same problem for the wazir, a fairy chess piece which can only move one square at a time horizontally or vertically.
Smallest Known Polyominoes
Needing n Copies for Wazirs
2
| 3
(Bryce Herdt)
| 4
(Bryce Herdt)
| 8
(Bryce Herdt)
| ∞
(Bryce Herdt)
|
Here are the best known solutions for giraffes, also known as (1,4) leapers.
Smallest Known Solutions For Giraffes
| 
| 
(Anti Solg)
| 
(Anti Solg)
| 
(Anti Solg)
|
(Anti Solg)
| 
(Anti Solg)
| 
(Anti Solg)
| 
(Anti Solg)
| 
(Anti Solg)
| |
Here are the best known solutions for zebras, also known as (2,3) leapers.
Smallest Known Solutions For Zebras
(Anti Solg)
| 
(Bryce Herdt)
| 
(Bryce Herdt)
| 
(Bryce Herdt)
|
(Anti Solg)
| 
(Anti Solg)
| 
(Anti Solg)
| |
What are the solutions for other fairy chess pieces?
If you can extend any of these results, please
e-mail me.
Click here to go back to Math Magic. Last updated 8/10/15.
