ITPUB论坛-中国最专业的IT技术社区

 找回密码
 注册
查看: 751|回复: 14

请用PL/SQL解欧拉计划599题:魔方的不同着色

[复制链接]
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
发表于 2017-4-16 12:53 | 显示全部楼层 |阅读模式
Distinct Colourings of a Rubik's Cube

Problem 599
The well-known Rubik's Cube puzzle has many fascinating mathematical properties. The 2×2×2 variant has 8 cubelets with a total of 24 visible faces, each with a coloured sticker. Successively turning faces will rearrange the cubelets, although not all arrangements of cubelets are reachable without dismantling the puzzle.
Suppose that we wish to apply new stickers to a 2×2×2 Rubik's cube in a non-standard colouring. Specifically, we have n n different colours available (with an unlimited supply of stickers of each colour), and we place one sticker on each of the 24 faces in any arrangement that we please. We are not required to use all the colours, and if desired the same colour may appear in more than one face of a single cubelet.
We say that two such colourings c1 ,c2 are essentially distinct if a cube coloured according to c1 cannot be made to match a cube coloured according to c2 by performing mechanically possible Rubik's Cube moves.
For example, with two colours available, there are 183 essentially distinct colourings.
How many essentially distinct colourings are there with 10 different colours available?
问题599:魔方的不同着色
著名的魔方有许多迷人的数学属性。2×2×2变体魔方有八个小方块, 总共有24个可见的面, 每个面上都有一张有色的贴纸。连续转动面将重新排列小方块, 但是不拆除魔方的情况下,不是所有小方块排列都可达。
假设我们希望将新的不干胶贴纸贴在一个非标准着色的2×2×2魔方上。具体地说, 我们有 n 种不同的颜色可用 (每种颜色的贴纸都无限供应), 我们在每个面上都贴一张贴纸。我们不一定要使用所有的颜色, 如果需要, 在单个小方块的多个面上可以出现相同的颜色。
如果按照 c1着色的魔方,不能通过旋转的机制, 使魔方变成与着色c2匹配。那么我们说这c1,c2两种着色本质上是不同的。
例如, 有两种颜色可用时, 本质上有183种不同的着色。
求:若有十种不同的颜色,有多少种本质上不同的着色?



招聘 : 系统分析师
论坛徽章:
475
大众
日期:2013-12-31 04:19:40马上有车
日期:2014-03-27 15:59:39马上有车
日期:2014-04-08 17:57:38技术图书徽章
日期:2014-04-21 10:26:402014年世界杯参赛球队: 伊朗
日期:2014-05-23 10:41:312014年世界杯参赛球队: 比利时
日期:2014-06-17 12:09:43itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-09-29 01:14:14itpub13周年纪念徽章
日期:2014-10-08 15:15:25itpub13周年纪念徽章
日期:2014-10-08 15:15:25
发表于 2017-4-17 16:33 | 显示全部楼层
通过展开魔方给魔方编号,然后上色处理?

使用道具 举报

回复
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
 楼主| 发表于 2017-4-17 19:42 | 显示全部楼层
lastwinner 发表于 2017-4-17 16:33
通过展开魔方给魔方编号,然后上色处理?

我设想用一个24个元素的数组存颜色,然后把通过旋转得出的去掉。
10种颜色有10^24个着色

使用道具 举报

回复
论坛徽章:
453
秀才
日期:2015-08-18 09:49:27举人
日期:2015-09-09 10:34:21秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01状元
日期:2015-09-09 10:34:21榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01
发表于 2017-4-17 22:43 | 显示全部楼层
单纯展开是不够的,还要加上扭转旋转翻转各种变型。

先做2015 puzzleup第二题的附加题再说:
http://www.itpub.net/thread-1931570-2-1.html

那个只是标准着色,我的代码就跑了五分多钟。所以用代码模拟是不现实的,必须从数学理论上找到计算公式。

使用道具 举报

回复
招聘 : 系统分析师
论坛徽章:
475
大众
日期:2013-12-31 04:19:40马上有车
日期:2014-03-27 15:59:39马上有车
日期:2014-04-08 17:57:38技术图书徽章
日期:2014-04-21 10:26:402014年世界杯参赛球队: 伊朗
日期:2014-05-23 10:41:312014年世界杯参赛球队: 比利时
日期:2014-06-17 12:09:43itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-09-29 01:14:14itpub13周年纪念徽章
日期:2014-10-08 15:15:25itpub13周年纪念徽章
日期:2014-10-08 15:15:25
发表于 2017-4-18 11:55 | 显示全部楼层
newkid 发表于 2017-4-17 22:43
单纯展开是不够的,还要加上扭转旋转翻转各种变型。

