c++ - Longest domino chain/sequence -

c++ - Longest domino chain/sequence -

i have run issue assignment of mine , appreciate tips/help on matter! have searched extensively help on problem, not find solutions.

i need find longest chain of dominoes possible, given set of 12 randomly picked dominoes. i've recursively generated possibilities of dominoes (there 91 possibilities using face values of 0 12). domino consists of 1 "brick" 2 squares on it: [a|b] 0 =< a,b <= 12. thus, illustration of domino [12,0] or [6,3] etc. dominoes may connect if adjacent halves have same value.

dominoes may flipped accommodate match. example, given [8,4], [9,4] flipped create pair [8,4][4,9]

the next (relevant question) methods available class:

void flipends(); // flips domino int getleft() const; int getright() const; bool hasbeenplayed() const; void setplayed(bool value);

so, sample info problem follows:

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 ]

this more of math problem, how can find longest chain of dominoes? assume must done recursively.

thanks in advance!

a sequence of dominos might represented {#3,y}, {#4,n}, {#0,y}, ... first number number of domino in hand , sec whether flipped or not. want check every possible sequence, prune illegal 1 early.

lets assume have function testsequence(sequence) tests sequence valid. maintain 2 lists, 1 of current sequence currentseq, , 1 of dominos have not yet chosen unused.

a recursion might like

checkallseq( currentseq, unused ) { foreach( domino in unused ) { unused2 = unused - domino // remove domino unused list seq1 = currentseq + {domino,true} // add together unfliped domino sequence test if( testsequence(seq1) ) { checkallseq(seq1,unused2) // recurse } // domino flipped seq2 = currentseq + {domino,false} if( testsequence(seq2) ) { checkallseq(seq2,unused2) } } }

i've missed few things out. tests possible sequences not result.

c++ recursion sequence chain