棋盘覆盖问题

1、Tromino谜题分治法分治法 分分治法的基本思想治法的基本思想 对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题， 然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divide and conquer)。 分治法的三个步骤 分治法在每一层递归上由三个步骤组成： (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3

2、) 合并(combine)： 将各子问题的解合并为原问题的解。 它的一般算法设计范型如下： DIVIDE&CONQUER (P) 1 if |P|c 2 then return(DSOLVE(P) 3 else divide P into k into P1, P2, , Pk subproblems 4 for i 1 to k 5 do si DIVIDE&CONQUER(Pi) 6 SCOMBINE(s1, s2, , sk) 7 return S 从分治法的一般设计模式可以看出， 直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。 设T(n)表

3、示用分治法求解规模为n的问题所需的计算时间，如果问题规模足够小，比如nc，则可直接求解问题，T(n)=(1)。 假定将原问题分为k个子问题，每一个子问题规模是原问题的1/m， 若分解该问题和合并该问题的时间分别为D(n)和C(n)，则算法的计算时间T(n)可表示为如下的递归方程： )()()/() 1 ()(nCnDmnkTnTnc nc 如果n为m的幂，分解该问题和合并该问题的时间为f(n)，则该递归方程的解为 1log0log)/()(niiikmmmnfknnT子问题2的解子问题2的解原始问题的解原始问题的规模是n子问题1的规模是n/2子问题2的规模是n/2 图解在一个2k2k （k0）

4、个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用如图（b）所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且骨牌之间不得有重叠。(a) k=2时的一种棋盘时的一种棋盘 (b) 4种不同形状的种不同形状的L型骨牌型骨牌棋盘覆盖问题棋盘覆盖问题 残缺棋盘是一个有残缺棋盘是一个有2 2k k2 2k k （k1k1）个方格的棋盘，其中恰有）个方格的棋盘，其中恰有一个方格残缺。图一个方格残缺。图4-74-7给出给出k=1k=1时各种可能的残缺棋盘，其时各种可能的残缺棋盘，其中残缺的方格用阴影表示。中残缺的方格用阴影表示。 号 号 号 号这样的棋盘我们称作这样

5、的棋盘我们称作“三格板三格板”，残缺棋盘问题就是要用这，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：1 1）两个三格板不能重叠）两个三格板不能重叠2 2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为在这种限制条件下，所需要的三格板总数为(2(2k k2 2k k -1 )/3 -1 )/3。 棋盘覆盖问题棋盘覆盖问题 1 1）问题分解过程如下：）问题分解过程如下：以以k=2k=2时的问题为例，用二分法进行分解，得到的是如下图，时的问题

6、为例，用二分法进行分解，得到的是如下图，用双线划分的四个用双线划分的四个k=1k=1的棋盘。但要注意这四个棋盘，并不的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如中的残缺方都是与原问题相似且独立的子问题。因为当如中的残缺方格在左上部时，第格在左上部时，第1 1个子问题与原问题相似，而右上角、左个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为下角和右下角三个子棋盘（也就是图中标识为2 2、3 3、4 4号子号子棋盘），并不是原问题的相似子问题，自然也就不能独立棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个号三格板（图中阴影

7、）覆盖求解了。当使用一个号三格板（图中阴影）覆盖2 2、3 3、4 4号三个子棋盘的各一个方格后，如号三个子棋盘的各一个方格后，如4-84-8右图所示，我们把覆右图所示，我们把覆盖后的方格，也看作是残缺方格（称为盖后的方格，也看作是残缺方格（称为“伪伪”残缺方格），残缺方格），这时的这时的2 2、3 3、4 4号子问题就是独立且与原问题相似的子问题号子问题就是独立且与原问题相似的子问题了。了。 从以上例子还可以发现，当残缺方格在第从以上例子还可以发现，当残缺方格在第1 1个子棋盘，用个子棋盘，用号三格板覆盖其余三个子棋盘的交界方格，可以使另外三号三格板覆盖其余三个子棋盘的交界方格，可以使另外三

8、个子棋盘转化为独立子问题；同样地（如下图所示），当个子棋盘转化为独立子问题；同样地（如下图所示），当残缺方格在第残缺方格在第2 2个子棋盘时，则首先用号三格板进行棋盘个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第覆盖，当残缺方格在第3 3个子棋盘时，则首先用号三格板个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第进行棋盘覆盖，当残缺方格在第4 4个子棋盘时，则首先用个子棋盘时，则首先用号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。独立子问题。如下图：如下图：同样地同样地k=1k=1，2 2，3 3，4 4都是如

9、此，都是如此，k=1k=1为停止条件。为停止条件。图图 其它其它4 4* *4 4的残缺棋盘的残缺棋盘分治策略2k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盘分割棋盘分割(b) 构造相同子问题构造相同子问题 技巧在于技巧在于划分棋盘划分棋盘，使每个子棋盘均包含一，使每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题棋盘覆盖问题k2k2时时，可将，可将2k2k2k2k的棋盘划分为的棋盘划分为4 4个个22（k-1k-1）22（k-1k-1）的子棋盘）的子棋盘，这样，这样划分后，由于原棋盘只划分后，由于原棋盘只有

10、一个特殊方格，所以，这有一个特殊方格，所以，这4 4个子棋盘中只有一个子个子棋盘中只有一个子棋盘包含该特殊方格，其余棋盘包含该特殊方格，其余3 3个子棋盘中没有特殊方个子棋盘中没有特殊方格。为了将这格。为了将这3 3个没有特殊方格的子棋盘转化为特殊个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个棋盘，以便采用递归方法求解，可以用一个L L型骨牌型骨牌覆盖这覆盖这3 3个较小棋盘的会合处个较小棋盘的会合处，从而，从而将原问题转化为将原问题转化为4 4个较小规模的棋盘覆盖问题。递归地使用这种划分策个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为略，直至将棋盘

11、分割为1 11 1的子棋盘。的子棋盘。分治策略2 2）棋盘的识别）棋盘的识别 棋盘的规模是一个必要的信息，棋盘的规模是一个必要的信息，有了这个信息，只要知道其左有了这个信息，只要知道其左上角的左上角方格所在行、列上角的左上角方格所在行、列就可以唯一确定一个棋盘了，就可以唯一确定一个棋盘了，残缺方格或残缺方格或“伪伪”残缺方格直残缺方格直接用行、列号记录。接用行、列号记录。 trtr 棋盘中左上角方格所在行。棋盘中左上角方格所在行。 tctc 棋盘中左上角方格所在列。棋盘中左上角方格所在列。 drdr 残缺方块所在行。残缺方块所在行。 dl dl 残缺方块所在列。残缺方块所在列。 size si

12、ze 棋盘的行数或列数。棋盘的行数或列数。dcdrtrtcsize棋盘覆盖问题中的数据结构棋盘覆盖问题中的数据结构下面介绍棋盘覆盖问题中数据结构的设计：下面介绍棋盘覆盖问题中数据结构的设计：（1 1）棋盘：用二维数组）棋盘：用二维数组boardsizesizeboardsizesize表示一表示一个棋盘，其中，个棋盘，其中，size=2size=2k k。为了在递归处理的过程。为了在递归处理的过程中使用同一个棋盘，将数组中使用同一个棋盘，将数组boardboard设为全局变量；设为全局变量；（2 2）子棋盘：在棋盘数组）子棋盘：在棋盘数组boardsizesizeboardsizesize中，

13、中，由子棋盘左上角的下标由子棋盘左上角的下标trtr、tctc和棋盘边长和棋盘边长s s表示；表示；（3 3）特殊方格：用）特殊方格：用boardboarddrdrdcdc表示，表示，drdr和和dcdc是是该特殊方格在棋盘数组该特殊方格在棋盘数组boardboard中的下标中的下标; ;（4 4） L L型骨牌：一个型骨牌：一个2 2k k2 2k k的棋盘中有一个特殊方的棋盘中有一个特殊方格，所以，用到格，所以，用到L L型骨牌的个数为型骨牌的个数为(4(4k k- -1)/31)/3，将所，将所有有L L型骨牌从型骨牌从1 1开始连续编号，用一个全局变量开始连续编号，用一个全局变量t t

14、表表示示算法分析算法分析 假设有如下8*8的棋盘，其中着红色块为少了的方块：第一步先讨论问题的最小单位，即第一步先讨论问题的最小单位，即问题的原型。此时只有四个方格的问题的原型。此时只有四个方格的棋盘，假设其中任意一块是缺失的，棋盘，假设其中任意一块是缺失的，则只需要直接填充其余三块即则只需要直接填充其余三块即可可第二第二步，问题扩大，归纳其中的规步，问题扩大，归纳其中的规律。变成律。变成4 4* *4 4个的棋盘方格个的棋盘方格此时可以看到如果以方格中心交叉此时可以看到如果以方格中心交叉线分别为线分别为X X轴，轴，Y Y轴。则到了第二步，轴。则到了第二步，每个象限都会有一个方格着色了。每个

15、象限都会有一个方格着色了。并且，如果初始缺失的方格在其中并且，如果初始缺失的方格在其中任意一个象限，则其余象限分布的任意一个象限，则其余象限分布的着色方块必须在与原点最近的方块。着色方块必须在与原点最近的方块。这一步可以总结出一个关键点，着这一步可以总结出一个关键点，着色方块所在的象限。色方块所在的象限。为了得到着色块所在象限，我们必为了得到着色块所在象限，我们必须知道当前方格个数以及原点。但须知道当前方格个数以及原点。但是整个问题分析过程中只有一个原是整个问题分析过程中只有一个原点，如果想设计一个高效的算法让点，如果想设计一个高效的算法让其自动分解执行的话必须在各个子其自动分解执行的话必须在

16、各个子问题上都一个变量，于是利用了当问题上都一个变量，于是利用了当前方格的第一个点，即第一行第一前方格的第一个点，即第一行第一列的方块。这样，当算法继续执行列的方块。这样，当算法继续执行的时候会分解为不同的第一节点。的时候会分解为不同的第一节点。第三第三步，通过分析得知。可以设计一个递归算法步，通过分析得知。可以设计一个递归算法来控制各个方块的着色来控制各个方块的着色。算法思想：算法思想： 用分治策略，可以设计出解棋盘覆盖问题的简洁用分治策略，可以设计出解棋盘覆盖问题的简洁算法。算法。 (1)(1)当当k0k0时，将时，将2 2的的k k次幂乘以次幂乘以2 2的的k k次幂棋盘分割次幂棋盘分割

17、为为4 4个个2 2的的k-1k-1次幂乘以次幂乘以2 2的的k-1k-1次幂子棋盘。次幂子棋盘。 (2)(2)特殊方格必位于特殊方格必位于4 4个较小棋盘之一中，其余个较小棋盘之一中，其余3 3个个子棋盘中无特殊方格。子棋盘中无特殊方格。 (3)(3)为了将这为了将这3 3个无特殊方格的子棋盘转化为特殊个无特殊方格的子棋盘转化为特殊棋盘，可以用一个棋盘，可以用一个L L型骨牌覆盖这型骨牌覆盖这3 3个较小棋盘的个较小棋盘的会合处，这会合处，这3 3个子棋盘上被个子棋盘上被L L型骨牌覆盖的方格就型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为成为该棋盘上的特殊方格，从而将原问题转

18、化为4 4个较小规模的棋盘覆盖问题。递归地使用这种分个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为割，直至棋盘简化为1 1* *1 1棋盘。棋盘。 算法算法棋盘覆盖棋盘覆盖void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和和tc是棋盘左上角的下标，是棋盘左上角的下标，dr和和dc是特殊方格的下标，是特殊方格的下标，/ size是棋盘的大小，是棋盘的大小，t已初始化为已初始化为0 if (size = = 1) return; /棋盘只有一个方格且是特殊方格棋盘只有一个方格且是特殊方格 t+; / L型骨牌号

19、型骨牌号 s = size/2; / 划分棋盘划分棋盘 / 覆盖左上角子棋盘覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在左上角子棋盘中特殊方格在左上角子棋盘中 ChessBoard(tr, tc, dr, dc, s); /递归处理子棋盘递归处理子棋盘 else / 用用 t 号号L型骨牌覆盖右下角，再递归处理子棋盘型骨牌覆盖右下角，再递归处理子棋盘 boardtr + s - - 1tc + s - - 1 = t; ChessBoard(tr, tc, tr+s- -1, tc+s- -1, s); trtcdrdcSize / 覆盖右上角

20、子棋盘覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在右上角子棋盘中特殊方格在右上角子棋盘中 ChessBoard(tr, tc+s, dr, dc, s); /递归处理子棋盘递归处理子棋盘 else / 用用 t 号号L型骨牌覆盖左下角，再递归处理子棋盘型骨牌覆盖左下角，再递归处理子棋盘 boardtr + s - 1tc + s = t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在

21、右下角子棋盘中特殊方格在右下角子棋盘中 ChessBoard(tr+s, tc+s, dr, dc, s); /递归处理子棋盘递归处理子棋盘 else / 用用 t 号号L型骨牌覆盖左上角，再递归处理子棋盘型骨牌覆盖左上角，再递归处理子棋盘 boardtr + stc + s = t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); #include #include #define N 16#define N 16int a100100;int a100100;int t=1;int t=1;void Tromino(int (void Tromino(int

