65.9K
CodeProject 正在变化。 阅读更多。
Home

使用回溯算法在 C# 中解决打乱的方块

mshami
starIconstarIconstarIconstarIconstarIcon

5.00/5 (5投票s)

2014 年 9 月 6 日

CPOL

11分钟阅读

viewsIcon

28810

downloadIcon

496

打乱方块问题的非图形化解决方案。

目录

  • 引言
  • 背景与求解方法
  • 实现

引言

B-Dazzle 公司推出了一款名为（Scrambled Squares）或（Scrabble Squares）的游戏。该游戏有多种图案；有些有颜色，有些没有，等等。您可以在官方网站 www.b-dazzle.com 上找到这款益智游戏。

游戏包含 4、9 或 16 个方块，排列成 d X d 的网格。下面是一个例子……。

几个月前，一位学生打电话给我，请求帮助。他在学习这个问题的过程中遇到了一些困难。我解释了一下，所以我会在这里附上带有插图的解决方案。

我发现关于这个问题最好的网站是 www.public.asu.edu/~kburger2/scholar/scramble/scramble.html，其中包含一个演示问题的 PDF 文件。代码也以 Java Applet 的形式提供。

在本文中，我将一步一步地向您介绍解决方案，解释用于解决该问题的算法和数据结构。

问题是什么？

您可能会注意到，每个独立的方块都有 4 个不同的侧面。以第一个方块为例，您会看到 4 个滑雪者，但并非滑雪者的整个身体都可见，您可能只看到身体的上半部分或下半部分。此外，您还会看到每个身体部分都有不同的颜色。有些方块包含 4 种不同的颜色，有些只有 3 种。

在这个游戏中，您的任务是重新排列或旋转每个方块，形成一个完整的棋盘，使得一个方块的侧面与相邻方块的侧面能够完美匹配，并且颜色也必须相同。

这项工作必须通过编码来实现……我们首先需要理解问题并开发一种算法，同时考虑到对程序员最易于理解的方式。

背景与求解方法

假设您有一个 2 X 2 的方块棋盘。

要解决这个谜题，您需要遵循以下步骤：

  • 考虑位置 1.1（第一行，第一列）的 sq1（方块编号 1）。
  • 现在，您需要尝试将 sq2 放在下一个位置 1.2，并检查 sq2 的左侧是否能与 sq1 的右侧完美匹配。
  • 如果可以，我们就继续将 sq3 放在位置 2.1，以此类推。
  • 否则，我们就需要旋转 sq2（例如向左旋转）并重新检查兼容性。
  • 我们可以尝试旋转 sq2 三次，每次旋转后都必须重新检查兼容性。如果这种旋转没有用，那么我们就将 sq3 替换 sq2 放在该位置，并重试相同的步骤。
  • 如果没有任何方块能与位置 1.1 的 sq1 匹配，我们就必须旋转 sq1 并尝试之前的步骤。
  • 如果旋转三次并尝试都对 sq1 无效，那么您就需要将 sq2 替换 sq1 并重复上述步骤。
  • 以此类推……。

这种冗余的迭代和步骤非常适合我们将要讨论的递归算法。这类递归算法称为回溯算法，因为我们可以尝试一个步骤，如果成功就继续；如果不成功，我们就回滚并更改上一个步骤，然后重试……以此类推。这些算法依赖于错误和试错。

现在，它需要多少时间？让我们从数学上谈谈……。

  1. 每个方块在任何位置都旋转 3 次。
  2. 对于每个位置，我们有 n 种排列。

其中 n = 总元素（方块）计数。

因此，对于每个部分解决方案，我们有 3n 次旋转，并且有 (n!) 次替换，哇，这是一个巨大的转换和旋转数量，尤其是当您玩更大尺寸的游戏时。

因此，对于我们的例子，我们有 3^4 X 4! = 1944（最坏情况下的移动次数）。现在，很清楚为什么我们需要计算机程序来解决这个问题。

现在您已经理解了我在代码中实现的**回溯算法**。

对于棋盘上的每个位置，从位置 0 开始，我们将放置一张卡片，然后我们必须尝试所有可用的卡片来填充下一个位置，为此，我们可以将当前卡片的顶部和左侧与现有卡片进行比较。

假设您已到达位置 4，您必须将当前实验卡片的顶部与位置 1 的卡片的底部进行比较，并将当前实验卡片的左侧与位置 3 的卡片的右侧进行比较。

