# 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. – Dmitry Kamenetsky Oct 15 '19 at 5:10
• @Tim If C6 is a queen A5 is still uncovered right ? Its covered if its a knight. – GoodSp33d Oct 15 '19 at 9:32
• @GoodSp33d A princess is a piece from fairy chess that can move like a knight or a bishop. – pajonk Oct 15 '19 at 12:49
• How easy is it to show that there is no solution with only 5 princesses? – Tanner Swett Oct 15 '19 at 14:04
• @GoodSp33d: there are no queens in this puzzle... – user10445 Oct 15 '19 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! – Dr Xorile Oct 15 '19 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! – Dr Xorile Oct 15 '19 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. – Jaap Scherphuis Oct 16 '19 at 10:05
• @JaapScherphuis I think we'd all love to see the source code – Pureferret Oct 16 '19 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 – Dr Xorile Oct 16 '19 at 19:03
• It takes about 2 minutes on my machine (the vast majority due to calculating the n_covered5 variable). – Brent Oct 16 '19 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. – Daniel Mathias Oct 16 '19 at 23:55