设为首页收藏本站

切换到窄版

魔方吧·中文魔方俱乐部 › 论坛 › 『其它智力游戏』 › ★ 数学、算术趣题 (Math Puzzles) › 【脑洞求助】一种类Flip Game的通解及思路启发

发新帖

查看: 4644|回复: 4

上一主题

下一主题

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

Rank: 1

积分: 15
帖子: 14
精华: 0
UID: 1336180
兴趣爱好: 速度

电梯直达

跳转到指定楼层

1^#

发表于 2021-12-25 19:24:05 |只看该作者 |倒序浏览

本帖最后由 acan 于 2021-12-25 19:24 编辑

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

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

使用道具举报

Rank: 1

积分: 15
帖子: 14
精华: 0
UID: 1336180
兴趣爱好: 速度

2^#

发表于 2021-12-25 19:31:13 |只看该作者

目前1*1到6*6是用电脑跑了一个小程序计算出来的，6*6棋盘的10支蜡烛的解就有200多种（含对称），7*7的算了快三天了还没出结果

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

使用道具举报

Rank: 4

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

3^#

发表于 2021-12-26 08:38:42 |只看该作者

可以看看这个 https://arxiv.org/pdf/1102.5206.pdf

已有 1 人评分	经验	收起理由
redcarrot	+ 10	感谢分享！

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

使用道具举报

Rank: 2

积分: 350
帖子: 652
精华: 1
UID: 112
性别: 男

4^#

发表于 2021-12-29 09:24:03 |只看该作者

chuchudengren 发表于 2021-12-26 08:38
可以看看这个 https://arxiv.org/pdf/1102.5206.pdf

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

使用道具举报

Rank: 4

积分: 2051
帖子: 1372
精华: 4
UID: 1321618

5^#

发表于 2022-1-3 14:48:55 |只看该作者

居然有人分享了arxiv的文章，倍感亲切

使用道具举报

发新帖

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

GMT+8, 2024-11-27 08:26

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部