如果实验卡片适合此位置……没问题，我们可以继续到下一个位置，如果不适合……卡片必须在该位置旋转，然后重试比较。如果卡片旋转了 3 次……这意味着您已尝试了该卡片在该位置的所有可用旋转，您必须将卡片替换为下一个尚未使用的卡片，并重试之前的步骤；如果该位置没有接受任何卡片，那么我们就必须**回溯**到棋盘上的前一个位置（位置 3），尝试旋转卡片，然后重新进行所有操作。

啊哈……这是该算法工作原理的总结。

每个回溯算法的伪代码如下：

TrySolve()
{ 
Initialize selection of candidates;
Do { 
Select next candidate;
If (acceptable)
{ 
Record it;
If (solution incomplete)
{ 
Try next step;
If (not successful)
Cancel recording;
} 
} 
} while (not successful) and (remains of candidates);
}

这意味着，在我们的算法中：

  • 取位置 x
  • 对于每个可用的卡片（crd）……（未在另一个位置使用）
    • 比较 crd.left 与 left_crd.right && crd.top 与 upper_crd.bottom
    • 如果比较成功
      • 将此部分解决方案记录在草稿中
      • 尝试对位置 x+1 执行相同的步骤
      • 如果位置 x+1 的解决方案不成功
        • 取消 x 的部分解决方案记录
    • 旋转位置 x 中的 crd 并重试

如上所述，回溯算法依赖于错误和试错，这意味着任何未能构建另一个部分解决方案以实现主要目标的**部分解决方案**都会被删除，然后尝试另一块拼图。

该算法的最佳示例是国际象棋中的马的移动，以及其他。

实现

  • 输入文件格式
  • 类（项目结构）
  • 循序渐进

您现在应该会意识到一些事实。

  • 仅出于显而易见和易于理解的目的，使用 OOP 方法编写解决方案。您可能会注意到性能不如您期望的那样。
  • 我专注于算法和代码结构，而不是输入和输出形式，因此您可以开发使用图形形式进行输入和输出的新代码。

输入文件格式

假设之前的方块我们将称之为 CARD。这张卡片有四个侧面：顶部、右侧、底部和左侧。每个侧面都由身体的 PART（上半部分、下半部分）和 COLOR 组成。因此，这张卡片在输入文件中的形式如下：

CardName top-color right-color bottom-color left-color
0 HEAD-VIOLET TAIL-BLUE HEAD-VIOLET HEAD-YELLOW

现在看看这个文件，它将用于测试，并且也随源代码一起打包。

此文件用于构造一个 /3 X 3/ 的游戏棋盘，请注意它有 9 个项目，从 0 到 8。

这些卡片以图所示的行状数组形式分布……

类和方法

让我们仔细看看代码。

1- CardReader：读取卡片输入文件并按上述方式存储。

此类包含 4 个方法，其中最主要的是 MakeAllCards。此方法读取文件的行，并将该行传递给 MakeCard 方法，该方法使用 GetPart 和 GetColor 方法分离每个侧面的组件，然后构建 4 个侧面，创建新卡片并将其返回给 MakAllCard 方法。它会重复此过程，直到文件结束。

输入文件格式与此类相关联。如果您希望更改文件格式，则必须修改此类以适应新格式。

2- Part、PartColor 枚举：枚举部分 和部分颜色 （4 种或更多颜色）。

颜色和部分的 enum 用于构造 Side 类，因为侧面需要与另一个卡片侧面进行比较，所以我们可以为每种颜色和部分分配一个数值。现在看这个方程：

Part

Color

3- Side：创建方块/卡片的一个侧面，其中包含 PART-COLOR 对。

此类是代码中的基本类；它代表方块的一个侧面，并具有一个数值，该数值根据 PART-COLOR 对区分它与其他侧面。

假设 side1 、side2 和 side3 。

如果您计算每个值的数值，您会发现分别是 3、-3 和 2。

所以您可以说 side1、side2 和 side3 不相等，但 side2 是 side1 的互补。

每对互补的数值相加必须返回 0。

它包含一个布尔方法 CanJoin(Side side)，该方法决定此侧面是否为参数侧面的互补。侧面的值可以从计算它的 public property Value 中获得。

4- Border：包含 4 个侧面，形成 CARD 基类。

Border 类有 4 个侧面和一个整数值，该值在每次旋转时都会改变，还有一个 Rotate() 方法，该方法以圆形方式更改侧面，然后递增 Orientation 属性。当方向小于 3 时，它可以旋转。

5- Card：从 BORDER 派生，但添加了新属性……等等。

因此，它具有 Border 属性以及名称、位置等新属性。此类中最重要的**方法**是 IsCompatible(Card left, Card top) 方法，如果该卡片可以放置在此位置并与上方和左侧卡片兼容，则返回 true。它使用侧面的方法（CanJoin(side s)）来决定兼容性。

