<p>Here's a possible alternative to Bob's reduction, this time from (undirected) Hamiltonian cycle.  <strike>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.</strike> <b>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 </b>(I think)<b>, but then it's not significantly different from his reduction.</b></p>

<p>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.</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/OxUqC.png" alt="corner gadget"></p>

<p><img src="https://i.sstatic.net/fjqlI.png" alt="horizontal 4-splitter gadget"></p>

<p><img src="https://i.sstatic.net/l1vp1.png" alt="hoard gadget"></p>

<p>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.</p>

<p><img src="https://i.sstatic.net/DYSh3.png" alt="one edge"></p>

<p>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.</p>

CC BY-SA 2.5
2010-10-08T01:40:44.950Z
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
CC BY-SA 2.5
2010-10-08T04:03:50.433Z
The second problem is easy to fix: move the starting location for the king deeper inside the horde.
Jeffε
CC BY-SA 2.5
2010-10-08T04:04:38.803Z
But the first problem is more serious.  I guess we need your crossover gadgets after all.  Drat!
Jeffε
CC BY-SA 2.5
2010-10-08T04:52:15.763Z
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
CC BY-SA 2.5
2010-10-07T22:05:42.270Z
2010-10-08T04:10:28.097Z
2010-10-08T04:10:28.097Z
Jeffε
<p>Now why didn't you pose this problem to me when I was working on my thesis?</p>

<p>OK, I have a reduction from Planar Directed Hamiltonian Cycle.</p>

CC BY-SA 2.5
2010-10-06T23:34:01.177Z
Do tell! (Can you briefly describe the reduction?)
Ryan Williams
CC BY-SA 2.5
2010-10-07T02:07:31.257Z
Sorry, Bob; didn't think of it then.  Yes, please describe (or link to) the reduction!
Jeffε
CC BY-SA 2.5
2010-10-07T08:43:21.977Z
This is not really an answer.
Dave Clarke
CC BY-SA 2.5
2010-10-07T15:46:40.237Z
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
CC BY-SA 2.5
2010-10-07T17:19:00.423Z
You need 100 reputation to add a comment.  It's a feechur.
Jeffε
CC BY-SA 2.5
2010-10-07T17:33:08.787Z
@JeffE: Nitpicking: it is 50, not 100.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-06T21:23:08.483Z
2010-10-06T22:33:04.077Z
2010-10-06T22:33:04.077Z
Bob Hearn
<p>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?".</p>

<p>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 <a href="http://www.hearn.to/draughts.pdf">http://www.hearn.to/draughts.pdf</a>. 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.</p>

<p>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).</p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-07T16:16:33.403Z
Nice reduction!
Jeffε
CC BY-SA 2.5
2010-10-07T17:18:05.667Z
But can you answer the second question?  Is winning in one move NP-hard?
Jeffε
CC BY-SA 2.5
2010-10-07T17:26:55.273Z
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
CC BY-SA 2.5
2010-10-07T17:32:04.780Z
I guess it would also take some extra navigational machinery outside the corridors, but it ought to be doable.
Bob Hearn
CC BY-SA 2.5
2010-10-07T07:32:32.447Z
2010-10-07T07:32:32.447Z
Bob Hearn
<p>Is the following problem NP-hard?</p>

<blockquote>
  <p>Given a board configuration for $n\times n$ <a href="http://en.wikipedia.org/wiki/International_draughts">international draughts</a>, find a single legal move.</p>
</blockquote>

<p>The corresponding problem for $n\times n$ <a href="http://en.wikipedia.org/wiki/English_draughts">American checkers (aka English draughts)</a> is trivially solvable in polynomial time.  There are three major differences between these two games.</p>

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

<p>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.</p>

<p>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 <em>maximal</em> 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 <em>must</em> choose the <em>longest</em> sequence of captures.  Thus, my problem is <em>equivalent</em> to the following:</p>

<blockquote>
  <p>Given a board configuration for $n\times n$ <a href="http://en.wikipedia.org/wiki/International_draughts">international draughts</a>, find a move that captures the maximum number of opposing pieces.</p>
</blockquote>

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

