棋盤覆蓋問題

1、Tromino謎題分治法分治法 分分治法的基本思想治法的基本思想 對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決(比如說規(guī)模n較小)，則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題， 然后將各子問題的解合并，得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法(divide and conquer)。 分治法的三個(gè)步驟 分治法在每一層遞歸上由三個(gè)步驟組成： (1) 劃分(divide)：將原問題分解為若干規(guī)模較小、 相互獨(dú)立、 與原問題形式相同的子問題。 (2) 解決(conquer)： 若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。 (3

2、) 合并(combine)： 將各子問題的解合并為原問題的解。 它的一般算法設(shè)計(jì)范型如下： 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 從分治法的一般設(shè)計(jì)模式可以看出， 直接用它設(shè)計(jì)出的算法是一個(gè)遞歸算法。我們可用遞歸方程描述遞歸算法的運(yùn)行時(shí)間。 設(shè)T(n)表

3、示用分治法求解規(guī)模為n的問題所需的計(jì)算時(shí)間，如果問題規(guī)模足夠小，比如nc，則可直接求解問題，T(n)=(1)。 假定將原問題分為k個(gè)子問題，每一個(gè)子問題規(guī)模是原問題的1/m， 若分解該問題和合并該問題的時(shí)間分別為D(n)和C(n)，則算法的計(jì)算時(shí)間T(n)可表示為如下的遞歸方程： )()()/() 1 ()(nCnDmnkTnTnc nc 如果n為m的冪，分解該問題和合并該問題的時(shí)間為f(n)，則該遞歸方程的解為 1log0log)/()(niiikmmmnfknnT子問題2的解子問題2的解原始問題的解原始問題的規(guī)模是n子問題1的規(guī)模是n/2子問題2的規(guī)模是n/2 圖解在一個(gè)2k2k （k0）

4、個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為特殊方格。棋盤覆蓋問題要求用如圖（b）所示的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且骨牌之間不得有重疊。(a) k=2時(shí)的一種棋盤時(shí)的一種棋盤 (b) 4種不同形狀的種不同形狀的L型骨牌型骨牌棋盤覆蓋問題棋盤覆蓋問題 殘缺棋盤是一個(gè)有殘缺棋盤是一個(gè)有2 2k k2 2k k （k1k1）個(gè)方格的棋盤，其中恰有）個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。圖一個(gè)方格殘缺。圖4-74-7給出給出k=1k=1時(shí)各種可能的殘缺棋盤，其時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。中殘缺的方格用陰影表示。 號(hào) 號(hào) 號(hào) 號(hào)這樣的棋盤我們稱作這樣

5、的棋盤我們稱作“三格板三格板”，殘缺棋盤問題就是要用這，殘缺棋盤問題就是要用這四種三格板覆蓋更大的殘缺棋盤。在此覆蓋中要求：四種三格板覆蓋更大的殘缺棋盤。在此覆蓋中要求：1 1）兩個(gè)三格板不能重疊）兩個(gè)三格板不能重疊2 2）三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格）三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格在這種限制條件下，所需要的三格板總數(shù)為在這種限制條件下，所需要的三格板總數(shù)為(2(2k k2 2k k -1 )/3 -1 )/3。 棋盤覆蓋問題棋盤覆蓋問題 1 1）問題分解過程如下：）問題分解過程如下：以以k=2k=2時(shí)的問題為例，用二分法進(jìn)行分解，得到的是如下圖，時(shí)的問題

6、為例，用二分法進(jìn)行分解，得到的是如下圖，用雙線劃分的四個(gè)用雙線劃分的四個(gè)k=1k=1的棋盤。但要注意這四個(gè)棋盤，并不的棋盤。但要注意這四個(gè)棋盤，并不都是與原問題相似且獨(dú)立的子問題。因?yàn)楫?dāng)如中的殘缺方都是與原問題相似且獨(dú)立的子問題。因?yàn)楫?dāng)如中的殘缺方格在左上部時(shí)，第格在左上部時(shí)，第1 1個(gè)子問題與原問題相似，而右上角、左個(gè)子問題與原問題相似，而右上角、左下角和右下角三個(gè)子棋盤（也就是圖中標(biāo)識(shí)為下角和右下角三個(gè)子棋盤（也就是圖中標(biāo)識(shí)為2 2、3 3、4 4號(hào)子號(hào)子棋盤），并不是原問題的相似子問題，自然也就不能獨(dú)立棋盤），并不是原問題的相似子問題，自然也就不能獨(dú)立求解了。當(dāng)使用一個(gè)號(hào)三格板（圖中陰影

