用分治法求解棋盤覆蓋問題

1、.棋盤覆蓋問題問題描述： 在一個2k×2k（k0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。顯然，特殊方格在棋盤中出現(xiàn)的位置有4k中情形，因而有4k中不同的棋盤，圖（a）所示是k=2時16種棋盤中的一個。棋盤覆蓋問題要求用圖（b）所示的4中不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且熱河亮哥L型骨牌不得重復(fù)覆蓋。 圖（b）圖 （a）問題分析：K>0時，可將2k×2k的棋盤劃分為4個2k-1×2k-1的子棋盤。這樣劃分后，由于原棋盤只有一個特殊方格，所以，這4個子棋盤中只有1個子棋盤中有特殊方格，其余3個子棋盤中沒有特

2、殊方格。為了將這3個沒有特殊方格的子棋盤轉(zhuǎn)化成為特殊棋盤，以便采用遞歸方法求解，可以用一個L型骨牌覆蓋這3個較小的棋盤的會合處，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1×1的子棋盤。問題求解：下面介紹棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計。（1） 棋盤：可以用一個二維數(shù)組boardsizesize表示一個棋盤，其中size=2k。為了在遞歸處理的過程中使用同一個棋盤，將數(shù)組board設(shè)為全局變量。（2） 子棋盤：整個棋盤用二維數(shù)組boardsizesize表示，其中的子棋盤由棋盤左上角的下標(biāo)tr、tc和棋盤大小s表示。（3） 特殊方格：用boar

3、ddrdc表示特殊方格，dr和dc是該特殊方格在二維數(shù)組board中的下標(biāo)。（4） L型骨牌：一個2k×2k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數(shù)為（4k-1）/3，將所有L型骨牌從1開始連續(xù)編號，用一個全局變量tile表示。C語言源碼：/*author: 彭洪偉 *studentID:0950310006 *class:計科1班 *problem:分治法解決棋盤覆蓋問題 */#include <stdio.h>#include <math.h>int tile=1; /記錄骨牌的型號int board2020=0; /存儲棋盤被覆蓋的情況void

4、ChessBoard(int tr,int tc,int dr,int dc,int size) /tr和tc是棋盤左上角的下標(biāo),dr和dc是特殊方格的下標(biāo),size是棋盤的大小int t=0;int s;if (size=1)return;t=tile+;s=size/2; /劃分棋盤/覆蓋左上角棋盤if (dr<tr+s&&dc<tc+s) /特殊方格在棋盤的左上角ChessBoard(tr,tc,dr,dc,s);elseboardtr+s-1tc+s-1=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆蓋右上角棋盤if (dr&l

5、t;tr+s&&dc>=tc+s) /特殊方格在棋盤的右上角ChessBoard(tr,tc+s,dr,dc,s);elseboardtr+s-1tc+s=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆蓋左下角棋盤if (dr>=tr+s&&dc<tc+s)/特殊方格在棋盤的左下角ChessBoard(tr+s,tc,dr,dc,s);elseboardtr+stc+s-1=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);/覆蓋右下角棋盤if (dr>=tr+s&&dc

6、>=tc+s) /特殊方格在棋盤的右下角ChessBoard(tr+s,tc+s,dr,dc,s);elseboardtr+stc+s=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);int main()int k,x,y;printf("請輸入棋盤的規(guī)模K：");scanf("%d",&k); printf("請輸入特殊方格的下標(biāo)x,y：");scanf("%d %d",&x,&y);ChessBoard(0,0,x,y,pow(2,k);for(int i=0; i<pow(2,k); i+)for (int