如何用数据结构存储魔方

如果–我是说如果–魔方只是6个各有9个色块的面，每个色块可以有6种颜色，那么它应该有n=6^(6*9)=1047532535594334222593508922191671036215296种不同状态。我想这个数字如果可以折叠，还是不要放出来比较好。

但这一数字中包含很多绝不可能的状态（比如一个角块三个面都是黄色），随便抽出一个状态，符合魔方现实规律的概率几乎是0。毕竟，有那么多角块和棱块。也就是说，面向色块的存储模型必定会包含大量冗余。即使我们紧凑存储，它也需要log(n)=139.59个比特。

既然如此，我们来看看魔方到底是什么。我们都知道扭了一个角的魔方永远无法复原，实际上魔方有大量这样的状态。对于棱块、角块和中心块，情况非常不同。

首先是中心块。中心块决定了魔方本身的方向。由于它们本身就是参考系，故只有一种状态。这不足以让信息有差异–所以我们不需要存储它。

然后…这里必须拿出前人总结出的魔方定律。它们有方法推导，但过程比较复杂。（你不会想看到！）这里直接放自然语言表述：

棱块方向守恒：被翻转的棱块数量必须是偶数。

角块方向守恒：所有角块的旋转角度之和必须是360°的倍数。

排列奇偶性守恒：棱块错位的步数和角块错位的步数，其奇偶性必须一致。

即使有这些限制，魔方大部分棱块和角块的朝向仍然相当自由。

对于棱块的朝向，我们任意确定12个棱块中的11个，总会有一个棱块和它们在一起时，能满足第一条定律，原因不言自明。

角块朝向也是如此–7个角块确定时，第8个角块总是能选0°，120°和240°之一来满足第二条定律。

角块位置也只需要存储其中7个，因为用排除法可以确定第8个。

棱块的位置，在角块位置确定后，就只需要储存前10个，根据第三条定律，剩余两个的相对顺序是固定的。

所以，一个完整的，储存魔方状态的数据结构大概长这样—-

struct RubiksCube {
    // 角块位置
    corner_pos: [u8; 7],
    // 角块朝向
    corner_ori: [u8; 7],
    // 棱块位置
    edge_pos: [u8; 10],
    // 棱块朝向
    edge_ori: [u8; 11]
}
impl RubiksCube {
    fn new() -> RubiksCube {
        // 我们用这个状态表示已复原的魔方
        RubiksCube {
            corner_pos: [1, 2, 3, 4, 5, 6, 7],
            corner_ori: [0, 0, 0, 0, 0, 0, 0],
            edge_pos: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
            edge_ori: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        }
    }
}

等等…如果我们要进一步压缩内存呢？

corner_pos的范围是1~7，3个比特可以容纳，而corner_ori（0~2）需要2个比特。edge_pos（0~10）需要…4个比特，可惜。而edge_ori（0~1）只需要1个。我们得到7*3+7*2+10*4+11*1，也就是86比特。

如果我们数据限制在二进制的框架内，86是需要的最小值。但这其中有很多不可能的状态–比如，如果某个序列的“edge_pos”字段某元素是0xE（14），事情就不对劲了。

为了最大限度地消除无效状态，我们可以引入混合进制编码（Mixed-radix Encoding）。此时状态数量接近比特序列能承载信息的极限，为

在二进制下，需要最少66个比特。

它还是大于64。魔方太坏了。