逻辑游戏，9 张方牌和 1 个大方格

Question

我不确定这是正确的地方，也许其他一些堆栈交换，告诉我我会在其他地方发布。

这是我的问题，我在朋友那里发现了一个老游戏，它应该是一个智力游戏：9张小方形卡片，你必须将它们放置在一起，以便它们全部组合在一起，这是一张图片：

在游戏前几个小时后，我发现没有真正简单公平的方法来完成游戏，所以我采用了程序化的方式。

这就是我遇到困难的地方，我想我可以使用一些随机函数，一个大循环，然后就可以完成它。但是有类似 (4*9)^9 的解决方案，所以看起来并不那么容易。

这是我写的代码，目前没什么用： 每次我进入循环时，我都会洗牌数组，按随机值旋转卡片并检查拼图是否正确，浪费了很多周期，但我不知道从哪里开始才能提高效率。

编辑 ： 固定代码，我得到了几副 8 张牌，但没有 9 张牌，如果有人修复了我的代码，或者可能没有解决方案？

require 'json'

class Array
    def rotate n
        a =dup
        n.times do a << a.shift end
        a
    end
end


@grid = [[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"o", "head" => 2}],
[{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"c", "head" => 1},{"type"=>"p", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}],
[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}],
[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 1}],
[{"type"=>"a", "head" => 1},{"type"=>"p", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"a", "head" => 1},{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2}],
[{"type"=>"o", "head" => 1},{"type"=>"a", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"p", "head" => 1}],
[{"type"=>"p", "head" => 1},{"type"=>"c", "head" => 2},{"type"=>"o", "head" => 2},{"type"=>"a", "head" => 1}]]
@new_grid = [nil, nil, nil,nil, nil, nil,nil, nil, nil]
@used = [false, false, false,false, false, false,false, false, false]

def check_validity(card, position, orientation)
    # since I'm adding from top left to bottom, I only need to check top and left           
    try_card = @grid[card].rotate orientation     
    valid = true
    # top
    if (@new_grid[position-3])
        if (try_card[0]["type"] != @new_grid[position-3][2]["type"] || try_card[0]["head"] == @new_grid[position-3][2]["head"])
            valid = false
        end
    end
    # left
    if (@new_grid[position-1] && (position % 3) != 0)
        if (try_card[3]["type"] != @new_grid[position-1][1]["type"] || try_card[3]["head"] == @new_grid[position-1][1]["head"])
            valid = false       
        end
    end
    return valid
end


def solve_puzzle(position)
    (0..8).each do |card|
        unless (@used[card])
            (0..3).each do |orientation|
                if (check_validity(card, position, orientation))
                    @used[card] = true
                    @new_grid[position] = @grid[card].rotate orientation
                                        if position == 7 
                                            puts @new_grid.to_json                                      
                                        end
                    if (position < 8)
                        solve_puzzle(position + 1)
                    else
                        puts "I WON"
                        puts @new_grid.to_json
                    end
                    @new_grid[position] = nil
                    @used[card] = false
                end
            end
        end
    end
end


solve_puzzle(0)

Answer 1

图像中的方块实际上没有解。我通过将最后一块右侧的绿色/蓝色底部更改为红色/白色底部（就像上面右侧的那块一样）来实现它。

随机化是一个坏主意，最好进行彻底的搜索，尝试每一种可能性，就像 Petar Minchev 回答的那样。您也许可以通过预处理来加快速度。除了第一块之外，您始终会知道需要匹配的一侧或两侧。每种类型在所有 9 件中只有 3 到 6 个实例。想象一下你有这些空间：

0   1   2
3   4   5
6   7   8

最初我是通过填充位置 4 来做到这一点的，然后是 1、3、5、7，最后是角落。通过 2371 次递归调用，在 3.5 毫秒内找到了 4 个解决方案。通过将顺序更改为 4, 1, 5, 2, 7, 8, 3, 0, 6，递归调用次数降至 1.2 毫秒，因为角落里的选项较少。现在想想，按顺序进行会介于两者之间，但修改后的顺序也会同样快（0、1、3、4、2、5、6、7、8）。重要的是，必须检查两个匹配项可以减少进行昂贵的递归调用的次数。

