一个生成打乱的魔方的算法应该怎么写呢（正文里有详情）

[flowfire]

1. 给定六个面及其顺序（方位信息，凭借这个信息能确保这六个面不拼错拼反或旋转）
2. 要求打乱后的魔方必须能够还原（比如拧一个角块这样的因为不能还原就不行）
3. 不能使用逐步打乱记录法（不能从已还原的魔方一步一步逐渐打乱，必须直接生成打乱后的魔方）


最后解释一下，这不是啥面试题或者实际当中用到的问题，只是无聊忽然想到了。
讲道理其实想问一下有没有 “打乱公式” 这种东西 。。。。

[caaaalabash]

有打乱公式这种东西

[Ayahuasec]

我记得好像有个叫 Kociemba 的算法说明了一个 3 阶的魔方无论打乱成什么样，最多 20 步就可以还原。那从一个已还原的算法随机打乱最多 20 步，应该就可以生成所有可能的能还原的魔法。打乱 20 步的复杂度也不高，不知道为啥条件 3 要规定不能用逐步打乱。。。

[dapang1221]

拆一个魔方就知道了，比如给定一个中心块，那它的对面颜色是不变的，给一个角块，它的这几个面只有这么几种可能。可以提前生成所有的块，再把这些块随机组合起来

一个想法，不知道对不对

[isaacpei]

玩魔的来讲一下把:

3 阶魔方将六个面分别标上字母
上 U 下 D 前 F 后 B 左 L 右 R
以其中一个面为例
U 代表上层顺时针转 90 度
U'代表上层逆时针转 90 度
U2 代表上层转动 180 度，顺逆时针效果一样

如果我记得没错 wca 的打乱规则是随机生成 20 步(相连步骤不重复, 就是不会有连着的两个 U 这种)

[TyteKa]

lz 说是直接生成那个打乱后的结果，而不是打乱步骤。那可以去看看背后的简单数学原理。
https://math.berkeley.edu/~hutching/rubik.pdf
在以复原结果作为 generator 生成的群空间里采一个样就好了。

[imn1]

魔方有公式的，打乱和还原都有
国际赛不同参赛者的起始魔方不是都一样的，就靠这个（些）公式确定“乱”的程度都是相同级别，这样竞赛才公平
换个角度说，就是一定有一个公式，可以确定打乱的程度，不然就拧一下也叫打乱啊

看 LZ 的需求，是要直接“生成”一个乱序的魔方，不然不存在第二条需求

[lizytalk]

你直接从一个还原好的模仿通过随机旋转若干步来打乱不行么？现实中不也是这么做的？

[geelaw]

附言和正文是两个不同的问题。
能够识别可还原魔方，不代表就可以抽取一个随机的可还原魔方。（并不显然具有多项式时间归约。）

可以先研究拧魔方映射的群，然后依据群的结构抽样。然而这样做的结果很可能就是“从还原魔方逐步打乱”。
群的结构也可以导出识别轨道的算法（即如何识别一个魔方是还原魔方被拧魔方映射作用后的结果的方法）。

[yukiww233]

角块 /棱块的颜色和位置.奇偶性校验下就好了

[lemon94]

魔方可移动的是 8 个角和 12 个楞。
楞因为只涉及两个面，所以不存在顺逆时针的顺序。
角复杂一些，要考虑顺逆时针。
如果用 6 个数组代表 6 个面，那么要做的步骤：
1.确定 6 个数组中那 3 个值可以形成角，哪 2 个值可以形成边。
2.对 12 个边进行颜色唯一和颜色正确（对立面的颜色不可形成边）校验。
3.对 8 个角进行颜色唯一和颜色正确（同上）以及颜色顺逆序校验。
我的思路是这样，挺 low 的，等大佬们更好的思路

[Jerry0x2A]

给定一个随机魔方，在不尝试还原的前提下确认其可被还原。

================

只是判断打乱是否正确比较简单，不使用数学算法的话，可以考虑盲拧的处理方式，判断色相、位置是否有矛盾。

如果想要生成合理的打乱，可以看下 wca 官方打乱工具： https://github.com/thewca/tnoodle

[MoYi123]

魔方公式 百度 CFOP，或者简单一点的层先法
1. 查表，看看当前魔方状态有没有符合的，如果没有能套公式的状态，就返回 false
2. 调公式，魔方进入下一个状态
3. 如果魔方 6 面同色就返回 true，否则返回步骤 1

[flowfire]

@Jerry0x2A 如果我没理解错的话，官方打乱工具使用的就是 “逐步打乱” 的方法，而不是 “直接生成打乱后的方块”

[xelatex]

可以。三阶魔方拆散拼回去有 1/12 可能是可以还原的。判断不难，能心算：角块色向和是零（ 1/3 ）、边块色向和是零（ 1/2 ）、角边置换同奇偶（ 1/2 ）。要生成也容易，取随机置换，之后取固定两角修理好奇偶、取一边修理好边色向和、取一角修理好角色向和，即可确保能还原。