图钉棋的游戏

小学教育网

　　在3×3的钉板上，把一枚红图钉插在其中一个角落上，然后在除了对角之外的其余洞中，插上蓝图钉，如图所示。图钉可以向上、向下或横向移动到相邻的空位，但不能沿对角线方向移动，也不能跳过别的图钉。


　
　　请以最少的移动次数，使红图钉到达对角的位置。
　　当你认为已找到3×3钉板的最好解答后，请试着在4×4的钉板上，然后在5×5的钉板上解同样的问题。
　　这时你应该已考虑出一套基本策略，可以将红图钉移动到板上的任何位置。因此，可以试着用公式说明在n×n的钉板上，移动红图钉到对角所需最少次数N，以及n与N的关系。
解答与分析
　　在3×3的钉板上需走13步。
　　在4×4的钉板上需走21步。
　　在5×5的钉板上需走29步。

　　N=8n-11
　　这些数字和公式也许经多次的尝试后就可以得到，不过还是应作更深入的探讨。
　　先把3×3钉板上的各个位置从1到9编号，如图1。在红图钉移动之前，旁边必须要有空位。最简单的做法，就是移动最靠边的3枚图钉，使空位按照1→2→3→4的次序移动，这样位于9的红图钉就可以在第四次移动时到达4。现在红图钉可以用一种有系统的方式，按部就班地以向右、向上、再向右的路线移动，最后抵达对角；每一步都可以用3枚图钉的移动说明(图2)。

　　图3分别表示在3×3、4×4、5×5的钉板上，红图钉的移动路线，以及每一步所需要的移动次数。

　　因此在n×n的钉板上，总共所需的移动次数为：
N＝(2n-2)＋(2n-3)×3＝8n-11
　　尝试在长方形的钉板上探讨类似问题。