<blockquote>
  <p>Given a board configuration for $n\times n$ <a href="http://en.wikipedia.org/wiki/International_draughts">international draughts</a> <em>involving only kings</em>, can (and therefore must) one player capture <em>all</em> her opponent's pieces in a single turn?</p>
</blockquote>

<p>The corresponding checkers problem can be answered in polynomial time; this is an entertaining homework exercise.  The problem looks more similar to <a href="http://arxiv.org/abs/cs/0008025">Demaine, Demaine, and Eppstein's analysis of Phutball endgames</a>; a solution to the entertaining homework exercise appears at the end of their paper.  A solution also appears in the FOCS 1978 paper by <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1978.36">Frankel et al.</a> that proves that playing checkers optimally is PSPACE-hard; see also <a href="http://dx.doi.org/10.1137/0213018">Robson's 1984 proof</a> that checkers is actually EXPTIME-complete.</p>

CC BY-SA 2.5
2010-10-05T19:15:16.113Z
typo ? "it's obviously in P" - maybe you mean "in NP" ? Also, WHERE do you get these questions ?
Suresh Venkat
CC BY-SA 2.5
2010-10-05T19:18:19.323Z
Yep, fixed.  Also reworded the problem; it's not clear that the number of legal moves from a given position is only polynomial.
Jeffε
CC BY-SA 2.5
2010-10-05T19:22:14.990Z
This one comes out of writing up a solution for the "entertaining homework exercise".
Jeffε
CC BY-SA 2.5
2010-10-07T20:43:26.027Z
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
<cc.complexity-theory><np-hardness><open-problem><board-games>
Is it NP-hard to play international draughts correctly?
Jeffε
# Is it NP-hard to play international draughts correctly?

(Asked by: username_0 on 2010-10-05)

Is the following problem NP-hard?

> Given a board configuration for $n\times n$ [international draughts](http://en.wikipedia.org/wiki/International_draughts), find a single legal move.

The corresponding problem for $n\times n$ [American checkers (aka English draughts)](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://arxiv.org/abs/cs/0008025); 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.](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1978.36) that proves that playing checkers optimally is PSPACE-hard; see also [Robson's 1984 proof](http://dx.doi.org/10.1137/0213018) that checkers is actually EXPTIME-complete.

**Tags:** cc.complexity-theory, np-hardness, open-problem, board-games

> **Comments:**
> **username_1**: typo ? "it's obviously in P" - maybe you mean "in NP" ? Also, WHERE do you get these questions ?  
> **username_0**: Yep, fixed.  Also reworded the problem; it's not clear that the number of legal moves from a given position is only polynomial.  
> **username_0**: This one comes out of writing up a solution for the "entertaining homework exercise".  
> **username_2**: 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.  

---

## 3 answers

### Answer by username_2 on 2010-10-07. Score: 27 | Accepted answer

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.

> **Comments:**
> **username_0**: Nice reduction!  
> **username_0**: But can you answer the second question?  Is winning in one move NP-hard?  
> **username_2**: 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.  
> **username_2**: I guess it would also take some extra navigational machinery outside the corridors, but it ought to be doable.  

---

### Answer by username_0 on 2010-10-07. Score: 5

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](https://i.sstatic.net/OxUqC.png)

![horizontal 4-splitter gadget](https://i.sstatic.net/fjqlI.png)

![hoard gadget](https://i.sstatic.net/l1vp1.png)

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](https://i.sstatic.net/DYSh3.png)

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.

> **Comments:**
> **username_2**: 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.  
> **username_0**: The second problem is easy to fix: move the starting location for the king deeper inside the horde.  
> **username_0**: But the first problem is more serious.  I guess we need your crossover gadgets after all.  Drat!  
> **username_2**: 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.  

---

### Answer by username_2 on 2010-10-06. Score: 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.

> **Comments:**
> **username_3**: Do tell! (Can you briefly describe the reduction?)  
> **username_0**: Sorry, Bob; didn't think of it then.  Yes, please describe (or link to) the reduction!  
> **username_4**: This is not really an answer.  
> **username_2**: 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.  
> **username_0**: You need 100 reputation to add a comment.  It's a feechur.  
> **username_5**: @JeffE: Nitpicking: it is 50, not 100.  

---

