在细胞网格中形成对的算法

Question

给定一个由偶数个单元格组成的网格，其中网格边缘的两个单元格缺失，我想以这样的方式形成相邻单元格对，使得没有一个单元格没有伙伴(不计算“缺失” "细胞)。

根据两个“丢失”的单元格的放置位置，我相信做出这样的安排要么总是可能的，要么总是不可能的。我在这里画了两个例子，左边的图是一次成功的尝试，右边的图是一个不成功的尝试(剩下两个单元格没有伙伴)。为摇晃的相机手道歉。

单元格内的箭头指示单元格与哪个邻居合作。

我有两个问题:

1. 我如何知道将“丢失”的细胞放在哪里是安全的，同时又不会让每个细胞都成为伙伴？

2. 根据我上面提到的条件，并且考虑到单元格表可以更大(尽管总是有偶数个单元格)并且不一定是正方形(但矩形)？示例可以是 3x4 网格或 6x6 网格。

我还不知道如何知道将“丢失”的单元格放在哪里是安全的，但只要它们位于已知安全的位置，我的算法如下:

1. For each cell that isn't "missing" or already paired, iterating from top-left to bottom right, horizontally first:
2. Choose a random neighbor to form a pair with: either right or bottom.
3. Check all the cells to see if there are any cells that cannot make a pair, if so:
4. Undo the last pair, go back to 2 and choose the other neighbor.

我完全不知道图论或任何可以帮助我想出一个好的解决方案的东西，所以我非常感谢你能提供的任何帮助。任何不太晦涩的语言的伪代码或真实代码都很棒，简单的文本解释也是如此。

Answer 1

这个问题更广为人知的是 mutilated chessboard problem .由于Gomory，解决方案是首先将棋盘的正方形从1到n^2编号，使得数字k和k + 1相邻(并且1和n^2相邻)。

 1  2  3  4
16  7  6  5
15  8  9 10
14 13 12 11

现在，当且仅当两个删除的数字不是偶数或奇数时，就有一个解决方案。如果第一个删除的数字是a，则平铺(a + 1, a + 2), (a + 3, a + 4)等，直到到达b。然后平铺 (b + 1, b + 2), (b + 3, b + 4) 等，直到到达 a。 (所有加法都以 n^2 为模完成，即它“转角”使得 n^2 + 1 = 1，等等)

这是一个 5x6 编号。

 1  2  3  4  5
30  9  8  7  6
29 10 11 12 13
28 17 16 15 14
27 18 19 20 21
26 25 24 23 22