Step[] Steps = {
    new Step() { Type = 0, Position = 4 },
    new Step() { Type = 1, Position = 1, MatchP1 = 4, MatchO1 = 0 },
    new Step() { Type = 1, Position = 5, MatchP1 = 4, MatchO1 = 1 },
    new Step() { Type = 2, Position = 2, MatchP1 = 5, MatchO1 = 0, MatchP2 = 1, MatchO2 = 1 },
    new Step() { Type = 1, Position = 7, MatchP1 = 4, MatchO1 = 2 },
    new Step() { Type = 2, Position = 8, MatchP1 = 7, MatchO1 = 1, MatchP2 = 5, MatchO2 = 2 },
    new Step() { Type = 1, Position = 3, MatchP1 = 4, MatchO1 = 3 },
    new Step() { Type = 2, Position = 0, MatchP1 = 1, MatchO1 = 3, MatchP2 = 3, MatchO2 = 0 },
    new Step() { Type = 2, Position = 6, MatchP1 = 3, MatchO1 = 2, MatchP2 = 7, MatchO2 = 3 },
};

以下是我的卡片的设置方式，请注意我更改了最后一张卡片的一侧以获得解决方案。 1 是红色，2 是脂肪，3 是蓝色/绿色，4 是黄色。我与 0x10 进行异或表示它是相同颜色的底部。这样，您可以对 2 个类型进行异或，然后与 0x10 进行比较，看看它们是否匹配，或者您可以对一个类型与 0x10 进行异或，以找到您要查找的类型。

Card[] cards = {
    new Card(0x01, 0x03, 0x14, 0x12),
    new Card(0x02, 0x14, 0x13, 0x01),
    new Card(0x03, 0x11, 0x12, 0x04),

    new Card(0x01, 0x13, 0x12, 0x04),
    new Card(0x11, 0x13, 0x04, 0x03),
    new Card(0x04, 0x11, 0x12, 0x01),

    new Card(0x04, 0x02, 0x14, 0x13),
    new Card(0x02, 0x14, 0x13, 0x01),
//              new Card(0x01, 0x13, 0x12, 0x04) // no solution
    new Card(0x01, 0x11, 0x12, 0x04) // 4 solutions
};

在预处理时，我想要一个按我正在寻找的类型索引的数组，它将为我提供具有该类型的所有卡片以及该类型所在的方向。我还将 NextType（顺时针）放在那里，以便更容易比较角点：

public CardImageOrientation[][] Orientations { get; set; }

public struct CardImageOrientation
{
    public int CardIndex;
    public int TypePosition;
    public int NextType;
}

// Orientations[1] is an array of CardImageOrientation structs
// that tell me what cards contain a side with type 1, what position
// it is in, and what the next type clockwise is

这是我的主要递归方法：

public bool Method1Step(int stepIndex)
{
    StepCalls++;
    if (stepIndex > 8) // found a match
    {
        FindCount++;
        return !Exhaustive; // false return value will keep going if exhaustive flag is true
    }

    Step step = Steps[stepIndex];
    switch (step.Type)
    {
        case 0:
            // step 0 we just loop through all cards and try them in position 4 with orientation 0
            for (int i = 0; i < 9; i++)
            {
                PlaceCard(i, 4, 0);
                steppedUp = true;
                if (Method1Step(stepIndex + 1))
                    // found a solution, return true (will be false below for exhaustive)
                    return true;
                RemoveCard(4);
            }
            break;
        case 1:
        case 2:
            // step type 1 we simply try to match one edge with another, find card in position we are matching with
            Card card = Cards[CardIndices[step.MatchP1]];

            // to find the actual type in that position, we take the position we are looking for, subtract card orientation, add 4 and take the lowest two bits
            int type = card.Types[(step.MatchO1 - card.Orientation + 4) & 0x03];

            // find opposite orientation where we need to put the match in the empty spot
            int orientation2 = (step.MatchO1 + 2) & 0x03;

            // looking for type that is the opposite of the existing type
            int searchType = type ^ 0x10;
            for (int i = 0; i < Orientations[searchType].Length; i++)
            {
                // try one card value that matches
                CardImageOrientation cio = Orientations[searchType][i];

                // make sure it isn't in use
                if (Cards[cio.CardIndex].Position < 0)
                {
                    // check either we are step 1 or that second type matches as well
                    if (step.Type == 1 || (
                            step.Type == 2 && 
                            (Cards[CardIndices[step.MatchP2]].Types[(step.MatchO2 - Cards[CardIndices[step.MatchP2]].Orientation + 4) & 0x3] ^ cio.NextType) == 0x10)
                        ) {
                        // get new orientation for card
                        int newOrientation = (orientation2 - cio.TypePosition + 4) & 0x03;

                        PlaceCard(cio.CardIndex, step.Position, newOrientation);
                        if (Method1Step(stepIndex + 1))
                            // found solution and non-exhaustive so return true
                            return true;
                        RemoveCard(step.Position);
                    }
                }
            }
            break;
    }
    return false; // dead end or exhaustive search
}

