The game of chess is fairly old. Therefore many chess puzzles had been invented during time, which are not actually chess games, but only use chess pieces in one way or another. This chapter contains such type of puzzles.
When trying to solve the »Problem of the Month July 2006« by Erich Friedman, I was inspired to write down more details of my findings. The following pages are the result. The question how to populate an n*m rectangular chess board with white chess pieces, that every cell is attacked exactly k-times, is rather challenging. The attack condition must hold for all cells of the board, whether occupied by a piece or empty. The basic rules how chess pieces attack are necessary to understand the following and are assumed to be well known.
All kinds of pieces are allowed in any number and on any cell, but of course only one piece on a cell. Pawns are used without extra rules like conversion and can be set on first and last row. To be precise the term »k times attacked« counts only direct attacks on a cell. This is slightly different from a chess player's view, who would e.g. count cells in front of a double rook as doubly attacked.
These rules create an interesting and considerable difficult puzzle, which will be thoroughly investigated. It's some kind of exact cover problem like polyform puzzles, but the behaviour of the pieces is more dynamic and depend on the context. The original question from Erich Friedman asks for minimal solutions, i.e. those with the fewest number of pieces. Here we will analyse the puzzle in-depth and look for other interesting facts.
We can find most of the solutions of 2*2 and 3*3 boards by taking the wooden chessboard from the shelf and playing with the pieces.
Single, double and triple attacks:
The graphics are drawn using a chess font made by Eric Bentzen. The design of the pieces is adapted from the books of "Sportverlag Berlin". This DDR (East Germany) publishing house issued at that time translations of brilliant Russian chess books. I used these books in my younger days successfully and with great pleasure to learn chess tactics.
But it's laborious trying to find all solutions even with small board sizes manually. Therefore careful considerations are needed to find a procedure that finds the complete solution set. The upper bound for the number of piece placements is 7n*m, six kinds of pieces or an empty place on every cell. This number is already a too large to make the crude approach of letting a computer try all placements.
A procedure is needed that fills the board cell by cell. The first approach, to set pieces sequentially until one cell is attacked more than k times, is flawed. The condition is not valid, because the attack path of pieces working far-ranging may be interrupted by pieces set later in the process.
Illustration:
Every cell on a 5*5 board needs a double attack. The pieces will be placed in
bottom to top and left to right order. When placing the bishop on c1, we find
the cell a3 triple attacked already. But it's wrong to conclude that the position
of the bishop is invalid, because any pieces on the blue marked cell brings
a3 back to a valid double attack. This creates a dilemma to define a validation
condition for sequential piece placements. At least I don't know any.
On second thought the idea emerged to look at the subject from the direction of the final solution. We can decompose every solution into a number of pieces with the attacked cells attached. This means we focus on attack patterns instead of pieces. An attack pattern is a chess piece together with the attacked cells and context conditions allowing the pattern to be set. So the attack patterns are solution fragments that build the solutions when combined. Especially pieces that attack far-ranging create a multiplicity of attack patterns, whether or not adjacent cells are occupied. Attack patterns depend on form and size of the board, the position on the board and the status of the surrounding cells. They have to be calculated for each board individually. Each of the following diagrams show exactly one attack pattern.
Some
illustrations:
The patterns of knights, kings and pawn are easy to understand. These pieces
do not attack far-ranged and their patterns do not depend on neighbouring pieces.
There is exactly one pattern for every cell of the board.
The
bishop on the contrary is a far-range attacking piece and therefore has many
attack patterns for each board position. The left diagram shows the pattern
that occur, if on the cells marked with red rings any other piece is placed
and the cells marked blue are free. The bishop has four attack patterns related
to the cell c2. Note that additional pieces at the edge of the board are not
impacting the pattern.
On a 5*5 board kings, knights and pawns have a total number of 25 patterns each,
bishops 95, rooks 324 and the queen as most flexible piece has 1331 attack patterns.
Four types of status information define every attack pattern, where the types 3 and 4 can come only in addition of attacked cells.
Attack patterns can be added under certain conditions. According to the classical chess rules, of course only one piece is allowed on a cell. Cells of type 1 conflict with type 3, that means no pieces can be placed on cells, which are defined free by the other pattern. Additionally cells of type 3 and 4 are mutually exclusive.
Examples:
These three patterns are incompatible to each other. The pawn would be placed
on cells that must be free. The pattern of the bishop requires a piece on d3,
which is blocked by the queen.
The next diagram shows a sequence of allowed additions. The result is always
independent of the calculation order.
Every solution of the chess puzzle is a unique sum of attack patterns.
With these preliminary considerations the step to the solution procedure is pretty simple. As a start we restrict the problem to single attacks.
At first all attack patterns of all pieces are generated for all cells. Then we define a certain order for the cells. The procedure will proceed in this order. Every order is fine, but should not be altered on the way. Now each cell has a number from 1 to n*m and we can for each pattern determine the minimal cell number that is attacked by this pattern (type 1). At the same time each cell corresponds to a list of patterns, which attack none of the cells with smaller numbers.
The solution procedure starts with the first cell and the first pattern in the associated list. Then we search for the next free cell, do the same and add the first compatible pattern that does not exceed the attack count of any cell. This mechanism repeats until a list is at the end. In that case the procedure goes back to the pattern of the previous step and exchanges it with the next compatible pattern in the list (backtracking). Because of the construction of the pattern lists it's assured that with every step all patterns used have no effect on the attack count of all previous cells.
Now there is only a little complication left. While continuing the procedure it may or may not happen that cells requiring a piece on it do actually have a piece set. To assure this, the procedure checks the type 4 condition before advancing to the next cell. If the cell needs a piece placement, a compatible pattern is added.
With this procedure all solutions will be found exactly once, if we count all rotated and mirrored solutions too. The symmetric variants are discarded in a separate work step after completion of the main procedure.
We can do a little optimization by discarding redundant attack patterns. The pattern of king and queen is identical, if the piece is completely enclosed by other pieces. The same applies to bishops and pawns on the first row. In that cases only the king and bishop patterns are used. Of course this has an impact on the total number of solutions. Another special case is pieces that attack no cells, e.g. pawns on the last row. These will be used only if an attack path of a far-ranged attacking piece needs a block.
In case the problem asks for multiple attacks, the procedure works as described above and adds attack patterns until the attack count for the current cell is reached. Additionally we can create all combinations of multiple attacks for each cell and use it if appropriate to save computations under way. Special care is necessary to avoid redundant solutions that occur through permutation of pattern on the same cell.
Examples:
The three patterns show triple and quadruple attacks on the blue marked cell.
All complex patterns are created by adding a number of single attack patterns.
Note the cells with dashed red rings. These mark cells, where the required piece placements are already resolved within the combined pattern.
I am not sure that this procedure is optimal. But it works and delivers correct and complete results. Furthermore the mechanism works not only for rectangular boards but also for any kind of form. Additionally every cell may have an individual attack count.