先做2015 puzzleup第二题的附加题再说:

回看了下,枚举不现实,确实得找到数学算法

使用道具 举报

回复
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
 楼主| 发表于 2017-4-18 13:57 | 显示全部楼层
用了http://blog.csdn.net/libin56842/article/details/24151065#
的数据结构来模拟
U=[1,1,1,1];
L=[2,2,2,2];
F=[3,3,3,3];
R=[4,4,4,4];
B=[5,5,5,5];
D=[6,6,6,6];

function show()
println("..",U[1],U[2],"....")
println("..",U[3],U[4],"....")
println(L[1],L[2],F[1],F[2],R[1],R[2],B[1],B[2])
println(L[3],L[4],F[3],F[4],R[3],R[4],B[3],B[4])
println("..",D[1],D[2],"....")
println("..",D[3],D[4],"....")
end;

function turn_x()
F[2],F[4],D[2],D[4],B[3],B[1],U[2],U[4] =
U[2],U[4],F[2],F[4],D[2],D[4],B[1],B[3];
R[1],R[2],R[3],R[4]=R[2],R[4],R[1],R[3];
show();
end;

function turn_y()
F[1],F[2],R[1],R[2],B[1],B[2],L[1],L[2] =
L[1],L[2],F[1],F[2],R[1],R[2],B[1],B[2];
U[1],U[2],U[3],U[4]=U[2],U[4],U[1],U[3];
show();
end;

function turn_z()
U[3],U[4],L[2],L[4],D[1],D[2],R[3],R[1] =
R[1],R[3],U[3],U[4],L[2],L[4],D[1],D[2];
F[1],F[2],F[3],F[4]=F[2],F[4],F[1],F[3];
show();
end;

----
julia> show()
..11....
..11....
22334455
22334455
..66....
..66....

julia> turn_x();
..15....
..15....
22314465
22314465
..63....
..63....

julia> turn_y();
..55....
..11....
65223144
22314465
..63....
..63....

julia> turn_z();
..55....
..34....
61213144
21236465
..52....
..63....

julia>

使用道具 举报

回复
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
 楼主| 发表于 2017-4-19 10:00 | 显示全部楼层
这里的数据结构能节约空间,http://blog.miskcoo.com/2017/03/how-to-reconstruct-rubik-cube
是否newkid的也是这个思路

使用道具 举报

回复
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
 楼主| 发表于 2017-4-19 19:27 | 显示全部楼层
newkid 发表于 2017-4-17 22:43
单纯展开是不够的,还要加上扭转旋转翻转各种变型。

先做2015 puzzleup第二题的附加题再说:

标准色块改成贴纸后怎么排除重复,我直接把你的12改为[1,2][1,3][1,4][1,5][1,6]等多出来好多种

使用道具 举报

回复
论坛徽章:
453
秀才
日期:2015-08-18 09:49:27举人
日期:2015-09-09 10:34:21秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01状元
日期:2015-09-09 10:34:21榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01秀才
日期:2015-09-09 10:33:01
发表于 2017-4-20 04:02 | 显示全部楼层
什么代码?什么12?
标准六色只是一个特例,要把其它所有颜色排列组合都尝试一遍是不现实的。

使用道具 举报

回复
论坛徽章:
393
雪佛兰
日期:2013-12-04 20:30:02马上有钱
日期:2014-03-11 11:59:122014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13
 楼主| 发表于 2017-4-20 05:36 来自手机 | 显示全部楼层
12是你提供的连接中sql最后一步distinct的23个字符串的组成部分,贴纸3面有8种,用1-8代表

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则

久等啦!10张门票开启你的DTCC2017之旅~

2017中国数据库技术大会将于2017年5月11-13日如约而至,本届大会以“数据驱动•价值发现”为主题,共设定2大主场和21个技术专场,云集海内外120+位技术大牛,共同探讨Oracle、MySQL、NoSQL、云端数据库、区块链、深度学习等领域的前瞻性热点话题。
即日起,填写DTCC2017会前调查问卷,即有机会赢取价值2600元的大会门票1张!仅限10张!
----------------------------------------
活动截止时间:2017年5月5日统一公布

问卷入口>>
TOP技术积分榜 社区积分榜 徽章 电子杂志 团队 统计 虎吧 老博客 知识索引树 读书频道 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档 | IT博客
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛 | SAP ERP系统
CopyRight 1999-2011 itpub.net All Right Reserved. 北京皓辰网域网络信息技术有限公司版权所有 联系我们 网站律师 隐私政策 知识产权声明
京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表