在网格中形成对的算法

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

这个问题更好地称为残缺的棋盘问题.由于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