6
$\begingroup$

Let's say I have a bunch of cards or dominoes with one color on the left side of the card and another color on the right. (The two colors could be the same.) Dominoes can't be rotated so the color on each side is fixed. There is no limit on the number of colors and colors can be repeated on cards.

Dominoes are placed in a line, one after another.

The rule is, the color on the right hand side of a domino must match the color on the left hand side of the domino placed next to it.

The problem is, given a pool of dominoes, is it possible to put all of the dominoes in a line while following the rule? (I believe this is the same problem as given a group of matrices is it possible to multiply them all together.)

So for example given these dominoes: R-R, R-B, G-Y, GG-Y, Y-GG, R-R, R-B, ..., R-B, B-R, P-G is it possible to form a straight line with all adjoining sides having the same color.

My real question is this: Is the complexity of this problem (determining if it is possible to put all N dominoes in a line) NP?

$\endgroup$

migrated from cstheory.stackexchange.com Aug 14 '12 at 9:19

This question came from our site for theoretical computer scientists and researchers in related fields.

10
$\begingroup$

This is just the Eulerian path problem on a multigraph. The colors are the vertices, and the dominos are the edges. You want to know whether there is a path that goes passes through each edge exactly once. It's polynomial time, and you should be able to find the algorithm by googling "Eulerian path".

$\endgroup$
  • 1
    $\begingroup$ As the dominoes may not be rotated, it has to be directed edges (and a directed Eularian path), hasn't it? (Maybe that was assumed.) $\endgroup$ – Raphael Aug 14 '12 at 20:38
  • $\begingroup$ @Raphael is right: I should have said the directed Eulerian path problem. $\endgroup$ – Peter Shor Aug 15 '12 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy