用 C++ 和“跳舞链接”解决五格骨牌谜题

• 下载源代码 - 103 KB
• 下载 exe - 88 KB

引言

整理旧文件时，我发现了很多代码。这是个寻找拼图游戏解决方案的程序。我不记得为什么写的了，当时觉得是个有趣的挑战。

问题

有一个拼图。你必须把所有块放进一个正方形的长方形里。你可以翻转和旋转块。

解决方案

我最初是用地板块数组来写的。每个适合的块（没有孔）都会成为一个新的地板。这很慢，而且占用了大量资源（用于分配数组）。

所以，我重写了一个算法，可以在同一个地板上向前和向后移动，添加和移除块。

想法很简单。你放第一个块（遍历块的数组）。如果可以，就放下一个。如果不行，就退回去，从数组中移除它。唯一要记住的是块的顺序，这样当你退回去时，可以继续放下一个块。

代码 - 加载块

有三个类用于处理块

• CPiezas：负责从 XML 文件加载所有块的类。XML 格式很简单，有一个根节点 PIEZAS，下面有子节点 PIEZA。

每个 PIEZA 节点有这些属性

• Nombre：块的名称。
• Ancho：块的宽度。
• Alto：块的高度。
• Contenido：内容。使用 0 表示空格，1 表示块的内容，它根据宽度和高度表示块。例如，Ancho="4" Alto="2" Contenido="11110010" 应该被读取为

1111
0010

CPiezas 类还有一个数组（映射），里面包含它从 XML 加载的所有块（CPiezaInfo）。

• CPiezaInfo：包含块的信息以及它所有可能的旋转和翻转。它包含一个 CPieza 向量。向量中的每个 CPieza 代表块的一种可能的旋转或翻转状态。
• CPieza：这个类的每个项代表块的一种旋转或翻转状态。它有颜色以及旋转和翻转的方法。由于有 8 种可能的旋转和翻转组合（4 种旋转，2 种翻转），ID 同时包含块 ID 和状态。

例如，ID 26 表示块 ID:2，状态:6。所有可能的状态都在枚举 TipoPieza 中定义。这个类继承自 CFillRectangle，其中包含通用的长方形操作。

代码 - 长方形操作

CFillRectangle 类负责在长方形内标记方块。它以效率为目标编写（考虑到大型地板向量）。所以，它使用二进制逻辑来分配方块。因此，在一个字节中，8 个方块被用作标记 1 或 0。这个类同时用于地板和块。

代码 - 地板

CBoard 类继承自 CFillRectangle，代表放置块的地方。变量有

• Fila：代表放置块的当前行。
• Columna：代表放置块的当前列。
• nodos：一个包含 12 个 CNodo 类型项的数组。每个 CNodo 代表地板上某个位置的一个块。每个 CNodo 还有一个索引变量，用于移动到块数组中的下一个块。
• inodo：代表当前正在处理的 nodos 数组中的位置（0-11）。
• nodeseval：一个计数器，用于记录正在尝试的每个块。
• mappiezas：一个映射，将每个块 ID 与 CPieza 对象关联起来。
• vecpiezas：一个向量，用于通过 CNodo 的索引变量遍历块。
• mappiezasdisp：一个映射，表示块是否在地板上（块是否可用）。
• piezas：块的指针。

方法有

• TieneHuecos：检查地板是否有任何未占用单元格。此方法未使用，可以删除。
• MarcarCasillas：给定一个块（CPieza 类型的参数），它在当前地板位置（变量 Fila 和 Columna）标记或取消标记对应于该块的所有单元格。
• AsignarProxColumnaFila：它将地板变量 Fila 和 Columna 分配给从下到上、从左到右的第一个未标记单元格。
• CorrespondePieza：检查是否可以在当前地板单元格（Fila 和 Columna）放置一个块。
• InitPiezasDisp：加载所有块数组（vecpiezas、mappiezasdisp、mappiezas）。
• Init：加载 nodos 的 12 个节点并将其设置为 null。
• MarcarPiezaInfo：给定一个块，它在映射中（所有位置）标记或取消标记它们为可用或不可用。
• GetIndexFirstAvailable：获取向量 vecpiezas 中下一个可用的块（检查 mappiezasdisp）。

代码 - 求解器

CPuzzleSolver 类是算法发生的地方。“soluciones”变量用于存储解决方案（12 个 CNodo 的数组）。变量 solman 是 CSolutionMan 类型的对象，用于过滤重复的解决方案。SolvePuzzle 方法初始化地板和数组，并执行 HacerMovida 方法，直到用户取消或算法完成。HacerMovida 的描述

if (Current piece index in current node is last + 1, go backwards)
{
    Put null into current node.
    Move backwards (go to the node before, index of nodes -1)
 
    if (There are no more nodes before)
        End Process.
    Position the board in the coordinates of the current node.
 
    Remove the piece of the current node from 
           the board (we need to move to the next piece).
    Add the piece of current node to the list of available pieces.
 
    Move to the next available piece in the current node.
}
else
{
    if (Add the piece of the current node to the board)
    {
        Add the piece to the board (mark cells).
        Remove the piece from the list of available pieces.
        Assign the current node the coordinates of the board.
        if (not find next free cell in the board, the board is full, solution)
        {
            Add Solution
            Remove piece from board
            Add piece to list of available pieces
            Move to the next available piece in the current node.
        }
        else
        {
            Move to the next node (which is null).
            Assign the node the first available piece from the list.
        }
    }
    else
        Move to the next available piece in the current node.
}

代码 - 删除重复项

CSolutionMan 类使用 CSolPuntos 类型的数组来删除重复的解决方案。CSolPuntos 类与地板（CFillRectangle）不同，它包含一个块 ID 而不是布尔值（1 或 0）。

想法是，为了检查重复项，在长方形上旋转或翻转点比旋转或翻转块要容易得多。

算法是

• 遍历解决方案（i）。
• 对于每个解决方案，旋转、翻转、旋转、翻转（结果：3 个新解决方案）。
• 将每个剩余的解决方案（n-i 个解）与上一步的三个解决方案进行比较。
• 如果相等，则移除解决方案。

算法 X

有一个更快的算法来解决这个问题，称为 Donald Knuth 开发的算法 X。该算法最高效的实现是舞动链。

该算法解决的问题是“精确覆盖”。基本上，它所做的是，给定一个由 1 和 0 组成的矩阵，找到恰好覆盖所有值为 1 的列的所有行。

	A	B	C	D
P	0	1	0	1
Q	1	0	0	0
R	1	1	0	0
S	0	0	1	0
T	0	0	1	1

在该示例中，行 P、Q 和 S 以及行 R 和 T 是给定矩阵的解决方案。这看起来很简单，但对于更大的矩阵，找到所有解决方案需要时间。

算法 X 由 4 个步骤组成，这些步骤一直执行，直到矩阵为空（找到解决方案）或某个列全为 0（不成功）。每次迭代都会减小矩阵的大小。

• 找到 1 最少的列（如果有多个，选择第一个）。例如，A 列。
• 对于该列，选择一行，使其与该列的交集为 1。记住这一行。例如，Q 行。
• 对于该行，选择该行值为 1 的列，对于这些列，移除该列值为 1 的所有行（在此示例中，Q 行的唯一 1 在 A 列，因此移除 Q 和 R 行）。
• 移除之前选择的列（在此示例中为 A）。

执行这些步骤后，矩阵 A 列被移除，Q 行和 R 行也被移除

	B	C	D
P	1	0	1
S	0	1	0
T	0	1	1

接下来我们选择 B 列，并从该列中选择P 行。我们记住这一行。从 P 行，我们选择 B 列和 D 列（P 行值为 1）。B 列和 D 列在 T 行和 P 行（当然）有 1。因此，P 行和 T 行被移除，B 列和 D 列也被移除。

	C
S	1

这里我们选择 C 列（我们选择不多），并选择S 行。S 行和 C 列消失，我们得到一个空矩阵（成功）。选择的行是 Q、P、S。这是一个解决方案。

继续，我们选择原始矩阵中（A 列）1 最少的列的下一行 1。该行是R 行。R 行在 A 列和 B 列有 1，所以我们选择这些列。这些列在 P、Q 和 R 行有 1。因此，P、Q 和 R 行被移除，A 列和 B 列也被移除。

	C	D
S	1	0
T	1	1

现在 1 最少的列是 D 列。第一行有 1 的是 T。所以我们选择T 行。T 行在 C 列和 D 列有 1，这些列在所有行都有 1，所以我们又得到一个空矩阵（成功）。解决方案是 R 行和 T 行。

算法 X 的实现，舞动链

对于大型矩阵，移除和恢复行和列的操作非常耗时。此外，在大多数问题中，这些矩阵是“稀疏”的，这意味着有很多 0 和很少的 1。所以，只表示 1 是个好主意。

首先我们介绍双向循环链表的概念

每个项有两个指针，一个指向左，一个指向右。最后一项指向第一项。

遍历列表向右移动，从 Item2 开始

For (i = Item1.Right; i != Item1.Right; i = i.Right)

