星战的4N结论

2022-03-14 23:38 作者:嘉和逆天 0人读过 | 我要投稿

星战的规则详见谜题规则介绍#5 放置类——星战(starbattle)

这个结论很简单：

(1)N>1时，每行每列N个星星的星战至少需要4N*4N的盘面才能放下，并且

(2)如果不限制宫的情况下，4N*4N的盘面每行每列放N个星星恰有两个解。

(3)而N=1时，除去一个1*1的盘面有唯一解以外，剩下的结论同上。

注：以下内容证明较多较枯燥，如果不想看证明而只想知道两个解长什么样，只需要看图即可。

由于证明了(1)(2)可以推出(3)，故这里只证(1)(2)。

证明(1)是很简单的，只需要利用星战的一个常用结论：任何2*2区域内最多只有1个星星。

假如盘面是M*M的，而每行每列需要放N个星星，那么星星的总数是N*M个。由于任何2*2区域内最多只有一个星星，因此盘面的面积不能小于星星数目的4倍，即盘面的面积不小于4N*M。而盘面的面积就是M*M，因此M≥4N。

对于(2)，我们来证明一下。

首先构造M=4，N=1时的两个解，这里只有两个解也是显然的：

对于N>1的情况，构造其实是类似的。至于为什么呢，我们回头看看N=1的情况，将整个盘面分成2N*2N个2*2的部分，如下所示：

那么，这里的每一个2*2都恰好有一个星星。我们将上图中每一块2*2视为一个新的“单元格”，将这些“单元格”所在的行列称为“大行”和“大列”。那么我们有一个结论：同一个大行的星星，要么都在大行内2*2的左侧两格，要么都在右侧两格；同一个大列的星星，要么都在大行内2*2的上侧两格，要么都在下侧两格。

这个小结论证明并不难，以同一个大列的为例，我们看盘面的第2行，它要有N个星星。如果某个大列的第2行存在星星，那么由区块删减，该大列的第3行就不能是星星，则该大列的第4行就必须有星星，以此类推，那么这些大列的星星就都在下侧的两格。那么，由于偶数行的星星已经满了，剩下的大列的星星只能在奇数行，也就是说这些剩下的大列的星星都在上侧两格。大行上的情况是同理的。

那么根据上述结论，其实我们可以给每个大列标一个上/下的箭头，来表示该大列的星星全在上侧或全在下侧，可以给每个大行标一个左/右的箭头，来表示该大行的星星全在左侧或全在右侧。这样的话，每个大单元格可以看成是有两个箭头，来指示星星在该大单元格中的位置。

我们考虑一下还有哪些2*2没有使用。很明显，两个大单元格之间的2*2在论证上述结论的时候也用到了，那么就只有四个大单元格交叉的2*2未使用了。

这样的2*2限制了以下两种情况：

也就是说，如果列里从左到右出现了上（下）变成下（上），那么行里就不能有从上到下的左（右）变成右（左）。

看上去有点绕，但是我们可以得到全盘的方向分布只有两种情况：

1）列是从左到右连续N个上之后连续N个下，行是从上到下连续N个右之后连续N个左；

2）列是从左到右连续N个下之后连续N个上，行是从上到下连续N个左之后连续N个右。

证明的话并不难。先看列上，因为列上必然是N个上和N个下，所以中间至少会出现一次上到下或者下到上的变化。我们假设是中间出现了上到下的一次变化，那么由上述结论，行里面就完全不可以出现左到右的变化。因此，行里面只能是连续N个右之后连续N个左。那么行里面也有且仅有一次右到左的变化，也就是说列里就完全不可以出现下到上的变化，因此列里面只能是连续N个上之后连续N个下，这就是上面的情况1)。另一种情况的说明是类似的。

也就是说，我们证明了解只有两种情况：

将盘面沿两条中线分成四个2N*2N大区域，每个小盘面内有N*N个2*2的大单元格，那么

1）左上大区域的星星在单元格右上，右上大区域的星星在单元格右下，左下大区域的星星在单元格左上，右下大区域的星星在单元格右下；

2）左上大区域的星星在单元格左下，右上大区域的星星在单元格左上，左下大区域的星星在单元格右下，右下大区域的星星在单元格右上。

感觉文字说明看不懂？没关系，下面是N=2的时候的两个解，知道之后大家就可以类推出更大的N的时候的解了。