9
$\begingroup$

On an 8x8 checkerboard, there are 12 red kings and 1 black king. The kings behave as they would in any normal game of checkers, being able to move in any diagonal direction one space and jump any adjacent piece. If the king can jump another piece after a jump, he may do so an unlimited number of times.

If the kings can begin in any layout on the checkerboard, what is the minimum number of turns the black king needs to take to capture every single red king, and what would the initial board look like?

$\endgroup$
11
$\begingroup$

First of all, notice that you will only be on squares of one color. So we can simplify the board by taking only the squares of one color, and rotating the board diagonally.

enter image description here

Now, pieces move and jump horizontally and vertically.

Next, I will show a lower bound:

Say the king starts in a particular square. With only jumps, it can only visit every other column and every other row. That is, in the diagram below it can't leave the color it starts on.
enter image description here

Each of the colors is arranged the same way: eight dots, made up of a 2x3 rectangle and a single dot on each long side.

enter image description here
This arrangement only allows for nine total pieces to be jumped. So it cannot be done in one jump.

And now, the solution:

By the previous argument, it is not possible to do in one turn. It's also not possible to do in two: if one of the turns was a single step, you could just change the start or end position to make a one-turn solution. If both turns were entirely jumps, you could combine them into one turn.

But it is possible to do in three turns: a sequence of jumps, a step, and another sequence of jumps.

enter image description here
The black king starts on the left, then captures all the red pieces marked in black and ends on the space two cells right of its starting point. Then, it moves one step up, and its last turn captures all the red pieces marked in blue.

$\endgroup$
  • 3
    $\begingroup$ I had just finished drawing my 9+3 solution when you posted. :-( Nice explanation. $\endgroup$ – Jaap Scherphuis Oct 11 at 20:26
  • 1
    $\begingroup$ Yep, that's right. Checkmark incoming! $\endgroup$ – Bewilderer Oct 11 at 20:27
  • 1
    $\begingroup$ @Jaap I also had a 9 + 3 solution, if you still care to post $\endgroup$ – Bewilderer Oct 11 at 20:28
  • 2
    $\begingroup$ "If both turns were entirely jumps, you could combine them into one turn." -- This isn't quite so straightforward. Any captured pieces stay on the board (as defined in rules section 1.19: Capturing in General) until all the jumping is done, so one of the captured pieces could be blocking the next jump, which would then become possible on the next turn, after the blocking piece got removed at the end of the first turn. $\endgroup$ – Bass Oct 12 at 13:12
  • 1
    $\begingroup$ @Bass Interesting! The color argument still works for ruling out two turns of jumps only, but I wasn't aware that that was the official rule. (It seems like it allows the same piece to be captured multiple times in a single turn, though... is that allowed?) $\endgroup$ – Deusovi Oct 12 at 19:22
8
$\begingroup$

Here is a picture of my solution which uses

3

turns just like Deusovi's, but arranged differently.

The first turn captures 9 kings, then one move, followed by a triple capture. The numbers indicate the route of your king.
enter image description here

EDIT

I have now verified by computer that 12 is the maximum number of captures with this number of turns. With a few more turns it is possible to perform 14 captures. It is not possible to capture more, regardless of the number of turns you take, assuming the red kings remain stationary.

Here is the essentially unique way to capture 14 kings in 5 turns. It is simply Deusovi's solution with a move and two captures appended.
enter image description here
My computer program found 20 solutions for capturing 12 kings in 3 turns (not counting rotations/reflections). Six used 9+3 captures, six used 8+4, and eight used 7+5 captures.

$\endgroup$
  • $\begingroup$ Yeah, that's my exact solution $\endgroup$ – Bewilderer Oct 11 at 20:52
  • $\begingroup$ Don't you land on enemy piece 10 on turn 3? $\endgroup$ – Deusovi Oct 12 at 8:13
  • $\begingroup$ @Deusovi Oops! Back to the drawing board. $\endgroup$ – Jaap Scherphuis Oct 12 at 8:15

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.