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.

  • typo ? "it's obviously in P" - maybe you mean "in NP" ? Also, WHERE do you get these questions ? – Suresh Venkat Oct 5 '10 at 19:15
  • Yep, fixed. Also reworded the problem; it's not clear that the number of legal moves from a given position is only polynomial. – Jeffε Oct 5 '10 at 19:18
  • This one comes out of writing up a solution for the "entertaining homework exercise". – Jeffε Oct 5 '10 at 19:22
  • I guess the unspoken additional question here is, what is the complexity of the game itself (determining whether one player can win)? Is it EXPTIME-complete, as checkers is? Probably, but the proof for checkers is quite complicated. – Bob Hearn Oct 7 '10 at 20:43
up vote 23 down vote accepted

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.

  • 2
    Nice reduction! – Jeffε Oct 7 '10 at 16:16
  • But can you answer the second question? Is winning in one move NP-hard? – Jeffε Oct 7 '10 at 17:18
  • Maybe... I think that the gadgets could be modified so that after completing a Hamiltonian circuit, the king could then capture all of the black pieces on the "wires". The merge/split internal pieces would still have to be captured during the Hamiltonian circuit, so it would still be NP-hard. The idea would be to open gaps in the corridors adjacent to the black pieces, that would allow the corridors to be crossed, but not exited from the inside. – Bob Hearn Oct 7 '10 at 17:26
  • I guess it would also take some extra navigational machinery outside the corridors, but it ought to be doable. – Bob Hearn Oct 7 '10 at 17:32

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.

corner gadget

horizontal 4-splitter gadget

hoard gadget

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.

one edge

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.

  • Very nice. But I do see a couple of problems, one of which my reduction has as well. First, when the king exits a corner, it can stop anywhere, potentially allowing it to enter another corner inappropriately. Second, there's nothing to force the king to return to the initial vertex; it could end on any vertex. Mine has the same problem, but it is easily fixed for either reduction, by adding an appropriate extra piece to capture inside the start vertex. – Bob Hearn Oct 8 '10 at 1:40
  • The second problem is easy to fix: move the starting location for the king deeper inside the horde. – Jeffε Oct 8 '10 at 4:03
  • But the first problem is more serious. I guess we need your crossover gadgets after all. Drat! – Jeffε Oct 8 '10 at 4:04
  • I think removing the exit black piece from the corner gadget, and adding a black piece on every arm of the input splitter for each vertex, might also do the trick. – Bob Hearn Oct 8 '10 at 4:52

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.

  • 1
    Do tell! (Can you briefly describe the reduction?) – Ryan Williams Oct 6 '10 at 23:34
  • Sorry, Bob; didn't think of it then. Yes, please describe (or link to) the reduction! – Jeffε Oct 7 '10 at 2:07
  • This is not really an answer. – Dave Clarke Oct 7 '10 at 8:43
  • 1
    No... I thought I was adding a comment at the time. Now, I don't see how to add a comment to the main post. – Bob Hearn Oct 7 '10 at 15:46
  • You need 100 reputation to add a comment. It's a feechur. – Jeffε Oct 7 '10 at 17:19

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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