Longest domino chain/sequence <p>I have run into an issue with an assignment of mine and I would really appreciate some tips/help on this matter! I have also searched extensively for help on this problem, but I could not find any solutions.</p> <p>I need to find the longest chain of dominoes possible, given a set of 12 randomly picked dominoes. I've already recursively generated all possibilities of dominoes (there are 91 possibilities using face values of 0 to 12). A domino consists of one "brick" with two squares on it: [a|b] where 0 =&lt; a,b &lt;= 12. Thus, an example of a domino could be [12,0] or [6,3] etc. Dominoes may be connect if adjacent halves have the same value.</p> <p>Dominoes may be flipped to accommodate a match. For example, given [8,4], [9,4] could be flipped to make the pair [8,4][4,9]</p> <p>The following (relevant to this question) methods are available for this class:</p> <pre><code>void flipEnds(); // Flips the domino int getLeft() const; int getRight() const; bool hasBeenPlayed() const; void setPlayed(bool value); </code></pre> <p>So, sample data for this problem would be as follows:</p> <pre><code> myDomino #0: [1 12 ] myDomino #1: [0 5 ] myDomino #2: [7 9 ] myDomino #3: [2 7 ] myDomino #4: [7 12 ] myDomino #5: [4 8 ] myDomino #6: [8 10 ] myDomino #7: [3 11 ] myDomino #8: [11 12 ] myDomino #9: [10 11 ] myDomino #10: [2 9 ] myDomino #11: [2 4 ] </code></pre> <p>This is more of a math problem, but how can I find the longest chain of dominoes? I assume it must be done recursively. </p> <p>Thanks in advance!</p>