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.
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.
A princess is a piece from fairy chess that can move like a knight or a bishop.
$\endgroup$
I have an arrangement with 9 7? Lot of overlap, but not sure how to improve.
Image of solution:
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... ........
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... ........ ........
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]