检查多米诺骨牌金字塔的有效性

Question

我在编码面试中遇到了这个问题，但无法找到一个好的解决方案。

你有6个多米诺骨牌。每个多米诺骨牌有2个半部分，每个半部分上有一定数量的点数。你正在构建一个3层的多米诺骨牌金字塔。底层需要3个多米诺骨牌，中层需要2个，顶层只需要1个。

多米诺骨牌被摆放的方式是，每一层都位于下一层的中心位置。以下是一个示意图：

         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

金字塔必须设置成这样，即每个多米诺骨牌的一半上的点数应与其下面的一半上的点数相同。这不适用于同一级别上的相邻多米诺骨牌。

有可能按照上述安排使用6个多米诺骨牌建造金字塔吗？多米诺骨牌可以自由排列和旋转。

编写一个函数，该函数接受一个包含12个整数的数组（例如arr[0]、arr[1]是第一个多米诺骨牌，arr[2]、arr[3]是第二个多米诺骨牌等），如果可以使用给定的6个多米诺骨牌创建金字塔，则返回“YES”，否则返回“NO”。

谢谢。

- CuriousProgrammer70184

---

暴力破解不够好吗？只有23040个选项来排列这些图块，所以几乎不需要时间。 - m69 ''snarky and unwelcoming''

Answer 1

你可以比暴力破解更好。我没有时间提供完整的答案。所以这只是一个提示。

计算每个数字出现的次数。至少应该有两个数字出现3次或以上，以此类推。如果不符合这些条件，则无解。在接下来的步骤中，您需要考虑数字在图块上的位置。

- ElKamina

Answer 2

只需遍历每个排列并检查每个排列。如果你找到了一个解决方案，那么你可以停止并返回“是”。如果你通过了所有的排列，那么就返回“否”。有6个位置，每个多米诺骨牌有2个旋转，因此总共有12*10*8*6*4*2 = 46080种排列。其中一半是彼此镜像的，所以我们要加倍我们必要的工作量，但我认为这不会困扰用户。我会先修复多米诺骨牌的方向，然后遍历所有位置的排列，再遍历方向的排列并重复。

所以我会将算法呈现为：

For each permutation of domino orientations
    For each permutation of domino positions
        if arr[0] == arr[3] && arr[1] == arr[4] && arr[2] == arr[7] && arr[3] == arr[8] && arr[4] == arr[9] && && arr[5] == arr[10] then return "YES"
return "NO"

在那个时候，我会问面试官接下来想要做什么。我们可以看一下优化、等价、实现或者转移到其他内容。

- Heath Raftery

---

只是挑刺一下：1210864*2 = 46,080。但当然有一个多米诺骨牌你不应该旋转，否则你会检查到镜像解决方案，所以实际上是23,040。 - m69 ''snarky and unwelcoming''

不是挑剔，而是我的双重错误！谢谢，现在已经纠正了。 - Heath Raftery

Answer 3

我们可以提出一个递归解决方案：

valid_row:
  if row_index < N - 1:
    copy of row must exist two rows below
  if row_index > 2:
    matching left and right must exist
    on the row above, around a center
    of size N - 3, together forming
    a valid_row
  if row_index == N - 1:
    additional matching below must
    exist for the last number on each side

一种解决方法可能是在沿路径追踪已选择的多米诺骨牌时进行回溯。鉴于匹配的限制条件，六个多米诺骨牌的金字塔应该会很快完成。

- גלעד ברקן

Answer 4

在我开始之前...问题存在歧义，可能面试官更感兴趣的是问题本身而不是答案。这个问题看起来是要求一种验证特定值排列是否有效的方法，除了其中的一句话：“是否可以从上述排列的6个多米诺骨牌中建立一个金字塔？多米诺骨牌可以自由排列和旋转。” 这意味着他们可能希望您也移动多米诺骨牌以找到解决方案。我将忽略这一点，并坚持简单地验证它是否是有效的排列。（如果需要，我会将数组拆分成对，并针对此代码暴力破解可能的排列的排列，以找到第一个有效的排列。）

我选择C#作为我的解决方案语言，但我故意避免使用任何可能使C#人更易读或更快速的语言特性，因为问题并不特定于语言，所以我希望这可以被其他喜欢其他语言的人阅读/转换。这也是我使用了许多命名变量的原因。

基本上，检查每一行是否在下一行中重复（偏移一个），并在到达最后一行时停止。

一旦算法发现失败，它就会退出。该算法可扩展到更大的金字塔；但不验证输入数组的大小：如果数组合理，则可以正常工作。

using System;

public static void Main()
{
    int[] values = new int[] { 3, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6 };
    bool result = IsDominoPyramidValid(values);
    Console.WriteLine(result ? "YES" : "NO");
}

private const int DominoLength = 2;

public static bool IsDominoPyramidValid(int[] values)
{
    int arrayLength = values.Length;

    int offset = 0;
    int currentRow = 1; // Note: I'm using a 1-based value here as it helps the maths
    bool result = true;
    while (result)
    {
        int currentRowLength = currentRow * DominoLength;

        // Avoid checking final row: there is no row below it
        if (offset + currentRowLength >= arrayLength)
        {
            break;
        }

        result = CheckValuesOnRowAgainstRowBelow(values, offset, currentRowLength);
        offset += currentRowLength;
        currentRow++;
    }

    return result;
}

private static bool CheckValuesOnRowAgainstRowBelow(int[] values, int startOfCurrentRow, int currentRowLength)
{
    int startOfNextRow = startOfCurrentRow + currentRowLength;
    int comparablePointOnNextRow = startOfNextRow + 1;
    for (int i = 0; i < currentRowLength; i++)
    {
        if (values[startOfCurrentRow + i] != values[comparablePointOnNextRow + i])
        {
            return false;
        }
    }

    return true;
}

- Richardissimo