解决一个4x4拼图网格

我试图创建一个程序，将发现的步骤来解决以下规则一个难题：解决一个4x4拼图网格

鉴于任何一组色彩在4x4的方格，试图匹配具有相同数量的颜色的结束模式。
颜色不交换，但水平或垂直旋转，使得

{W，W，B，W}

可旋转以

{W，W，W ，B}

{B，W，W，W}

{W，B，W，W}

整个难题可以用不到16个步骤解决。

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

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

stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726 ＃34656726
stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically
amzi.com/articles/rubik.htm
chessandpoker.com/rubiks-cube-solution.html

和15个数字问题

stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15 - 移动 - 数字拼图

为了使这个问题尽可能明确：什么是a）储存的好方法/打印的步骤，和b）发现，采取至少步骤解决？

来源

2016-01-22 Rhys

*什么是a）存储/打印步骤的好方法，b）找到采取最少步骤的解决方案？a）树。 b）树分支上的最少节点数。 –

@GilbertLeBlanc，我将如何构造该树/节点集？只要选择N个可能的随机动作（16个方格中的每个方格可能有6个方格就是96个方格）并继续？ – Rhys

它不是随机的。根据您自己的示例，您将以4 x 4网格作为顶级节点。你做所有可能的水平或垂直移动。每一步都是起始位置的一个节点。你走下一个关卡，在每个节点上做同样的事情，直到你有了解决方案。通过广度优先搜索，您可以找到最短的解决方案，而无需解决所有问题，但您应该在关系紧密的情况下完成关卡。 –

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

说你有这样的起动方式：

[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，我们只有2种模式垂直向上和垂直向下。

我们有1级

共有12种模式，我们走得很有条理。我们的举动没有随机性。水平向右，水平向左，垂直向上，垂直向下。

现在，采取级别1的12个模式中的每一个，并生成16个模式。你不必保存匹配在0级和第二级的模式，1

生成和保存的模式弥补了2级

继续生成每个级别，直到你打16级或你有图案一个办法。由于您要删除树级别的重复项，因此您不会达到级别16的16至16个电源节点的理论最大值。

如果存在具有最少移动次数的多个解决方案。

来源

2016-01-22 08:54:19

解决一个4x4拼图网格

回答

相关问题