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.
$\begingroup$
$\endgroup$
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
14
Here is the optimal answer with
6 princesses.
Shown as knights;
-
2$\begingroup$ Ah thank you! This problem was driving me insane. $\endgroup$ Commented Oct 15, 2019 at 5:10
-
1$\begingroup$ @Tim If C6 is a queen A5 is still uncovered right ? Its covered if its a knight. $\endgroup$ Commented Oct 15, 2019 at 9:32
-
4$\begingroup$ @GoodSp33d
A princess is a piece from fairy chess that can move like a knight or a bishop.$\endgroup$– pajonkCommented Oct 15, 2019 at 12:49 -
3$\begingroup$ How easy is it to show that there is no solution with only 5 princesses? $\endgroup$ Commented Oct 15, 2019 at 14:04
-
2$\begingroup$ @GoodSp33d: there are no queens in this puzzle... $\endgroup$– user10445Commented Oct 15, 2019 at 17:12
$\begingroup$
$\endgroup$
1
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.
-
3$\begingroup$ It's a good start and sets an upper-bound on the solution! $\endgroup$ Commented Oct 15, 2019 at 0:03
$\begingroup$
$\endgroup$
1
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... ........
answered Oct 15, 2019 at 1:00
-
2$\begingroup$ You're right about the 6. Thanks for inspiring this! $\endgroup$ Commented Oct 15, 2019 at 15:38
$\begingroup$
$\endgroup$
2
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... ........ ........
-
$\begingroup$ My program gives the same results as yours. $\endgroup$ Commented Oct 16, 2019 at 10:05
-
1$\begingroup$ @JaapScherphuis I think we'd all love to see the source code $\endgroup$ Commented Oct 16, 2019 at 15:03
$\begingroup$
$\endgroup$
3
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]
-
$\begingroup$ How long does that take to run? Thanks for posting. Great answer $\endgroup$ Commented Oct 16, 2019 at 19:03
-
$\begingroup$ It takes about 2 minutes on my machine (the vast majority due to calculating the n_covered5 variable). $\endgroup$– BrentCommented Oct 16, 2019 at 19:17
-
2$\begingroup$ @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. $\endgroup$ Commented Oct 16, 2019 at 23:55