魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 3939|回复: 4

【脑洞求助】一种类Flip Game的通解及思路启发 [复制链接]

Rank: 1

积分
15
帖子
14
精华
0
UID
1336180
兴趣爱好
速度
发表于 2021-12-25 19:24:05 |显示全部楼层
本帖最后由 acan 于 2021-12-25 19:24 编辑

问题如下 — 在n*n的方格棋盘内摆放蜡烛,每个蜡烛可以照亮上下左右及自身5格,问最少需要多少根蜡烛点亮整个棋盘?

题目与翻转点灯游戏非常相似,不过不会熄灭已经照亮的格子,目前在1*1到6*6我们算出了明确答案了,再往上暂时还没有穷解出来,,,,,不知道有没有人能给出问题的通解,或者了解过类似的问题,提供一下解题的思路

aa.jpg


bb.jpg

Rank: 1

积分
15
帖子
14
精华
0
UID
1336180
兴趣爱好
速度
发表于 2021-12-25 19:31:13 |显示全部楼层
目前1*1到6*6是用电脑跑了一个小程序计算出来的,6*6棋盘的10支蜡烛的解就有200多种(含对称),7*7的算了快三天了还没出结果

很有可能是程序算法不够精简。。。所以有大神能提供算法思路也可以分享一下

使用道具 举报

Rank: 4

积分
2052
帖子
1452
精华
5
UID
84402
性别

四年元老 十年元老 十二年元老

发表于 2021-12-26 08:38:42 |显示全部楼层
可以看看这个 https://arxiv.org/pdf/1102.5206.pdf
已有 1 人评分经验 收起 理由
redcarrot + 10 感谢分享!

总评分: 经验 + 10   查看全部评分

使用道具 举报

Rank: 2

积分
306
帖子
608
精华
1
UID
112
性别

十四年元老 十年元老 十二年元老 十八年元老 十六年元老

发表于 2021-12-29 09:24:03 |显示全部楼层
chuchudengren 发表于 2021-12-26 08:38
可以看看这个 https://arxiv.org/pdf/1102.5206.pdf

谢谢提供信息。虽然没细看,但是看结论这篇论文完美解决了楼主的疑问。

使用道具 举报

Rank: 4

积分
2050
帖子
1371
精华
4
UID
1321618

收藏爱好者 六年元老 八年元老

发表于 2022-1-3 14:48:55 |显示全部楼层
居然有人分享了arxiv的文章,倍感亲切

使用道具 举报

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

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-28 16:56

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部