有趣的说明：我编写了代码，使用现有的修改牌组和 4 个解决方案以及使用随机种子创建的 9999 个其他牌组来随机化卡片。 1 和 9999。我在 7.2 秒内发现了 3,465 个解决方案分布在 1,555 个起始布局上，因此每次运行的平均时间约为 0.72 毫秒。它总共调用了 416 万次 Method1Step()。

Answer 2

这个问题是另一种形式的平铺拼图，其他形式包括Pentominoes 和 数独。

解决此类难题的最有效算法之一是 算法 X，由 算法 X 开发="http://en.wikipedia.org/wiki/Donald_Knuth" rel="nofollow">唐纳德·高德纳。算法 X 的最佳实现技术之一被称为跳舞链接。

算法 X 在解决难题方面非常高效（通常在几毫秒内解决数独）的关键原因是，无用的配置被有效地从搜索空间中删除。

例如，对于您的拼图，如果左上角的棋子在南边缘有 Getafix 头，则可以消除在其正下方的北边缘没有 Getafix 脚的每个解决方案配置。

在制定算法 X 的约束矩阵方面，您有 9 个棋子，每个棋子可以放置在 4 个方向的 9 个位置，因此您的约束矩阵将有 324 行，每一行对应于每个可能的棋子放置。

识别约束列更为复杂。您将需要 9 个约束列 - 每个位置一个，以确保各个部分不会位于同一位置。您还需要一堆附加列来捕获跨越每个边缘的字符必须兼容的约束。有 12 个交互点，四个角色，每个角色分为两部分 - 另外 96 列。

更新

这是启动约束矩阵的尝试。让我们以 OP 图片中显示的第一块为例，它有以下四个部分：

• Getafix Head（北）
• Roman Head（东）
• Asterix Feet（南）
• Obelix Feet（西）

对于我们的约束矩阵，我们需要

• 9 列位置（TopLeft ） , TopCentre, ... MiddleCentre, ... BottomRight)
• 9 列用于棋子 (Piece1 ... Piece9)
• 96 列用于交互点

我们通过列出从特定位置得到的东西以及从特定位置获得的东西来构建约束行这个位置阻止了。

• 位置：左上，Piece1
• 包括：左上东罗马头、左上南 Asterix 脚
• 排除：上中心西 Getafix 头、上中心西 Getafix 脚、上中心西 Obelix 头、上中心西 Obelix 脚、上中心西 Asterix 脚、 TopCentreWest-Asterix-Head、TopCentreWest-Roman-Head
  （本质上，在 TopCentreWest 上只有罗马脚是可以的）
• 排除：MiddleLeftNorth-Obelix-Head、MiddleLeftNorth-Obelix-Feet、MiddleLeftNorth-Getafix-Head、MiddleLeftNorth-Getafix-Feet、MiddleLeftNorth-Roman-头、中左北罗马脚、中左北星形脚
  （只有 Asterix-Head 在 MiddleLeftNorth 位置可以）

现在，在左上位置的这件作品的其他三个方向上重复此操作 3 次...

• 位置：TopLeft，Piece1
• 包括：TopLeftEast-Getafix-头，TopLeftSouth-Roman-Head

• ...

• 位置：TopLeft，Piece1

• 包括：TopLeftEast-Obelix-Feet、TopLeftSouth-Getafix-Head

