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.

$\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 Jan 10 at 22:40
  • $\begingroup$ Yes, it's a standard 8x8 board. $\endgroup$ – FlanMan Jan 10 at 23:40
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.

$\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 Jan 10 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 Jan 10 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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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