c++ - 最长的多米诺骨牌链/序列

给定一组12个随机挑选的多米诺骨牌，我需要找到最长的多米诺骨牌链。我已经递归地生成了所有多米诺骨牌的可能性(使用0到12的面值有91种可能性)。一个多米诺骨牌由一个带有两个正方形的“砖”组成:[a | b]其中0 =
多米诺骨牌可以翻转以容纳比赛。例如，给定[8，4]，[9，4]可以翻转成对[8，4] [4，9]

以下(与该问题相关)方法可用于此类:

void flipEnds(); // Flips the domino
int getLeft() const;
int getRight() const;
bool hasBeenPlayed() const;
void setPlayed(bool value);

因此，此问题的样本数据如下:

 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 ]

这更多是一个数学问题，但是如何找到最长的多米诺骨牌链呢？我认为它必须递归完成。

最佳答案

多米诺骨牌序列可以表示为{＃3，Y}，{＃4，N}，{＃0，Y}，... ...第一个数字是您手中的多米诺骨牌号码，第二个数字是是否是否翻转。我们想检查所有可能的顺序，但是很早就删节显然是非法的。

假设您有一个testSequence(sequence)函数，该函数测试一个序列是否有效。
保留两个列表，一个是当前序列currentSeq，另一个是您尚未选择unused的多米诺骨牌。

递归可能像

checkAllSeq( currentSeq, unused ) {

   foreach( domino in unused ) {
      unused2 = unused - domino   // remove domino from unused list
      seq1 = currentSeq + {domino,true}   // add unfliped domino to sequence to test
      if( testSequence(seq1) ) {
          checkAllSeq(seq1,unused2)       // recurse
      }
      // now do it with the domino flipped
      seq2 = currentSeq + {domino,false}
      if( testSequence(seq2) ) {
          checkAllSeq(seq2,unused2)
      }
   }
}

我错过了几件事。这只是测试所有可能的序列，它对结果没有任何作用。