讨论：魔方状态的最小表示方法

aubell

普通三阶，六色，无图案的魔方，
表示它的状态，最少需要多少bit ？
无论是否方便操作。

（直接拿总状态数向2取对数吗？
要比这个小才行。
直接取对数的结果是 65.23 ，
也就是说要 66 位。
假如可以少两位，就可以利用一个 64 位整数表示了。
48同态用上，可以少5位，用61位。不知是否这样？
欢迎大家讨论：具体怎样实现64位存储，或61位？
或者更少的位数？
）

jshyhzj

去我网站上下一个跑下就晓得了，PC机上可以搜索到千万级别，你也可以下载源代码，设置为.net 4.0性能又可以提高50%，如果平台设为Intel 64能够搜索更多节点。通常得到的解在30步以内，三分钟以内搜到，和参数设置相关，单纯追求快速，可以在数秒内得到解，只是这时质量比较差，50步左右

小明的马甲

请教楼上，你说的你的软件计算速度极快，有多快，每秒可以搜索到多少个状态？

52封3

看不懂啊...我还以为讨论魔方的最少状态呢

jshyhzj

单纯讨论最少多少位能记录魔方的所有状态是没有任何意义, 关于熵信息论有全套的计算公式

小明的马甲

是否考虑过预处理？

另外你的非常快速。。有多快？

jshyhzj

我的魔方还原软件用了6个Int32来表示，每个Int32表示一个面：每个面有8个可动的块，每个色块可以有6种颜色，因此4位表示一个色块的颜色。这样都是半字节，处理起来很快速，所以我用穷举能够非常快速地搜索。
http://www.telossoft.com.cn/OtherRubikCube.aspx

对于4阶魔方我也考虑过了，可以用6个Int64表示，同样每个色块半字节。
4阶魔方旋转估计需要通过查表处理，3阶我通过位运算在处理。

骰迷

我不是很懂优化，但我会以打乱步骤表示状态。

yq_118

不过这个48同态用起来不知道怎么样。
对于一些自同够（感觉叫同构合理些），例如对称棋盘的状态，不管怎么用旋转，镜像，取逆，都是它本身，这样就是在压缩后还是占1种状态。而对于一些不具有对称性的状态，96种可以压缩到一种。
实际操作起来应该很复杂。

这点在OLL，PLL中也能够体现出来。

yq_118

48同态可以减少某些表的大小，例如距离表，两种状态如果是48同构的话（貌似加上逆可以达到96），那么它们的最少步还原步数就一样多，就可以节约存储空间。