4
$\begingroup$

N kings are placed on a chessboard, with at most one king on any square. Following standard rules of movement (one square in any direction), every king must be able to reach some edge of the board without ever occupying a square that was already occupied, and every square must be occupied exactly once by some king at some point. At the start, and after each move, no king may occupy a square that is currently adjacent to another king, horizontally or vertically (diagonally adjacent is OK). The kings may play in any order, and a king may exit the board once it reaches any edge. Kings may start on an edge square. What is the maximum N, what is a starting configuration that allows this maximum, and what is the order of play that allows all kings to exit the board?

Update: An edge square means any of the 28 squares on the perimeter of the board.

Improve this question
$\endgroup$
2
  • $\begingroup$ I know there's already an answer here, but is it safe to assume it's a standard 8x8 board? $\endgroup$
    – Chipster
    Commented Jan 10, 2021 at 22:40
  • $\begingroup$ Yes, it's a standard 8x8 board. $\endgroup$
    – FlanMan
    Commented Jan 10, 2021 at 23:40

2 Answers 2

Reset to default
6
$\begingroup$

My answer is

N=28 (obviously, it's the upper bound since no edge square can be used by more than one king)

The solution is drawn here:

enter image description here

Note that

the red dots are kings, the numbers are according to their order (e.g. king #1 moves and exits the board, then #2, #3 etc.), the red lines are their routes. It's easy to see that each square is visited only once, and the first 26 kings exit the board without disturbing each other. The king #28 must move first (before #27) and travel part of his path (e.g. to c6) to allow #27 move and exit the board without touching #28, and then continue moving.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ If you make 27 exit on the left instead (SE,W,NW,W,W) and have 26 pick up the extra square (S, NE, SE), then 28 can visit rest of the squares, and all kings can move without pausing. $\endgroup$
    – Bass
    Commented Jan 10, 2021 at 17:29
  • 1
    $\begingroup$ @Bass However, then the solution will be non-symmetric (well, both symmetry and the "non-stop" king moves are not required). $\endgroup$
    – trolley813
    Commented Jan 10, 2021 at 17:39
3
$\begingroup$

Via integer linear programming, I found a solution that uses

28 kings, which is the maximum,

and all such kings can exit in

5 steps, which is the minimum because each of the 4 central squares requires at least 4 steps, and at most 2 of these squares can be occupied initially.

Initial configuration:

enter image description here

Covered squares:

enter image description here

Animation:

enter image description here

Improve this answer
$\endgroup$
0

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.