逻辑游戏，9张方牌和一个大方块

Question

我不确定这是不是合适的地方，也许是其他的stackexchange，告诉我我会在其他地方发帖。

这就是我的问题，我在我的朋友家发现了一个古老的游戏，它应该是一个心理游戏: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

使用带剪枝的递归。我的意思是，当你放置当前卡片时，它必须与你已经放置的卡片的方向相匹配。因此，您可以消除许多不可能的情况：)

如下所示：

    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 2

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

你最好的选择是尝试生成并测试一些合理的搜索启发式和一点巧妙，以最大限度地减少浪费的搜索工作量。

这样考虑这个问题:您有9个要赋值的逻辑变量，{x1，...，x9}，其中x1，x2，x3是底行，x4，x5，x6是中间行，x7，x8，x9是顶行。

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

一个解决方案是从D到x1，...，x9的赋值，使得每一块恰好在一个赋值中使用，并且每对相邻的瓦片具有兼容的赋值(即，边缘匹配)。

您的搜索应该跟踪每个变量可能赋值的域。特别是：

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

一个好的搜索策略是总是选择剩余域最小的变量来尝试下一步赋值。这样，您将始终查看受搜索分支上已做出的决策影响最大的变量。

不管怎样，希望这能帮上忙。

干杯!

Answer 3

我想你的bug是在检查有效性中。您不需要检查位置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}],