想象一个多维多米诺骨牌的无序列表，其中每一对多米诺骨牌都是独一无二的。如何优雅高效地解决多米诺骨牌？

Question

作为几何算法的软件开发人员，我运行多次遇到以下问题，但对我解决它的方式从未真正满意。

问题陈述

想象一下 3D 笛卡尔 space 中的多米诺骨牌，其面具有 3D 坐标 (x, y, z)。这个游戏的一个附加条件是，每个坐标在游戏中只存在一次，并且恰好写在两个石头的面上。一旦找到一对匹配的面孔，就会找到一对多米诺骨牌。路径被定义为多米诺骨牌的有序列表，其中列表中的每两个成对相邻元素（多米诺骨牌）形成匹配。一场多米诺骨牌可以有多条路径。

例子

玩排序游戏前后的例子如下：

第 1 场比赛：单路作为结果。

游戏 2：结果为多条路径。

这个问题是否有 a) 高效和 b) 优雅的解决方案？

使用 while 循环的简单解决方案

我最好的猜测如下：

Let the input list of dominos be called list.
Let the currently forming path be an ordered list called cur_path.
Let the resulting list of paths be called results.

While (list is not empty)
  If (cur_path is empty)
    Draw random piece of domino from list and put into cur_path.
    Continue
  Else
    // Search equals finding a match for open ends of cur_path,
    // i.e. the first and the last domino in cur_path.
    Search in list for matching domino
    If (Found matching domino)
      Draw found piece from list and put at correct position into cur_path
    Else
      // We have not found a match amongst all residual dominos.
      // Store current path into result paths and begin new.
      Store cur_path in results.
      Clear variable cur_path.
      Continue

return results

您会看到我在大约 1 秒内对所有元素进行了 while 循环。 O(n²)。这个解决方案有两种我不喜欢的方法。首先，我不喜欢 while 循环，因为它们总是受限于不确定的条件。其次，我不喜欢我忽略多米诺骨牌的几何信息来缩小搜索范围 space 匹配的方式。您是否认为像边界体积层次结构方法这样的排序层次结构对于解决这个问题来说太过分了？

Answer 1

这在 O(n) 中是可以解决的。

这里是未经测试的 Python:

    tiles_at = {} # will map coordinates to tiles.
    for tile in all_tiles:
        for face in tile.faces:
            if face not in tiles_at:
                tiles_at[face] = [tile]
            else:
                tiles_at[face].append(tile)

    is_used = set() # will hold the used tiles
    paths = [] # will hold the final answer. Does not find loops.
    for face, tiles in tiles_at.items():
        if 1 == len(tiles) and tiles[0] not in is_used:
            # Found the start of a path.
            is_used.add(tiles[0])
            last_face = face
            last_tile = tiles[0]
            if face != tiles[0].faces[0]:
                last_tile = last_tile.flip()
            path = [last_tile]

            # Find the path
            while True:
                # Find the unused face.
                last_face = last_tile.faces[1]

                # Find the next tile in the path, if any.
                if 1 == len(tiles_at[last_face]):
                    break # EXIT LOOP AT END OF PATH
                elif last_tile == tiles_at[last_face][0]:
                    last_tile = tiles_at[last_face][1]
                else:
                    last_tile = tiles_at[last_face][0]
                # We used this tile
                is_used.add(last_tile)
                if last_face == last_tile.faces[1]:
                    last_tile = last_tile.flip()
                path.append(last_tile)
        # and record the path
        paths.append(path)

这个想法是 O(n) 扫描以将图块的所有面添加到哈希中。 O(n) 扫描以找到所有可能的起点，并且对于每个起点扫描路径，该路径将在所有路径上访问每个 O(n) 块恰好一次。

合起来就是 O(n)。

想象一个多维多米诺骨牌的无序列表，其中每一对多米诺骨牌都是独一无二的。如何优雅高效地解决多米诺骨牌？

Imagine an unordered list of multidimensional domino stones, where each pair of dominos is unique. How to elegantly and efficiently solve dominos?

sorting

algorithm

问题陈述

例子

使用 while 循环的简单解决方案