但您可能会注意到，前面提到的每个类都包含手动实现的 Clone() 方法……您可以借助 IClonable 接口。

6- DraftSpace：对空游戏棋盘的表示，临时存放解决方案卡片以构建解决方案。

此类仅用于临时处理解决方案，您可以删除它，但使用它会使代码更有条理。TryAdd(card c) 方法用于根据其位置和相邻卡片填充草稿数组，它是一个 d X d 的空数组，表示游戏棋盘。

7- Result：表示解决方案。

为了存储解决方案，我们发明了此类，您也可以删除它，因为我们只显示第一个也是唯一的第一个解决方案。我没有完成代码来发现其他解决方案，但您应该这样做。

8- ScrambledSquares：实现该算法的主类。

问题中的主类，包含 Solve(int x) 方法。此方法实现回溯算法，此外，它还包含一些辅助方法，如 PickCard(int position)，因为我们将位置作为一个数字而不是数组中的 (X,Y) 传递，以及 RegisterSolution 方法将解决方案注册到 Result 实例（如我所说，用于多个解决方案，但现在只有一个解决方案）。

分步指南

在 ScrambledSquares 类中的 Solve(int position) 方法中，您会看到：

logger.WriteLine("----------------------------------------------");
logger.WriteLine("Position = {0}\t\t\tSearch depth = {1}", pos, SearchDepth);
++SearchDepth;

logger 只是一个文件写入器，它写入每一步以查看程序的工作方式；SearchDepth 是一个整数属性，在每次调用此方法时递增，以查看达到的深度。

if (pos == MAX_CARDS)
{
   logger.WriteLine("Done");
   RegisterResult();
   draft.Clear();
   return true;
}

此代码段用于确定我们是否成功获得解决方案。在递归算法中，我们必须根据决定成功或失败的某些条件使用停止代码。现在对于我们的停止代码，如果我们到达了数组边界之外的位置，那么我们就有一个解决方案，否则递归尚未完成。

现在，遍历所有卡片是为了确定当前位置的最佳卡片。

for (int current = 0; current < MAX_CARDS; current++)
{
    Card c = PickCard(current);
    if (!c.Used)
    {
        c.ResetOrientation();
        while (c.CanRotate)
        {
            if (draft.TryAdd(c, pos))
            {
                logger.WriteLine("((TRY)) {0} --> {1} after {2} rotation", c.Name, pos, c.Orientation);
                c.Used = true;
                c.Position = pos;
                if (Solve(pos + 1))
                {
                    return true;
                }
                c.Used = false;
                logger.WriteLine("[REJECT] {0} from position {1}", c.Name, pos);
            }
            c.Rotate();
            logger.WriteLine("<<ROTATE>> {0} in position {1}", c.Name, pos);
        }
    }
}
return false;

我们使用 PickCard 方法从 0 开始搜索，它通过一个数字而不是两个（行和列）来获取卡片，方法是计算行和列的值，如下所示：

private Card PickCard(int pos)
{
    try
    {
        return cards[pos / dimension, pos % dimension];
    }
    catch (Exception)
    {
        return null;
    }
}

(Pos / dimention) 将返回行，(pos % dimension) 返回列；这适用于所有 n X n 数组。但如果位置超出了数组范围，它将返回 null 值。

回到主代码，选中的卡片必须是以前从未在任何地方使用过的，所以我们讨论卡片的状态；如果未使用，我们就继续；否则，我们就选择另一张卡片，依此类推。

if (!c.Used)

为了确保选中的卡片可以旋转，我们首先应该重置它的方向，然后我们将尝试当前位置的所有可用旋转，所以我们开始一个循环遍历所有可用的卡片旋转，以尝试一张卡片的所有旋转。

c.ResetOrientation();
while (c.CanRotate)
{
}

如果卡片在当前位置可接受，它将被添加到草稿棋盘上，并标记为已使用，然后我们尝试对 position+1（游戏棋盘上的下一个位置）重复这些操作。

if (draft.TryAdd(c, pos))
{
  c.Used = true;
  c.Position = pos;
  if (Solve(pos + 1))
  {
    return true;
  }

如果所有位置都已访问，这意味着所有卡片都已放置在首选的状态和位置。

如果不是，这意味着卡片不在完美位置，所以如果它可以旋转，我们就旋转它，否则我们就将卡片标记为未使用并继续下一张卡片。

c.Used = false;

如果所有卡片都尝试过但没有任何结果，则返回失败。

我们有 2 个输出文件，一个用于结果（如果存在），另一个用于日志。在日志文件中，您将看到解决问题所采取的步骤。

感谢阅读！

© . All rights reserved.