棋盤覆蓋問題

1、Tromino謎題分治法分治法 分分治法的基本思想治法的基本思想 對于一個規(guī)模為n的問題，若該問題可以容易地解決(比如說規(guī)模n較小)，則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題， 然后將各子問題的解合并，得到原問題的解。這種算法設計策略叫做分治法(divide and conquer)。 分治法的三個步驟 分治法在每一層遞歸上由三個步驟組成： (1) 劃分(divide)：將原問題分解為若干規(guī)模較小、 相互獨立、 與原問題形式相同的子問題。 (2) 解決(conquer)： 若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。 (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、示用分治法求解規(guī)模為n的問題所需的計算時間，如果問題規(guī)模足夠小，比如nc，則可直接求解問題，T(n)=(1)。 假定將原問題分為k個子問題，每一個子問題規(guī)模是原問題的1/m， 若分解該問題和合并該問題的時間分別為D(n)和C(n)，則算法的計算時間T(n)可表示為如下的遞歸方程： )()()/() 1 ()(nCnDmnkTnTnc nc 如果n為m的冪，分解該問題和合并該問題的時間為f(n)，則該遞歸方程的解為 1log0log)/()(niiikmmmnfknnT子問題2的解子問題2的解原始問題的解原始問題的規(guī)模是n子問題1的規(guī)模是n/2子問題2的規(guī)模是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號子問題就是獨立且與原問題相似的子問題號子問題就是獨立且與原問題相似的子問題了。了。 從以上例子還可以發(fā)現，當殘缺方格在第從以上例子還可以發(fā)現，當殘缺方格在第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) 構造相同子問題構造相同子問題 技巧在于技巧在于劃分棋盤劃分棋盤，使每個子棋盤均包含一，使每個子棋盤均包含一個特殊方格，從而將原問題分解為規(guī)模較小的個特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題棋盤覆蓋問題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個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為略，直至將棋盤

11、分割為1 11 1的子棋盤。的子棋盤。分治策略2 2）棋盤的識別）棋盤的識別 棋盤的規(guī)模是一個必要的信息，棋盤的規(guī)模是一個必要的信息，有了這個信息，只要知道其左有了這個信息，只要知道其左上角的左上角方格所在行、列上角的左上角方格所在行、列就可以唯一確定一個棋盤了，就可以唯一確定一個棋盤了，殘缺方格或殘缺方格或“偽偽”殘缺方格直殘缺方格直接用行、列號記錄。接用行、列號記錄。 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開始連續(xù)編號，用一個全局變量開始連續(xù)編號，用一個全局變量t t

14、表表示示算法分析算法分析 假設有如下8*8的棋盤，其中著紅色塊為少了的方塊：第一步先討論問題的最小單位，即第一步先討論問題的最小單位，即問題的原型。此時只有四個方格的問題的原型。此時只有四個方格的棋盤，假設其中任意一塊是缺失的，棋盤，假設其中任意一塊是缺失的，則只需要直接填充其余三塊即則只需要直接填充其余三塊即可可第二第二步，問題擴大，歸納其中的規(guī)步，問題擴大，歸納其中的規(guī)律。變成律。變成4 4* *4 4個的棋盤方格個的棋盤方格此時可以看到如果以方格中心交叉此時可以看到如果以方格中心交叉線分別為線分別為X X軸，軸，Y Y軸。則到了第二步，軸。則到了第二步，每個象限都會有一個方格著色了。每個

15、象限都會有一個方格著色了。并且，如果初始缺失的方格在其中并且，如果初始缺失的方格在其中任意一個象限，則其余象限分布的任意一個象限，則其余象限分布的著色方塊必須在與原點最近的方塊。著色方塊必須在與原點最近的方塊。這一步可以總結出一個關鍵點，著這一步可以總結出一個關鍵點，著色方塊所在的象限。色方塊所在的象限。為了得到著色塊所在象限，我們必為了得到著色塊所在象限，我們必須知道當前方格個數以及原點。但須知道當前方格個數以及原點。但是整個問題分析過程中只有一個原是整個問題分析過程中只有一個原點，如果想設計一個高效的算法讓點，如果想設計一個高效的算法讓其自動分解執(zhí)行的話必須在各個子其自動分解執(zhí)行的話必須在

16、各個子問題上都一個變量，于是利用了當問題上都一個變量，于是利用了當前方格的第一個點，即第一行第一前方格的第一個點，即第一行第一列的方塊。這樣，當算法繼續(xù)執(zhí)行列的方塊。這樣，當算法繼續(xù)執(zhí)行的時候會分解為不同的第一節(jié)點。的時候會分解為不同的第一節(jié)點。第三第三步，通過分析得知?？梢栽O計一個遞歸算法步，通過分析得知。可以設計一個遞歸算法來控制各個方塊的著色來控制各個方塊的著色。算法思想：算法思想： 用分治策略，可以設計出解棋盤覆蓋問題的簡潔用分治策略，可以設計出解棋盤覆蓋問題的簡潔算法。算法。 (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個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為割，直至棋盤簡化為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