7、）覆蓋求解了。當(dāng)使用一個(gè)號(hào)三格板（圖中陰影）覆蓋2 2、3 3、4 4號(hào)三個(gè)子棋盤的各一個(gè)方格后，如號(hào)三個(gè)子棋盤的各一個(gè)方格后，如4-84-8右圖所示，我們把覆右圖所示，我們把覆蓋后的方格，也看作是殘缺方格（稱為蓋后的方格，也看作是殘缺方格（稱為“偽偽”殘缺方格），殘缺方格），這時(shí)的這時(shí)的2 2、3 3、4 4號(hào)子問題就是獨(dú)立且與原問題相似的子問題號(hào)子問題就是獨(dú)立且與原問題相似的子問題了。了。 從以上例子還可以發(fā)現(xiàn)，當(dāng)殘缺方格在第從以上例子還可以發(fā)現(xiàn)，當(dāng)殘缺方格在第1 1個(gè)子棋盤，用個(gè)子棋盤，用號(hào)三格板覆蓋其余三個(gè)子棋盤的交界方格，可以使另外三號(hào)三格板覆蓋其余三個(gè)子棋盤的交界方格，可以使另外三

8、個(gè)子棋盤轉(zhuǎn)化為獨(dú)立子問題；同樣地（如下圖所示），當(dāng)個(gè)子棋盤轉(zhuǎn)化為獨(dú)立子問題；同樣地（如下圖所示），當(dāng)殘缺方格在第殘缺方格在第2 2個(gè)子棋盤時(shí)，則首先用號(hào)三格板進(jìn)行棋盤個(gè)子棋盤時(shí)，則首先用號(hào)三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第覆蓋，當(dāng)殘缺方格在第3 3個(gè)子棋盤時(shí)，則首先用號(hào)三格板個(gè)子棋盤時(shí)，則首先用號(hào)三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第4 4個(gè)子棋盤時(shí)，則首先用個(gè)子棋盤時(shí)，則首先用號(hào)三格板進(jìn)行棋盤覆蓋，這樣就使另外三個(gè)子棋盤轉(zhuǎn)化為號(hào)三格板進(jìn)行棋盤覆蓋，這樣就使另外三個(gè)子棋盤轉(zhuǎn)化為獨(dú)立子問題。獨(dú)立子問題。如下圖：如下圖：同樣地同樣地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) 構(gòu)造相同子問題構(gòu)造相同子問題 技巧在于技巧在于劃分棋盤劃分棋盤，使每個(gè)子棋盤均包含一，使每個(gè)子棋盤均包含一個(gè)特殊方格，從而將原問題分解為規(guī)模較小的個(gè)特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題棋盤覆蓋問題k2k2時(shí)時(shí)，可將，可將2k2k2k2k的棋盤劃分為的棋盤劃分為4 4個(gè)個(gè)22（k-1k-1）22（k-1k-1）的子棋盤）的子棋盤，這樣，這樣劃分后，由于原棋盤只劃分后，由于原棋盤只有

10、一個(gè)特殊方格，所以，這有一個(gè)特殊方格，所以，這4 4個(gè)子棋盤中只有一個(gè)子個(gè)子棋盤中只有一個(gè)子棋盤包含該特殊方格，其余棋盤包含該特殊方格，其余3 3個(gè)子棋盤中沒有特殊方個(gè)子棋盤中沒有特殊方格。為了將這格。為了將這3 3個(gè)沒有特殊方格的子棋盤轉(zhuǎn)化為特殊個(gè)沒有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采用遞歸方法求解，可以用一個(gè)棋盤，以便采用遞歸方法求解，可以用一個(gè)L L型骨牌型骨牌覆蓋這覆蓋這3 3個(gè)較小棋盤的會(huì)合處個(gè)較小棋盤的會(huì)合處，從而，從而將原問題轉(zhuǎn)化為將原問題轉(zhuǎn)化為4 4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為略，直至將棋盤

11、分割為1 11 1的子棋盤。的子棋盤。分治策略2 2）棋盤的識(shí)別）棋盤的識(shí)別 棋盤的規(guī)模是一個(gè)必要的信息，棋盤的規(guī)模是一個(gè)必要的信息，有了這個(gè)信息，只要知道其左有了這個(gè)信息，只要知道其左上角的左上角方格所在行、列上角的左上角方格所在行、列就可以唯一確定一個(gè)棋盤了，就可以唯一確定一個(gè)棋盤了，殘缺方格或殘缺方格或“偽偽”殘缺方格直殘缺方格直接用行、列號(hào)記錄。接用行、列號(hào)記錄。 trtr 棋盤中左上角方格所在行。棋盤中左上角方格所在行。 tctc 棋盤中左上角方格所在列。棋盤中左上角方格所在列。 drdr 殘缺方塊所在行。殘缺方塊所在行。 dl dl 殘缺方塊所在列。殘缺方塊所在列。 size si

