【東方】把三阶魔方的状态数存入数据库列表，需要多大空间？

haohmaru

原帖由 pengw 于 2009-9-27 19:47 发表
角块编号:8 ,二进制3位
角块位置:8,二进制3位
角块色向:3,二进制2位
棱块编号:12,二进制4位
棱块位置:12,二进制4位
棱块色向:2,二进制1位
中心块编号:6,二进制3位
中心块色向:4,二进制2位
----------------- ...

这个思路不错！！
如果按照盲拧的思路
把任一状态按照【角方向、角位置、棱方向、棱位置】
四个数值or数组来确定
那每个状态表示起来就容易多了

pengw

8楼计算有误，正确的应该是
------------------------------------
全色魔方一个状态最少位数：8*2+12*1+6*2=16+12+12=40位=5个字节
全色魔方一个状态最少位数：8*2+12*1=28位=4个字节

[ 本帖最后由 pengw 于 2009-9-27 20:57 编辑 ]

Pyrenees

我还是不懂，这个“9字节”到底是不是魔方一个状态的大小，因为这个9字节是LZ用魔方总状态数换算出来的…不理解

noski

意思是，魔方4千亿亿个状态中的任何一个状态，都可以在这9个字节中找到一个唯一的编号与之一一对应。这样，9个字节就足以存放下这么多个状态的信息。
不知道pengw在12楼是怎样化简到那么少的字节的。。。

pengw

8个角块:用3个位可以完全标识每个角块身份,每个角块用2个位可以表示所有色向
角块共须:40位

12个棱块:用4个位可以完全标识每个棱块身份,每个棱块用1个位可以表示所有色向
棱块共须:60位

6个心块:每个心块用二个位可以标识所有色向
心块共须:12位

每个棱块或角块数据的位置映射该块当前在魔方上的位置,心块数据依序每二位对应一个心块色向状态

全色三阶魔方:8*5+12*5+12=112位,14个字节
纯色三阶魔方:8*5+12*5      =100位,13个字节

---------------------

上面几楼的分析不完整,以此贴为准,希望看到更省空间的编码方式.

显然,编码长度应大于总状态数的二进制位数,此理不言自明.

[ 本帖最后由 pengw 于 2009-9-28 11:13 编辑 ]

noski

我想一个容易使用的编码，应该是根据该编码，通过简单的运算就可以得到魔方的具体状态，而不是在一个巨大的表中去搜索。所以前面说的用8~9个字节的编码并不太实用。

楼上 8*(3+2)+12*(4+1) = 100 bit 这个编码方式，虽然多了几个字节，但极大节省了解码运算时间。

还可以稍微化简，因为用2个bit来表示角色向0~2，还有用4个bit来表示棱位置0~11，均有一点点浪费。另外根据魔方的性质，最后一个角块和最后一个棱块也可以确定。不过这样一来，由编码算出状态，就需要一点运算时间了。

stray

http://www.jaapsch.net/puzzles/compcube.htm


好像不需要存具体状态是什么样的，只需按照状态标号存2bit的离初始状态的距离即可。

乌木

那么，如果照你说的，用状态标号代替具体状态，岂非先要有个四千亿亿个态、以及各态和初态的距离（当然是指最少步）的表格？如果是的，能具体列出那四千亿亿个态的表格吗？此外，好像至今还没有解决两态之间的最少步问题吧？
当然，上面各位说的也是无法真的把四千亿亿个具体态存起来的，只是探讨总的空间该多大而已。
事情是不是这样？

[ 本帖最后由 乌木 于 2009-9-29 10:01 编辑 ]

pengw

续15楼:
比较而言,用字母表达一个全色魔方状态至少须要60个字母,角:24,棱:24,心:12,每个字母占一个字节,共须480位,比15楼的四倍还多.

stray

都存不下来，只不过提供一种方法，和二阶的计算一样，遍历之后存下所需步数的表格。

现在的2 phase算法分两个阶段，步数表格就小了很多（但还是存不下，所以现在Cube Explorer是分别建立角和楞的索引表 ，虽然treesearch会多算一些，但存储小多，一共几十M吧，第一次安装时创建），但是这样算下来一般是次优步数了，如需验证是最少步，计算量还是很大，需要验证很多不同的pahse1的soluton，看能不能使phase2步数变得很短。

[ 本帖最后由 stray 于 2009-9-29 10:54 编辑 ]