魔方吧·中文魔方俱乐部

标题: 【脑洞求助】一种类Flip Game的通解及思路启发 [打印本页]

作者: acan 时间: 2021-12-25 19:24:05 标题: 【脑洞求助】一种类Flip Game的通解及思路启发

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

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

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

附件: bb.jpg (2021-12-25 19:22:04, 14.3 KB) / 下载次数 39
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc1OTY1fDhkY2NkNTY5fDE3MTQ4MTI0NDF8MHww

附件: aa.jpg (2021-12-25 19:22:04, 47.87 KB) / 下载次数 40
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc1OTY0fDk3MjZjYTFkfDE3MTQ4MTI0NDF8MHww

作者: acan 时间: 2021-12-25 19:31:13

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

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

作者: chuchudengren 时间: 2021-12-26 08:38:42

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

作者: xwfh2000 时间: 2021-12-29 09:24:03

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

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

作者: 折翼蚂蝗 时间: 2022-1-3 14:48:55

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

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)