一道填色问题

LZC_314

像五子棋一样，每行或每列或每斜行上面，最多连续的白色格子数不超过个， 这样理解是不是合适点。

jx215

LZC_314 发表于 2014-1-3 11:19
像五子棋一样，每行或每列或每斜行上面，最多连续的白色格子数不超过个， 这样理解是不是合适点。

差不多。即每行每列每斜线行不超过3个

Lwins_G

如图，只需填7格即可。
至于6格不可的证明，大家不妨自己试一试。

wayne

看了第一页还是一头浆糊. 看到了第二页 LZC_314的回帖, 才彻底搞明白了.
说白了, 就是 不存在超过3个同色的格子 "连续共线"呗.

jx215

wayne 发表于 2014-1-3 23:53
看了第一页还是一头浆糊. 看到了第二页 LZC_314的回帖, 才彻底搞明白了.
说白了, 就是 不存在超过3个同色 ...

是这样的。

现在13F已经给出了最少7格，只要证明了6格达不到要求就行了

hujunhua

要证明6格不够，篇幅还不算太长。用反证法，假定有一个合适的6格方案图G。

在图G中，行和列包含的黄格数分布都是｛1,1,1,1,2}(不管顺序）,
其中，黄格数为1的行，所含的唯一黄格必定位于列3,4,5. 所以黄格数为2的列必为列3,4 or 5
同样，黄格数为1的列，所含的唯一黄格必定位于行3,4,5. 所以荶格数为2的行必为行3,4 or 5
于是初步可得图1所示的结果：网格的4角必为白格，4边的中间带，即图中的4个灰色带各含一个黄格，剩下的2个黄格在中心九宫格待涂.

图1

图1

列1与列5的黄格必定同行，否则，行3,4,5就会都包含4连白格（暂时），都需要待涂的黄格来分割，但只有2个待涂黄格了。
同理，行1与行5的黄格同列。
所以，将图1的灰幕揭开后，可能的图案有9种，合并那些对称重复的，不重复的有3种，如图2, 图3, 图4 。

图2

图3

图4

在图2,3, 4 中，剩下待涂的两黄格位于灰色格内，无论如何都有斜线含连4白格。所以假设不成立，6格不够。

jx215

hujunhua 发表于 2014-1-5 01:50
要证明6格不够，篇幅还不算太长。用反证法，假定有一个合适的6格方案图G。

在图G中，行和列包含的黄格数 ...

另外想到一个问题，本题是5X5，连续格子<4,若改为一般形式nXn, 连续格子<m,(m<n),这样有无一般的解法？

sheng_jianguo

意思清楚了。
对于规模不大的情况可用用编程法解决。
比如，对5X5矩形，填6格不行，只需填7格即可，共有36种填7格情况。对6X6矩形，填9格不行，只需填10格即可，共有112种填10格情况。