残缺棋盘实现

lyx

残缺棋盘是一个有2^k*2^k个方格的棋盘，其中恰有一个方格残缺。残缺棋盘问题就是要用四种不同形状的三角板覆盖更大的残缺棋盘，三角板类型1.1所示。在此覆盖中要求：两个三角板不能重叠并且三角板不能覆盖残缺方格，但必须覆盖其他所有的方格。

图1.1 三角板类型

本程序采用分而治之方法来解决残缺棋盘问题。这一方法可将覆盖2^k*2^k残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2^k*2^k棋盘一个很自然的划分方法就是将它划分为4个2 ^(k – 1)*2 ^(k -1) 棋盘。当完成这种划分后，4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2^k*2^k棋盘仅仅有一个残缺方格)。首先覆盖其中包含残缺方格的2 ^(k – 1) *2 ^(k -1)残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘,为此将一个三角板放在由这3个小棋盘形成的角上，其中原2^k*2^k棋盘中的残缺方格落入左上角的2^(k – 1) *2 ^(k -1)棋盘。可以采用这种分割技术递归地覆盖2^k*2^k残缺棋盘。当棋盘的大小减为1×1时，递归过程终止。此时1x1的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三角板。本程序将上述分而治之算法编写成一个递归的函数。