解决 4x4 拼图网格

Question

我正在尝试创建一个程序，该程序将按照以下规则找到解决难题的步骤：

给定 4x4 网格中的任意一组颜色，尝试匹配具有相同数量颜色的结束模式。
颜色不会交换，而是水平或垂直旋转，这样

{W, W, B, W}

可以旋转到

{W, W, W, B}

{乙、乙、乙、乙}

{W, B, W, W}

整个谜题只需不到 16 步即可解决。

我已经想出了如何存储拼图本身的数据，但我正在努力寻找可以显示步骤的解决方案。由于深度限制为 16 步，我可以尝试暴力破解，但我真的不知道如何建立模式。

这类似于解魔方，我已经看过以下资源：

Whosebug。com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726#34656726
计算器。com/questions/5563671/solving-rubiks-cube-programmatically
amzi.com/articles/rubik.htm
chessandpoker.com/rubiks-cube-solution.html

和 15 个数字问题

计算器。com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

为了让这个问题尽可能清楚：a) store/print 步骤和 b) 找到最少的解决方案的好方法是什么步骤？

Answer 1

我想我无法解释没有图片的树。

假设您有这样的起始模式：

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

这将是树的顶级节点。 0 级。

所以现在，我们进行所有可能的水平和垂直旋转。先水平向右

[B, W, W, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[B, W, W, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, B, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[B, W, W, W]

水平向左。

[W, W, B, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, B, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, W, W, B]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, B, W]

垂直向上

[W, W, W, B]
[B, W, W, B]
[W, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, W]
[B, W, W, B]
[W, W, W, B]

垂直向下

[W, W, W, B]
[W, W, W, B]
[W, W, W, W]
[B, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, B]
[W, W, W, W]

由于第二列和第三列都是W，所以我们只有垂直向上和垂直向下两种模式。

我们在第 1 级共有 12 个模式。

我们非常有条不紊地搬家。我们的行动没有随机性。水平向右，水平向左，垂直向上，垂直向下。

现在，对第 1 级的 12 种模式中的每一种进行提取，并生成 16 种模式。您不必保存与级别 0 和级别 1 的模式匹配的模式。

生成并保存的图案构成第 2 级。

继续生成每个级别，直到您达到第 16 级或找到解决方案。因为您要从树级别中删除重复项，所以您不会在级别 16 上达到理论最大值 16 的 16 次方节点。

如果有多个解决方案且步数达到最小值，请通关。

解决 4x4 拼图网格

Solving a 4x4 Puzzle Grid

java

multidimensional-array

sliding-tile-puzzle