內固——n*n的棋盘上最多可以放多少个马

优秀书籍

定理：

如果n是偶数（n>4）那么n*n的棋盘有一个哈密顿圈。

如果n是奇数（n>3）那么n*n的棋盘有一个哈密顿链。

像这样的图还可以构造一些，不过基本上都差不多。

总结起来就是，最中间的格子是比较特殊的，上图中标号1-8的这8个格子构成1个圈，

其余的16个格子也构成1个圈，相当于5*5的棋盘其实就是3个圈组合而成，只要适当地选择断点，即可把3个圈连接成一条链。

如果选取的起点不同，得到的哈密顿链还是略有区别的。

比如：112象棋（12）

关于上面的2个定理，书上的意思是用数学归纳法来证明，从n=k变成n=k+4相当于在原来的基础上，套上了一个宽度为2的边框。这个边框是若干个哈密顿圈组成的，只要在适当的地方断开，就可以和里面的k*k连接起来。不过这个定理是否正确，我也不确定。

下面讨论，7*7的棋盘去掉中间的3*3如何形成哈密顿圈。

首先，角落的点只有2个邻居，那么在圈里面，这2个点也一定都是他的邻居。

其他的，以此类推，可以得到下图：

对于那些已经连了2条线的点，自然是没有任何悬念了，所以接下来只需要考虑那些恰好连了1条线的点该如何连接起来。将上图化简如下：

黑色的线表示一定相连，红色的线表示可能相连。

这样，可以得到这16个点的哈密顿圈：

与此对应，可以得到原图：

这是由2个哈密顿圈构成的。

这样，整个通过把大的圈断开一个地方，可以得到下图：

在把紫色的哈密顿圈和这个长为41的哈密顿链连接起来，即可得到7*7的哈密顿链

下面用这个定理来分析，n*n的棋盘上（n>4）最多可以放多少个马，使得它们互不攻击，即马的内固数是多少。

如果n=2*k，因为有一个哈密顿圈，圈的大小是4*k*k，所以内固数不超过2*k*k，即n*n/2。

如果n=2*k+1，因为有一个哈密顿链，圈的大小是4*k*k+4*k+1，所以内固数不超过2*k*k+2*k+1,即（n*n+1）/2。

我们将棋盘按照国际象棋的棋盘来染色，使得白色的格子数-黑色的格子数=0或1。

也就是说，白色格子有（n*n+1）/2个，在所有的白色格子里面放马，这些马都不能互相攻击。

所以，马的內固数是（n*n+1）/2

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/52634492