22、(* *a)N,int dr,int dc,int tr,int tc,int size)a)N,int dr,int dc,int tr,int tc,int size) int s; int s; if(size=1) return; if(size=1) return; if(size1) if(size1) s=size/2; s=size/2; if(dr=(tr+s-1)&dc=(tc+s-1) / if(dr=(tr+s-1)&dc=(tc+s-1) /* *特殊方块在左上部分特殊方块在左上部分* */ / atr+s-1tc+s=t; atr+s-1tc+s=t

23、; atr+stc+s=t; atr+stc+s=t; atr+stc+s-1=t; atr+stc+s-1=t; t+; t+; Tromino(a,dr,dc,tr,tc,s); Tromino(a,dr,dc,tr,tc,s); Tromino(a,tr+s-1,tc+s,tr,tc+s,s); Tromino(a,tr+s-1,tc+s,tr,tc+s,s); Tromino(a,tr+s,tc+s,tr+s,tc+s,s); Tromino(a,tr+s,tc+s,tr+s,tc+s,s); Tromino(a,tr+s,tc+s-1,tr+s,tc,s); Tromino(a,tr

24、+s,tc+s-1,tr+s,tc,s); if(dr(tc+s-1)if(dr(tc+s-1)/ /* *特殊方块在右上部分特殊方块在右上部分* */ / atr+s-1tc+s-1=t; atr+s-1tc+s-1=t; atr+stc+s-1=t; atr+stc+s-1=t; atr+stc+s=t; atr+stc+s=t; t+; t+; Tromino(a,dr,dc,tr,tc+s,s); Tromino(a,dr,dc,tr,tc+s,s); Tromino(a,tr+s-1,tc+s-1,tr,tc,s); Tromino(a,tr+s-1,tc+s-1,tr,tc,s); Tromino(a,tr+s,tc+s-1,tr+s,tc,s); Tromino(a,tr+s,tc+s-1,tr+s,tc,s); Tromino(a,tr+s,tc+s,tr+s,tc+s,s); Tromino(a,tr+s,tc+s,tr+s,tc+s,s); if(dr(tr+s-1)&dc(tr+s-1)&dc(tr+s-1)&dc