灵魂潮汐16-1（迷失之芯）最少步算法

解密内容主要分为两部分。第一部分---确定图案的目标位置：主要是数独。第二部分---把图案移动到目标位置的方式：元素置换和二维二阶魔方（实际上是两个六阶置换群和一个八阶置换群）

第一张图的最少步数9步（4步交换位置，3步旋转），第二张图是12步（2步交换位置，10步旋转），其他的解密部分较简单，大家应该花的步数区别不大

第一张图的具体步骤(从左上方开始标号，第一个旋转中心为a，第二个旋转中心为b)

【资料图】

旋转：a

置换：[[3, 1, 1, 2, 2, 0], [1, 1, 3, 2, 2, 0], [1, 2, 3, 2, 1, 0]]（列表中的每个元素的位置对应可以交换的六个位置，按从左到右，从上到下的顺序,0=雪花，1=太阳，2=枫叶，3=芽）

第二张图的具体步骤：

旋转：abcbbabacc

置换：[0,2],[2,0]

解：写个程序让电脑跑。

第一阶段：写个自动填数独的脚本，以确定图案的目标位置

将游戏中的数独界面简化为一个嵌套列表，可被移动的图案留空，不能被移动（被旋转或置换）的图案简化为数独中预先固定的数字，旋转节点简化为数独中的断点（断点的所在行的左右视作不连续，断点所在列的上下视作不连续）。得到第一张图的数独列表：

[        ["$"    , None, None, None],

[None, "$"    , None, "$"    ],

[None, None, "$"    , None],

[None, None, None, None]  

]

第二张图的数独列表：

[       ["$"     , 2      , 1       , None, 3       ],

[0       , 3       , None , "$"   , None],

[None , None, "$"     , None, 2      ],

[None, "$"     , None, 3       , 0       ],

["$"    , None, None, 1 , "$"    ]

]

有很多留空，第一张图甚至所有的图案的位置都不固定，此时让去跑应该会得到很多解。

同时要考虑到，每个数字的大小范围和可使用的次数以及可能到达的位置都是确定的。

由于两张图数独能被填入的数字被分为了独立两部分（置换部分和旋转部分），需要分情况讨论。

先看情况简单的图二，图二中置换部分只有两个空位，只有两种不同的情况，分别考虑这两种情况下可能的解，在游戏初始状态

[       ["$"     , 2      , 1       , None, 3       ],

[0       , 3       , None , "$"   , None],

[0       , None, "$"     , None, 2      ],

[None, "$"     , None, 3       , 0       ],

["$"    , None,2         , 1        , "$"    ]

]

下无解，所以只需考虑

[["$", 2, 1, None, 3],

[0, 3, None, "$", None],

[2, None, "$", None, 2],

[None, "$", None, 3, 0],

["$", None, 0, 1, "$"]]

的解，以此作为输入，脚本输出了一个解

Solution 1 :

$ 2 1 0 3 

0 3 2 $ 1 

2 1 $ 0 2 

3 $ 2 3 0 

$ 3 0 1 $ 

自此，图二中所有的图案的目标位置均已确定。

再看第一张图，置换部分和旋转部分都有6个空位，看起来情况没差，我觉得都是我人脑考虑不全所有可能的情况的情况。

因为旋转比较有趣我选择了先分析旋转的所有情况，写一个模拟二维魔方的程序。

设置二维魔方的初始状态与游戏中的状态相同（matrix = [[3, 1], [0, 0], [3, 2]]），让用dfs遍历所有旋转可能得到的情况输出所有不同的结果。得到60种不同的旋转结果。把60种结果分别填入嵌套列表，得到60张数独游戏界面，让自动解数独程序依次解这60张数独表，输出所有有解的情况得到28个结果。自此得到了图一中所有图案的可能的共28种目标位置。

第二阶段，写个计算各个移动方式花费最少步骤的程序和trsbfs和，用以得到各种情况中步数最少的步骤

