## Friday, April 27, 2018

### some Chessboard Puzzle solutions

In the previous post I mentioned some mathematical chessboard puzzle puzzles, created as part of working through the book Across the Board, by John J. Watkins. This post provides some possible solutions to the puzzles on that puzzle page.

Queens on a 5 by 5 board

The puzzle "Place 3 queens on a 5x5 chessboard. The board must be dominated," is asking you to find the minimal dominating set for queens on a 5x5 board (3 is the queen's domination number for 5x5 boards). Here are two solutions:

The large dots show where the queens are placed, and a small dot appears on every square that is reachable by a queen. In the solution on the left, all three queens can be attacked, but in the solution on the right, the queen in the corner is uncovered.

The puzzle "Place 5 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent," is asking you to find the maximal independent set for queens on a 5x5 board (5 is the queens independence number for 5x5 boards). Here's a solution:

There is also a puzzle that asks you to find an arrangement between the domination and independence numbers, "Place 4 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent." Here is one solution for that:

Queens on other boards

On a 6x6 board, our queen puzzles will be bounded by the domination number of 3 and the independence number of 6. Here are solutions for those:

In between these, we have "Place 5 queens on a 6x6 chessboard. The board must be dominated. The pieces must be independent;" here's a solution for that one:

Just to get a sense of what solutions to these might look like in general, let's jump up to 8x8. In this case, the domination number for queens is 5, so the puzzle in our set with the fewest queens on 8x8 is "Place 5 queens on a 8x8 chessboard. The board must be dominated. The pieces must be independent." Here is one solution:

This particular solution is of interest because the pieces are in a pattern known as the Spencer-Cockayne construction, which can be used to find coverings of square boards of side length 9, 10, 11, and 12 as well. More interesting details can be found in Across the Board.

Knights on a 5x5 board

There are plenty of "independence and domination" problems for the knight on a 5x5 board, because the gap between the domination number (5) and the independence number (13) is so large (compared to queens on the 5x5, at least). Finding solutions for some of the intermediate numbers is a bit tricky, you may find.

For example, here is a solution to "Place 9 knights on a 5x5 chessboard. The board must be dominated. The pieces must be independent":

Knights on other boards

All puzzles based on the maximum number of independent knights on a board have the same solution: put a knight on every square of the colour that has the most squares (on odd boards, one colour has more squares than the other).

Here is an example of a puzzle based on a "sub-optimal" dominating set that is also independent: "Place 11 knights on a 6x6 chessboard. The board must be dominated. The pieces must be independent." And a solution:

Bishops on 5x5

Of the remaining pieces that we have puzzles for, bishops, kings, and rooks, the bishop is the most interesting, and the 5x5 board gives a good idea of how to construct the puzzle solutions.

Consider these two puzzles:

"Place 5 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

"Place 8 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

The minimum dominating set for bishops on a 5x5 board has 5 pieces, and the maximum independent set has 8. In between these, we can also form puzzles based on non optimal dominating sets (that are also independent), such as:

"Place 6 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

"Place 7 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

Solutions for finding similar solutions for bishops on boards of other sizes follow the same patterns as those on the 5x5 board.

Hopefully, these examples will help you out if you get stuck on any of the puzzles. As mentioned earlier, if you are interested in learning more about the mathematics behind these puzzles, check out Across the Board.

Related posts and pages
domination and independence puzzles
post introducing chessboard puzzles
chess tour puzzles
post on chess tour puzzles