17
$\begingroup$

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)

$\endgroup$

5 Answers 5

23
$\begingroup$

Here is the optimal answer with

6 princesses.

Shown as knights;

enter image description here

$\endgroup$
14
  • 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$
    – GoodSp33d
    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$
    – pajonk
    Commented 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$
    – user10445
    Commented Oct 15, 2019 at 17:12
9
$\begingroup$

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

Image of solution:

7 princesses
Dots represent knight moves, lines represent bishop moves.

$\endgroup$
1
  • 3
    $\begingroup$ It's a good start and sets an upper-bound on the solution! $\endgroup$
    – Dr Xorile
    Commented Oct 15, 2019 at 0:03
8
$\begingroup$

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...
........

$\endgroup$
1
  • 2
    $\begingroup$ You're right about the 6. Thanks for inspiring this! $\endgroup$
    – Dr Xorile
    Commented Oct 15, 2019 at 15:38
8
$\begingroup$

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...
........
........

$\endgroup$
2
  • $\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
6
$\begingroup$

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:

enter image description here

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]
$\endgroup$
3
  • $\begingroup$ How long does that take to run? Thanks for posting. Great answer $\endgroup$
    – Dr Xorile
    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$
    – Brent
    Commented 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.