# Princesses covering an 8x8 chess board

What is the minimum number of princesses you need to place on an 8x8 chessboard so that every empty square is attacked by at least one princess?

A princess is a piece from fairy chess that can move like a knight or a bishop.

(Inspired by recent puzzles)

Here is the optimal answer with

6 princesses.

Shown as knights;

• Ah thank you! This problem was driving me insane. Oct 15, 2019 at 5:10
• @Tim If C6 is a queen A5 is still uncovered right ? Its covered if its a knight. Oct 15, 2019 at 9:32
• @GoodSp33d A princess is a piece from fairy chess that can move like a knight or a bishop. Oct 15, 2019 at 12:49
• How easy is it to show that there is no solution with only 5 princesses? Oct 15, 2019 at 14:04
• @GoodSp33d: there are no queens in this puzzle...
– user10445
Oct 15, 2019 at 17:12

I have an arrangement with 9 7? Lot of overlap, but not sure how to improve.

Image of solution:

Dots represent knight moves, lines represent bishop moves.

• It's a good start and sets an upper-bound on the solution! Oct 15, 2019 at 0:03

This is a great puzzle that had me really hooked!

Partial answer. I can almost do it with 6:

x are princesses. The only square that remains uncovered is Y. I believe 6 should be possible...

........
........
..x.x...
....x...
.......Y
....x...
..x.x...
........


• You're right about the 6. Thanks for inspiring this! Oct 15, 2019 at 15:38

Brute force (which, mind you, might be faulty) revealed that

no solutions with 5 princesses exist

So the accepted answer is probably optimal. Here are, up to mirrorings and rotations, all solutions I found:

Solution 1

........
.X...X..
...X....
.....X..
........
..X.X...
........
........

Solution 2
........
.X......
...XX.X.
........
........
..X.X...
........
........
Solution 3
........
..X.....
....XX..
........
........
....XX..
..X.....
........
Solution 4
........
........
..XXXX..
........
........
...XX...
........
........

• My program gives the same results as yours. Oct 16, 2019 at 10:05
• @JaapScherphuis I think we'd all love to see the source code Oct 16, 2019 at 15:03

In addition to Oray's and Arthur's answers, I also found via brute force that

There is no solution with 5 princesses.

In particular,

There will always be at least three empty squares that are not attacked by any princess in a 5-princess setup, and there are only 4 (or 32, including reflections and rotations) setups for which only three empty squares are not attacked.

The (as close to optimal but still failing) setups:

Code (R):

#######
# Set up chessboard
# reading as book, numbers 1-64
#######
xs <- rep(1:8, times=8)
ys <- rep(1:8, each=8)

get_princess_moves <- function(ind){
x <- xs[ind]
y <- ys[ind]

### Bishop-like moves (includes self)
## Up-right/down-left diagonals
moves <- c(unlist(mapply(function(xcand, ycand){
which(xs == xcand & ys == ycand)
}, x + (-7:7), y + (-7:7))))
## Up-left/down-right diagonals
moves <- c(moves, unlist(mapply(function(xcand, ycand){
which(xs == xcand & ys == ycand)
}, x - (-7:7), y + (-7:7))))
### Knight-like moves: each combination of +/- 2 in one direction and +/- 1 in the other direction
moves <- c(moves, unlist(mapply(function(xcand, ycand){
which(xs == xcand & ys == ycand)
}, x + c(2,2,-2,-2,1,1,-1,-1), y + c(1,-1,1,-1,2,-2,2,-2))))

unique(moves)
}

moves_list <- lapply(1:64, get_princess_moves)

n_covered5 <- combn(64, 5, function(inds)length(unique(unlist(moves_list[inds]))))

max_cover5 <- max(n_covered5)

max_inds5 <- which(n_covered5 == max_cover5)

combn(64,5)[,max_inds5]

• How long does that take to run? Thanks for posting. Great answer Oct 16, 2019 at 19:03
• It takes about 2 minutes on my machine (the vast majority due to calculating the n_covered5 variable). Oct 16, 2019 at 19:17
• @DrXorile (also for Brent, and anyone else interested) Here is some C code that runs in about one second if compiled locally. I can improve readability if you like. Oct 16, 2019 at 23:55