V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
flowfire
V2EX  ›  程序员

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

  •  
  •   flowfire · 305 天前 · 1908 次点击
    这是一个创建于 305 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1. 给定六个面及其顺序(方位信息,凭借这个信息能确保这六个面不拼错拼反或旋转)
    2. 要求打乱后的魔方必须能够还原(比如拧一个角块这样的因为不能还原就不行)
    3. 不能使用逐步打乱记录法(不能从已还原的魔方一步一步逐渐打乱,必须直接生成打乱后的魔方)


    最后解释一下,这不是啥面试题或者实际当中用到的问题,只是无聊忽然想到了。
    讲道理其实想问一下有没有 “打乱公式” 这种东西 。。。。
    第 1 条附言  ·  305 天前
    再解释一下下。其实这个问题的本质说白了就是:
    给定一个随机魔方,在不尝试还原的前提下确认其可被还原。
    14 条回复    2021-01-26 21:21:56 +08:00
    caaaalabash
        1
    caaaalabash   305 天前
    有打乱公式这种东西
    Ayahuasec
        2
    Ayahuasec   305 天前
    我记得好像有个叫 Kociemba 的算法说明了一个 3 阶的魔方无论打乱成什么样,最多 20 步就可以还原。那从一个已还原的算法随机打乱最多 20 步,应该就可以生成所有可能的能还原的魔法。打乱 20 步的复杂度也不高,不知道为啥条件 3 要规定不能用逐步打乱。。。
    dapang1221
        3
    dapang1221   305 天前
    拆一个魔方就知道了,比如给定一个中心块,那它的对面颜色是不变的,给一个角块,它的这几个面只有这么几种可能。可以提前生成所有的块,再把这些块随机组合起来

    一个想法,不知道对不对
    isaacpei
        4
    isaacpei   305 天前
    玩魔的来讲一下把:

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

    如果我记得没错 wca 的打乱规则是随机生成 20 步(相连步骤不重复, 就是不会有连着的两个 U 这种)
    TyteKa
        5
    TyteKa   305 天前   ❤️ 3
    lz 说是直接生成那个打乱后的结果,而不是打乱步骤。那可以去看看背后的简单数学原理。
    https://math.berkeley.edu/~hutching/rubik.pdf
    在以复原结果作为 generator 生成的群空间里采一个样就好了。
    imn1
        6
    imn1   305 天前
    魔方有公式的,打乱和还原都有
    国际赛不同参赛者的起始魔方不是都一样的,就靠这个(些)公式确定“乱”的程度都是相同级别,这样竞赛才公平
    换个角度说,就是一定有一个公式,可以确定打乱的程度,不然就拧一下也叫打乱啊

    看 LZ 的需求,是要直接“生成”一个乱序的魔方,不然不存在第二条需求
    lizytalk
        7
    lizytalk   305 天前
    你直接从一个还原好的模仿通过随机旋转若干步来打乱不行么?现实中不也是这么做的?
    geelaw
        8
    geelaw   305 天前 via iPhone   ❤️ 1
    附言和正文是两个不同的问题。
    能够识别可还原魔方,不代表就可以抽取一个随机的可还原魔方。(并不显然具有多项式时间归约。)

    可以先研究拧魔方映射的群,然后依据群的结构抽样。然而这样做的结果很可能就是“从还原魔方逐步打乱”。
    群的结构也可以导出识别轨道的算法(即如何识别一个魔方是还原魔方被拧魔方映射作用后的结果的方法)。
    yukiww233
        9
    yukiww233   305 天前
    角块 /棱块的颜色和位置.奇偶性校验下就好了
    lemon94
        10
    lemon94   305 天前
    魔方可移动的是 8 个角和 12 个楞。
    楞因为只涉及两个面,所以不存在顺逆时针的顺序。
    角复杂一些,要考虑顺逆时针。
    如果用 6 个数组代表 6 个面,那么要做的步骤:
    1.确定 6 个数组中那 3 个值可以形成角,哪 2 个值可以形成边。
    2.对 12 个边进行颜色唯一和颜色正确(对立面的颜色不可形成边)校验。
    3.对 8 个角进行颜色唯一和颜色正确(同上)以及颜色顺逆序校验。
    我的思路是这样,挺 low 的,等大佬们更好的思路
    Jerry0x2A
        11
    Jerry0x2A   305 天前
    给定一个随机魔方,在不尝试还原的前提下确认其可被还原。

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

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

    如果想要生成合理的打乱,可以看下 wca 官方打乱工具: https://github.com/thewca/tnoodle
    MoYi123
        12
    MoYi123   305 天前
    魔方公式 百度 CFOP,或者简单一点的层先法
    1. 查表,看看当前魔方状态有没有符合的,如果没有能套公式的状态,就返回 false
    2. 调公式,魔方进入下一个状态
    3. 如果魔方 6 面同色就返回 true,否则返回步骤 1
    flowfire
        13
    flowfire   305 天前
    @Jerry0x2A 如果我没理解错的话,官方打乱工具使用的就是 “逐步打乱” 的方法,而不是 “直接生成打乱后的方块”
    xelatex
        14
    xelatex   304 天前 via Android   ❤️ 1
    可以。三阶魔方拆散拼回去有 1/12 可能是可以还原的。判断不难,能心算:角块色向和是零( 1/3 )、边块色向和是零( 1/2 )、角边置换同奇偶( 1/2 )。要生成也容易,取随机置换,之后取固定两角修理好奇偶、取一边修理好边色向和、取一角修理好角色向和,即可确保能还原。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2364 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 09:38 · PVG 17:38 · LAX 01:38 · JFK 04:38
    ♥ Do have faith in what you're doing.