12、ze 棋盤的行數(shù)或列數(shù)。棋盤的行數(shù)或列數(shù)。dcdrtrtcsize棋盤覆蓋問題中的數(shù)據(jù)結(jié)構(gòu)棋盤覆蓋問題中的數(shù)據(jù)結(jié)構(gòu)下面介紹棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：下面介紹棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：（1 1）棋盤：用二維數(shù)組）棋盤：用二維數(shù)組boardsizesizeboardsizesize表示一表示一個(gè)棋盤，其中，個(gè)棋盤，其中，size=2size=2k k。為了在遞歸處理的過程。為了在遞歸處理的過程中使用同一個(gè)棋盤，將數(shù)組中使用同一個(gè)棋盤，將數(shù)組boardboard設(shè)為全局變量；設(shè)為全局變量；（2 2）子棋盤：在棋盤數(shù)組）子棋盤：在棋盤數(shù)組boardsizesizeboardsizesize中，

13、中，由子棋盤左上角的下標(biāo)由子棋盤左上角的下標(biāo)trtr、tctc和棋盤邊長和棋盤邊長s s表示；表示；（3 3）特殊方格：用）特殊方格：用boardboarddrdrdcdc表示，表示，drdr和和dcdc是是該特殊方格在棋盤數(shù)組該特殊方格在棋盤數(shù)組boardboard中的下標(biāo)中的下標(biāo); ;（4 4） L L型骨牌：一個(gè)型骨牌：一個(gè)2 2k k2 2k k的棋盤中有一個(gè)特殊方的棋盤中有一個(gè)特殊方格，所以，用到格，所以，用到L L型骨牌的個(gè)數(shù)為型骨牌的個(gè)數(shù)為(4(4k k- -1)/31)/3，將所，將所有有L L型骨牌從型骨牌從1 1開始連續(xù)編號(hào)，用一個(gè)全局變量開始連續(xù)編號(hào)，用一個(gè)全局變量t t

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

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

16、各個(gè)子問題上都一個(gè)變量，于是利用了當(dāng)問題上都一個(gè)變量，于是利用了當(dāng)前方格的第一個(gè)點(diǎn)，即第一行第一前方格的第一個(gè)點(diǎn)，即第一行第一列的方塊。這樣，當(dāng)算法繼續(xù)執(zhí)行列的方塊。這樣，當(dāng)算法繼續(xù)執(zhí)行的時(shí)候會(huì)分解為不同的第一節(jié)點(diǎn)。的時(shí)候會(huì)分解為不同的第一節(jié)點(diǎn)。第三第三步，通過分析得知。可以設(shè)計(jì)一個(gè)遞歸算法步，通過分析得知?？梢栽O(shè)計(jì)一個(gè)遞歸算法來控制各個(gè)方塊的著色來控制各個(gè)方塊的著色。算法思想：算法思想： 用分治策略，可以設(shè)計(jì)出解棋盤覆蓋問題的簡潔用分治策略，可以設(shè)計(jì)出解棋盤覆蓋問題的簡潔算法。算法。 (1)(1)當(dāng)當(dāng)k0k0時(shí)，將時(shí)，將2 2的的k k次冪乘以次冪乘以2 2的的k k次冪棋盤分割次冪棋盤分割

17、為為4 4個(gè)個(gè)2 2的的k-1k-1次冪乘以次冪乘以2 2的的k-1k-1次冪子棋盤。次冪子棋盤。 (2)(2)特殊方格必位于特殊方格必位于4 4個(gè)較小棋盤之一中，其余個(gè)較小棋盤之一中，其余3 3個(gè)個(gè)子棋盤中無特殊方格。子棋盤中無特殊方格。 (3)(3)為了將這為了將這3 3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)棋盤，可以用一個(gè)L L型骨牌覆蓋這型骨牌覆蓋這3 3個(gè)較小棋盤的個(gè)較小棋盤的會(huì)合處，這會(huì)合處，這3 3個(gè)子棋盤上被個(gè)子棋盤上被L L型骨牌覆蓋的方格就型骨牌覆蓋的方格就成為該棋盤上的特殊方格，從而將原問題轉(zhuǎn)化為成為該棋盤上的特殊方格，從而將原問題轉(zhuǎn)

18、化為4 4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為割，直至棋盤簡化為1 1* *1 1棋盤。棋盤。 算法算法棋盤覆蓋棋盤覆蓋void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和和tc是棋盤左上角的下標(biāo)，是棋盤左上角的下標(biāo)，dr和和dc是特殊方格的下標(biāo)，是特殊方格的下標(biāo)，/ size是棋盤的大小，是棋盤的大小，t已初始化為已初始化為0 if (size = = 1) return; /棋盤只有一個(gè)方格且是特殊方格棋盤只有一個(gè)方格且是特殊方格 t+; / L型骨牌號(hào)

19、型骨牌號(hào) s = size/2; / 劃分棋盤劃分棋盤 / 覆蓋左上角子棋盤覆蓋左上角子棋盤 if (dr tr + s & dc tc + s) / 特殊方格在左上角子棋盤中特殊方格在左上角子棋盤中 ChessBoard(tr, tc, dr, dc, s); /遞歸處理子棋盤遞歸處理子棋盤 else / 用用 t 號(hào)號(hào)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 號(hào)號(hào)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 號(hào)號(hào)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