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

Question

我需要找到最长的多米诺骨牌链，给定一组 12 个随机挑选的多米诺骨牌。我已经递归地生成了多米诺骨牌的所有可能性(使用 0 到 12 的面值有 91 种可能性)。多米诺骨牌由一 block “砖 block ”和上面的两个正方形组成:[a|b]，其中 0 =< a, b <= 12。因此，多米诺骨牌的示例可以是 [12, 0] 或 [6, 3]等等。如果相邻的两半具有相同的值，则多米诺骨牌可以连接。

多米诺骨牌可以翻转以适应比赛。例如，给定 [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 ]

这更像是一道数学题，但我怎样才能找到最长的多米诺骨牌链呢？我认为它必须递归完成。

Answer 1

多米诺骨牌序列可以表示为 {#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)
      }
   }
}

我错过了一些事情。这只是测试所有可能的序列，它不会对结果做任何事情。