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?