• ...

• 位置：TopLeft，Piece1

• 包括：TopLeftEast-Asterix-Feet、TopLeftSouth-ObelixFeet
• ...

重复这 4 行 8 个以上次，对于 8 个剩余空间中的 4 个方向中的每一个（另外 32 行，总共 36 行）。

然后，为剩余 8 块的每个位置/方向再创建 36 行（另外 288 行）。

您可能想要编写代码来生成矩阵，而不是手动计算它！

Answer 3

我确信了解 prolog 在这里会有很大的帮助，但我认为我没有资格回答那。不过，我也许可以帮助您计算出您当前的解决方案可行的可能性有多大：

9 块可以放入 9 块中！ = 362880 种排列（仅位置）

它们每个都可以旋转 4 种方式 -> 4^9 = 262114

然而，你将有 4 个解，它们只是彼此的旋转，所以 /=4。

在找到解决方案之前平均给出 23,781,703,680 种可能的安排来尝试:(

Answer 4

使用递归和修剪。我的意思是，当您放置当前卡片时，它必须与您已放置的卡片的方向相匹配。这样你就消除了许多不可能的情况:)

像这样：

    void generate(int whichPos) //whichPos is from 1 to 9
    {
       for (int card = 1; card <= 9; card++)
       {
          if (used[card]) continue;

          for (int orientation = 0; orientation < 4; orientation++)
          {
              if (orientation does match other cards from 1 to whichPos - 1 in the grid)
              { 
                  used[card] = true;
                  saveInGrid();
                  generate(whichPos + 1);
                  used[card] = false;
              }       
          }  
        }
    }

    generate(1);

Answer 5

直到最近我一直以约束规划研究为生，我想我可以提供一些建议。

您最好的选择是尝试使用一些合理的搜索启发式方法和一点狡猾来生成和测试，以最大程度地减少浪费的搜索工作量。

这样思考这个问题：你有九个要分配的逻辑变量，{x1，...，x9}，其中x1，x2，x3是底行，x4，x5，x6是中间行，x7， x8、x9 顶行。

每个变量可以采用集合 D = {(p, r) | 中的 36 个可能值之一。 p 是一个片段 {p1, p2, ..., p9}，r 是一个旋转 {0, 90, 180, 270}}。

一种解决方案是从 D 到 x1,...,x9 的分配，使得每个块都恰好用于一个分配中，并且每对相邻图块具有兼容的分配（即，边缘匹配）。

您的搜索应该跟踪每个变量的可能分配范围。特别是：

• 如果将一块 pi 分配给变量 xj，那么您必须从所有其他变量的域中划掉以 pi 为特征的所有可能值；
• 如果将值 (pi, r) 分配给变量 xj，则必须从 xj 的邻居中删除所有不兼容的分配；
• 如果你从一个变量的域中删除了所有可能的赋值，那么你就知道你已经进入了死胡同，必须回溯；
• 如果您曾经将变量的可能赋值集减少为单个值，那么您就知道该值必须分配给该变量；
• 如果你想变得更花哨，你可以使用回跳而不是简单的回溯（这是你在失败时回溯到最近的冲突决策，阻止你分配变量，而不是仅仅回溯到前一个决策）。

一个好的搜索策略是始终选择剩余域最小的变量来尝试下一步分配。这样，您始终可以查看受您在搜索分支上所做的决策影响最大的变量。

无论如何，希望这会有所帮助。

干杯!

Answer 6

我认为你的错误在于检查有效性。您不需要检查位置 3 和 6 的左侧，因为它们是拼图的左侧，不需要与上一行的右侧匹配。

编辑：这是我正在考虑的一行：

# left
if (@new_grid[position-1] && (position % 3) != 0)
    if (try_card[3]["type"] != @new_grid[position-1][1]["type"] || try_card[3]["head"] == @new_grid[position-1][1]["head"])
        valid = false       
    end
end

编辑2：检查你的作品，我看到中心作品如下：

[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 2}],

我认为应该是

[{"type"=>"p", "head" => 2},{"type"=>"c", "head" => 2},{"type"=>"a", "head" => 1},{"type"=>"c", "head" => 1}],