先看情况简单的图二，图二中所有的图案只有一种目标位置，用2dbfs遍历旋转部分后得到最短操作步数为10步，步骤为“abcbbabacc”，与置换部分的两步交换相加最少情况是12步。

再看图一，用2dbfs依次遍历28种目标位置，得到24种最短旋转操作步数，从1到7步不等（28种目标位置是所有图案的目标位置的不同情况，但在旋转部分的图案只有24种目标位置，因为同一种旋转部分的情况的数独可能有不止一个解）。用trsbfs依次遍历这24种目标位置，得到24中最短的置换操作步数，从（4到6步不等）。以相同序号连接两张表，得到相加最短步数9步。

但是我没考虑用雪花图案开门的情况，最多有2步的误差，如果有大佬感兴趣可以从那24种最优解中，考虑上开门计算最终的最优解。

虽然得到了这个游戏的解，但是以后出现这样旋转的游戏（二维魔方）不凭借计算机要怎么玩呢，我们可以用魔方的通用公式“上顺下逆”，举个例子，我们想通过4和3交换使[1234]->[1243],已知某个操作“上”可以通过旋转这四个元素的中心使这前四个元素轮流进行换位即[1234]->[2341]，又已知“顺”使其中的第三个位置的元素和这个集合之外的元素交换（？代表任意数字）[1234]->[12？4]，而下和逆是上和顺的相反操作，因此有相反的效果，进行一次旋转“上”时，它满足了我们的目的，将其中的一个元素移动到目标位置，但产生了负面影响，破坏了其它三个我们想要保留的位置，此时进行"下"时可以复原三个想要保留的位置，但也还原了我们想移动到位置，此时加两个操作之间加人“顺”它的作用是将“上”之后已经到达目的地的那个元素移开，让“下”进行其他三个位置复原的时候不破坏我们要的那个元素，等完成"下"后，再进行“逆”，把那个临时移走的元素再移动回来，[1234]->[2341]，[2341]->[23？1],[23？1]->[123？],[123？]->[124？]（可能有人疑惑为什么不是[123？]->[1234]，原因是元素的交换是在绝对坐标系下的两个固定位置的元素进行交换，而不是交换某两个特定的元素，看的是盒子而不是盒子里的东西），如果我们能找到一个合适的？（数字）--3，在临时移动时替换到想要保留变化的那个位置上，就能实现[1234]->[2341]。在图二中的（二维魔方）旋转机关中，

[0 0

1 1

2 2

3 3]

（bab'）可以让2的空穴到被1的空穴替换

[2 0

0 1

1 2

3 3]

c 可以让3的空穴被2的空穴替换

[0 0

1 1

3 2

3 2]

于是（bab'）c（ba'b'）c'，先使2到1的位置，3为了保护1临时代替了1,3代替1回到了1原本的位置，1再回来2之前的位置

[0 0

3 1

1 2

2 3]

如果会魔方公式的话，还可以直接使用其他的魔方公式。（说它是魔方是因为它和魔方都是置换群，都是每次转动90度进行一次四阶置换，二维是因为它相较魔方的每个角块只有一个面，二阶是因为它是2*2的，比三阶魔方少个十字-棱块和中心块）

上面的魔方万能公式上顺下逆来源于抽象代数中的交换子：g-1h-1gh，它是所有“置换群”进行置换的万能公式。第一张图中的6个元素之间进行两两交换的游戏也是置换群，6个元素之中实际上只有4个不同的元素，由于4阶置换可以分为3个2阶置换，所以最多3次两两交换就能得到那6个元素的所有排列情况

虽然得到了很好的解决办法，但其实这游戏我也没玩得很明白。首先这个游戏目标我就没看明白（让相连的直线上不存在相同能量源），不应该是让元素所在的直线上不存在相同能量源吗。还有就是第二张图的二阶魔方的中的8个元素可以被转动到8个元素的所有排列情况，而第一张图中的二阶魔方中的6个元素的转动却远满足不了6个不同元素的排列情况呢，希望会证明的大佬告知一下，有错误也请指出，多谢。

第一张图的所有解和魔方步骤计算程序下载地址//

关键词：