2464. Checkers

The cows have taken up the game of checkers with a vengeance.Unfortunately, despite their infinite enjoyment of playing, they are terrible at the endgame. They want your help.

Given an NxN (4 <= N <= 30) checkboard, determine the optimal set of moves to end the game on the next move. Checkers move only on the ‘+’ squares and capture by jumping ‘over’ an opponent’s piece. The piece is removed as soon as it is jumped. See the example below

where N=8:

• • • • • • • • The K’s mark Bessie’s kings; the o’s represent the
• • • • • • • • opponent’s checkers. Bessie always moves next. The
• • • K - + - + Kings jump opponent’s checkers successively in any
• • • • • • • • diagonal direction (and removes pieces when jumped).

• o - o - + - +

• • K - + - + - For this board, the solution requires the lower left

• o - + - + - + King to jump successively across all three of the

• • K - + - K - opponents’ checkers, thus ending the game (moving K

marked as >K<):

Original

• • • • • • • +
• • • • • • • -
• • • K - + - +
• • • • • • • -

• o - o - + - +

• • K - + - + -

• o - + - + - +

• ->K<- + - K -

After move 1

• • • • • • • +
• • • • • • • -
• • • K - + - +
• • • • • • • -

• o - o - + - +

K<- K - + - + -

• • • • • • • +
• • • • • • K -

After move 2

• • • • • • • +
• • • • • • • -
• • • K - + - +

• ->K<- + - + -

• • • o - + - +
• • K - + - + -
• • • • • • • +
• • K - + - K -

After move 3

• • • • • • • +
• • • • • • • -
• • • K - + - +
• • • • • • • -
• • • • • • • +
• • K ->K<- + -
• • • • • • • +
• • K - + - K -

The moves traversed these squares:

1 2 3 4 5 6 7 8 R C

1 - + - + - + - + start: 8 3

2 + - + - + - + - move: 6 1

3 - + - K - + - + move: 4 3

4 + - * - + - + - move: 6 5

5 - o - o - + - +

6 * - K - * - + -

7 - o - + - + - +

8 + - K - + - K -

Write a program to determine the (unique, as it turns out) game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board.