最长的多米诺骨牌链/序列 [英] Longest domino chain/sequence

问题描述

给定一组 12 个随机挑选的多米诺骨牌，我需要找到可能的最长多米诺骨牌链.我已经递归地生成了多米诺骨牌的所有可能性(使用 0 到 12 的面值有 91 种可能性).多米诺骨牌由一块砖"组成，上面有两个正方形:[a|b] 其中 0 =

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 =< a, b <= 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.

多米诺骨牌可以翻转以适应比赛.例如，给定 [8, 4], [9, 4] 可以翻转成对 [8, 4][4, 9]

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]

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

The following (relevant to this question) methods are available for this class:

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

所以，这个问题的样本数据如下:

So, sample data for this problem would be as 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 is more of a math problem, but how can I find the longest chain of dominoes? I assume it must be done recursively.

推荐答案

多米诺骨牌序列可能表示为 {#3,Y}, {#4,N}, {#0,Y}, ...第一个数字是您手中的多米诺骨牌号码，第二个数字是是否翻转.我们想检查每一个可能的序列，但尽早修剪明显非法的序列.

A sequence of dominos might be represented as {#3,Y}, {#4,N}, {#0,Y}, ... The first number is the number of the domino in your hand and the second is whether it is flipped or not. We want to check every possible sequence, but prune obviously illegal one early.

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

Lets assume you have a function testSequence(sequence) which tests is a sequence is valid. Keep two lists, one of the current sequence currentSeq, and one of the dominos you have not yet chosen 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)
      }
   }
}

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

I've missed a few things out. This just tests all possible sequences it does not do anything with the result.

这篇关于最长的多米诺骨牌链/序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！