使用 Item2 移除一个项（例如 Item2）

Item2.Right.Left = Item2.Left

在这里，我们将 Item3.Left（Item2.Right.Left）指向 Item2.Left（Item1），这样它就会“跳过”Item2。Item2.Right 是 Item3。Item2.Left 是 Item1。

Item2.Left.Right = Item2.Right

在这里，我们将 Item1.Left（Item2.Left.Right）指向 Item2.Right（Item3），这样它就会“跳过”Item2。Item2.Left 是 Item1。Item2.Right 是 Item3。

添加一个项（例如 Item23），放在 Item2 的右侧（在 Item2 和 Item3 之间），只使用 Item2

Item2.Right.Left = Item23
Item2.Right = Item23

在这里，我们将 Item3.Left 指向 Item23，将 Item2.Right 指向 Item23。Item2.Right 是 Item3。

Item23.Right = Item2.Right
Item23.Left = Item2

在这里，我们将 Item23.Right 指向 Item3（Item2.Right），将 Item23.Left 指向 Item2。

现在，算法 X 的问题可以用每个 1 表示为一个节点，并且链表在矩阵中交错，节点指向上下左右。表示示例问题

在此图中，S 行的节点在行中是单独的，所以它左右都指向自己。每个节点还有一个指向其列头的指针（在算法中）。

将五连块问题表示为精确覆盖

我们可以将棋盘表示为需要填充的 60 个“单元格”。每个块与其方向，在棋盘的特定位置“覆盖”某些“单元格”。例如，T 块，从位置 1 开始，覆盖单元格 1、2、3、8 和 14。

所以，我们可以创建一个有 60 列的网格，并表示每个块在所有方向上的每个位置（在棋盘上）。这是一个相当大的矩阵。但是每个块只能放在棋盘上一次，所以我们需要确保它不会重复。为了做到这一点，我们添加 12 列（每块一列），并在相应的块中放一个 1。如果 T 块是第 3 块，那么在位置 1、2 和 3 开始用 T 块填充的三块棋盘的表示将是

当然，有 60 个棋盘列，我只表示了 17 个，其余列在此示例中具有 0 值。对于这个问题，它是一个稀疏矩阵。每行有 72 个值，只有 6 个值为 1（8%）。如果我们只考虑块的 2 种（8 种方向中的）方向以消除微不足道的解决方案，则矩阵有 1864 行。

微不足道的解决方案

为了避免旋转或翻转的解决方案，你可以只使用一块的 2 种方向（总共有 8 种方向）。

舞动链，代码

两个最重要的方法是 cover 和 uncover（或 remove 和 restore）。给定一个列，它们会移除该列以及该列中有项的所有行。从视觉上看，这就像移除一个电视天线。

void CDLinks::Remove(CColumnHeader* hcol)
{
    //Remove the header
    hcol->right->left = hcol->left;
    hcol->left->right = hcol->right;

    //Iterate all the nodes in the column, going down.
    for (CNode* row = hcol->down; row != hcol; row = row->down)
    {
        //Remove the row, for each node, disconect vertically (zipper).
        for (CNode* col = row->right; col != row; col = col->right)
        {
            //Remove node vertically
            col->down->up = col->up;
            col->up->down = col->down;

           col->header->len--;
        }
    }
}

void CDLinks::Restore(CColumnHeader* hcol)
{
    //Iterate all the nodes in the column, going down.
    for (CNode* row = hcol->up; row != hcol; row = row->up)
    {
        //Reconnect vertically (add the row)
        for (CNode* col = row->left; col != row; col = col->left)
        {
            col->header->len++;

            col->down->up = col;
           col->up->down = col;
        }
    }
    //Restore the heather
    hcol->right->left = hcol;
    hcol->left->right = hcol;
}

结果

在我的笔记本电脑（速度慢）上，用了 11 分 13 秒，程序找到了 9356 个解决方案。在删除重复项后，剩下 2339 个解决方案（这在逻辑上是正确的，9356/4=2339）。它检查了 288,949,150 个节点（尝试将块放在棋盘上）。

使用舞动链并避免微不足道的解决方案，程序花了 14 秒找到所有解决方案。

这表明舞动链是计算此类问题解决方案的快得多的算法。

为了提高速度，所有节点都存储在一个向量中，并使用 reserve() 方法。这样，只有一次分配，而不是为每个创建的节点进行一次分配。

库

我将解决方案迁移到了 VS 2010。它使用了 MFC。代码可以编译为 32 位和 64 位。

致谢

• 舞动链数独.
• Donald E. Knuth 舞动链 C 算法.