问题设定 #

我们有一个矩形棋盘，就像普通的长方形桌面一样。棋盘上任意一个格子放置一枚棋子，两名玩家轮流移动这枚棋子，规则如下：

• 每次只能移动到相邻的格子（禁止对角线移动）；
• 棋子不能回到已经走过的格子（初始位置也算已访问）；
• 无法移动棋子的玩家判负。

请问：先手玩家和后手玩家中，谁拥有必胜策略？

问题背景 #

这个问题是接着一个数学论坛讨论帖的内容延伸而来的，那个帖子专门讨论了起点在棋盘角落的特殊情况，最终得出结论：

• 若棋盘总面积为奇数，后手玩家必胜；
• 若棋盘总面积为偶数，先手玩家必胜。

分析思路 #

我们依然可以用多米诺骨牌划分的思路来推导通用情况的策略：

情况1：棋盘总面积为偶数 #

当棋盘总面积是偶数时，它必然有一条边的长度是偶数。我们可以沿着这条偶数长度的边，把整个棋盘划分成若干个2×1的多米诺骨牌（也就是两两相邻的格子对）。

先手玩家的必胜策略如下：
每次移动时，都把棋子移到当前所在的多米诺骨牌的另一个格子里。后手玩家只能被迫移动到一个新的多米诺骨牌中，此时先手玩家再重复这个操作——移到当前多米诺的另一个格子。显然，先手玩家永远都有合法的移动步骤，后手玩家最终会陷入无棋可走的境地。

情况2：棋盘总面积为奇数 #

当棋盘总面积为奇数时，它的两条边长度都是奇数。我们先把棋盘染成国际象棋棋盘的样式（相邻格子颜色不同），此时四个角落的格子颜色必然相同，我们统一称这个颜色为蓝色，另一种颜色为灰色。

子情况2.1：起点是蓝色格子

此时，除起点外的剩余棋盘可以完全划分成多米诺骨牌。这是因为起点到棋盘四条边的距离的奇偶性完全一致：

• 如果所有距离都是奇数：我们可以在起点周围围出一个“框架”，剩余的棋盘会被分成四个各有一条边长度为偶数的矩形，每个矩形都能继续划分为多米诺骨牌；
• 如果所有距离都是偶数：我们可以沿着行/列向棋盘边缘铺多米诺骨牌，剩余部分同样会被分成四个可划分的偶数边矩形。

此时后手玩家拥有必胜策略：每当先手玩家移动到一个新的多米诺骨牌中时，后手玩家就把棋子移到该骨牌的另一个格子里。这样后手玩家永远都有合法移动，最终先手玩家会先无棋可走。

子情况2.2：起点是灰色格子

由于棋盘总面积为奇数，剩余棋盘里蓝色格子的数量会比灰色格子多2个——而每个多米诺骨牌需要占用1个蓝色和1个灰色格子，因此剩余棋盘无法被完全划分成多米诺骨牌。

从实际例子来看，比如3×3的棋盘，不管双方怎么操作，先手玩家总能获胜；3×5的棋盘看起来也是同样的结果。

待解问题 #

当棋盘总面积为奇数，且起点是灰色格子时：

• 谁拥有必胜策略？
• 是否先手玩家一定能保证获胜？
• 是否无论双方采取何种走法，最终都是先手玩家赢？

备注：内容来源于stack exchange，提问作者Aig