Is it NP-hard to play international draughts correctly?

Question

Is the following problem NP-hard?

Given a board configuration for $n\times n$ international draughts, find a single legal move.

The corresponding problem for $n\times n$ American checkers (aka English draughts) is trivially solvable in polynomial time. There are three major differences between these two games.

The first and most significant difference is the “flying king” rule. In checkers, a king may jump over an adjacent opponent's piece into an empty square two steps away in any diagonal direction. In international draughts, a king may jump over an opponent's piece an arbitrary distance away by moving an arbitrary distance along a diagonal.

As in checkers, the same piece can be used to capture a series of pieces in a single turn. However, unlike checkers, captured pieces in international draughts are not removed until the entire sequence is over. The capturing piece may jump over or land in the same empty square multiple times, but it may not jump over an opponent's piece more than once.

Finally, both checkers and international draughts have a forced capture rule: If you can capture an opponent's piece, you must. However, the rules rules disagree when there are several options for multiple. In checkers, you may choose any maximal sequence of captures; in other words, you can choose any capture sequence that ends when the capturing piece cannot capture any more. In international draughts, you must choose the longest sequence of captures. Thus, my problem is equivalent to the following:

Given a board configuration for $n\times n$ international draughts, find a move that captures the maximum number of opposing pieces.

It would suffice to prove that the following problem is NP-complete. (It's obviously in NP.)

Given a board configuration for $n\times n$ international draughts involving only kings, can (and therefore must) one player capture all her opponent's pieces in a single turn?

The corresponding checkers problem can be answered in polynomial time; this is an entertaining homework exercise. The problem looks more similar to Demaine, Demaine, and Eppstein's analysis of Phutball endgames; a solution to the entertaining homework exercise appears at the end of their paper. A solution also appears in the FOCS 1978 paper by Frankel et al. that proves that playing checkers optimally is PSPACE-hard; see also Robson's 1984 proof that checkers is actually EXPTIME-complete.

Answer 1

OK, here's the reduction. Turns out you don't need planarity after all. Also, for "find a legal move", I take the decision question as "is move X legal?".

First, let's work instead with a game where pieces move orthogonally instead of diagonally. This game is equivalent (just look at the draughts board rotated 45 degrees) except for edge properties, which we will not use. We use two gadgets: merge / split and crossover. See http://www.hearn.to/draughts.pdf. We assume there is a single White king on the board to move. (No other piece will be able to capture any significant number of pieces.) It will move through the indicated corridors, capturing black pieces along the way.

First, merge: if the king enters on any of the N paths A (via capturing a black piece, not shown), it can exit at B. Likewise, if we reverse the gadget and it enters at B, capturing the shown piece, it can exit along any path A (again, capturing an external black piece). This is a single-use gadget (because the exit black piece can be captured only once).

Second, crossover. If the king enters via A (C), it can exit at B (D). It can't stop in the middle and change routes, because that would be a non-capturing move segment.

Now, given a directed graph, construct a corresponding game configuration as follows. For each vertex, construct a merge which feeds into a split. Route the split outputs to the merge inputs of the vertex gadgets (merge + split) corresponding to the vertices the exiting edges connect to, using crossovers as necessary. Start the king on an extra input to any vertex (with a black piece to capture to let it enter the vertex).

Finally, equalize all of the "edge lengths" by adding extra black pieces along the output / input pathways as needed. If there are V vertices, and k black pieces along each edge, then the king can capture 2V + kV + 1 pieces if and only if there is a Hamiltonian circuit of the corresponding graph. If the king has an alternative move available, capturing a simple chain of 2V + kV pieces, then determining whether that alternative move is legal is NP-complete.

Answer 2

Here's a possible alternative to Bob's reduction, this time from (undirected) Hamiltonian cycle. I'm not 100% confident that the details are correct—I've already found and fixed several issues—but I'm sure it can be massaged into a correct proof. As Bob points out, this reduction has a serious bug; the white king can easily stray from its canonical path through the board. This bug can be fixed by adding Bob's cross-over gadget at appropriate locations (I think), but then it's not significantly different from his reduction.

Let $G$ be an undirected graph with $n$ vertices and $m$ edges. Draw $G$ in the plane by placing its vertices at regularly spaced points on a line with slope $-1$, and drawing every edge as a horizontal segment plus a vertical segment, both above the vertex line.

Now we reduce this drawing to an $O(n^2)\times O(n^2)$ board (rotated 45 degrees) with $O(n^2+m)$ black checkers and one white king. We need three types of gadgets: corners, splitters, and hordes. A corner contains two black pieces that can only be captured together by changing the white king's direction. A $k$-splitter contains a single piece that must be captured in a particular direction, with $k$ special locations for the capturing king to jump into. Finally, a hoard is a large box full of $hn$ black pieces that must be captured in a particular order, for some large constant $h$. In the figures below, the gray circles are pieces that cannot be captured.

Now replace every vertex of degree $k$ with a hoard, connected to a horizontal $k$-splitter and a vertical $k$-splitter. For each edge $(i,j)$, place constant number of corners aligned with the splitters for hoard $i$ and hoard $j$. It's easy to arrange for the corners for different edges to lie at distinct $x$- and $y$-coordinates. Place the white king inside one of the hoards, in the position shown by the white circle above.

The white king can capture at least $hn^2+4n$ opposing pieces—every piece in every hoard, plus four additional edge pieces per vertex—if and only if the graph $G$ is Hamiltonian.

Answer 3

Now why didn't you pose this problem to me when I was working on my thesis?

OK, I have a reduction from Planar Directed Hamiltonian Cycle.