平面图形之所有组合解之搜寻

1、平面圖形之所有組合解之搜尋研究者：李佳盈陳玉潔指導老師：董致平老師壹、緒論 一、研究動機         在一次偶然的機會下，學會玩一種組合平面三角形的遊戲（如下圖）。在解題的過程中，我們常常體會到任何的組合方式，都可以透過邏輯推理得到答案。因此我們希望能夠透過分析、邏輯思考的方式，分解出這個三角形的結構以及組合方式的可行性，然後設計出一個電腦程式，能夠讓電腦自行進行分析的動作以求答案。此平面三角形，為一個兩腰圍10單位長的等腰直角三角形。此等腰三角形又再分成55個小單位，由12個不同形狀的小塊

2、積木組合而成。簡圖如下：圖一：平面三角形的排列組合之一一種顏色代表一個小塊積木，共有12種不同的形狀。每個大平面三角形都由這12個小塊積木組合而成。遊戲的玩法是：給予既定、排列好的數個小塊積木，然後再由使用者用剩下有限的積木，完成這一個大平面三角形。舉例如下：圖二：遊戲情形之一除了命題已經用掉的4塊積木外，使用者還有8塊積木，必須用剩下的8塊積木組合成這個大平面三角形。詳細內容說明：圖三：既有的12塊小積木形狀如下：ABCDEFGHIJKL圖四：棋盤形狀：二、研究目的（一）分析出十二塊小積木的組合特性、探討遊戲中平面三角形的組合結構。（二）利用目的（一）的結果，撰寫一程式。能夠在有限的小積木裡

3、，配合使用者給予的參數，經過分析，求出可能的排列組合。（三）希望在分析的過程中，能夠增強邏輯思考的能力、以及平面圖形思考的實力。（四）能夠透過這些研究過程，對程式語言及其結構有更深層了解。（五）對研究的題目能夠有透徹的了解，然後有新的發現，進而推廣原有的平面三角形到任意圖形，例如：平面多邊形、立體四角錐、正多邊體等等。貳、研究設計對於我們的程式，以下為程式架構的說明，詳細的程式碼將會附在附錄中。 一、輸入使用說明 螢幕上將看到下列幾個問題：（一）please enter the width and the length of the table:請依次輸入棋盤的直行與橫列的長度，兩數字中間用空

4、白或enter區隔（二）please enter the number of the pieces:請輸入有幾塊積木 以下輸入會持續接受輸入到所有積木資料都已拿到（三）Input the width and the length of piece number X:請輸入第X塊積木的直行與橫列長度（四）Please input the shapes of pieces:請輸入此塊積木的形狀 關於所謂的形狀輸入，說明如下：我們以1表示圓圈，也就是積木實際有佔空間處；0則相反。從左上角開始橫向依序讀取，上圖這樣一塊積木即以 1 1 0 0 1 0 0 1 1 0 1 0代表其形狀，兩數字之間用空白

5、或enter區隔。二、棋盤的模擬利用class將棋盤作成一個類別table，對於棋盤的各種操作則透過呼叫成員函數來執行。（一）建構子table ( int width, int length )1. 利用動態記憶體配置開出一個存放整數的二維陣列，其長寬分別是width+2和length+2。2. 首行首列及末行末列的值設為-1，其餘的值設為0。唯有0值代表此格為空的。（二）成員函數1. bool table : put( int dx, int dy, int p_width, int p_length, int *direct, int which_piece )當使用者呼叫此函數，可將指定

6、的某塊積木左上角對準給定的座標放到棋盤上。放置成功，則回傳真值；如無法放入，則回傳假值。(1) dx和dy為x，y座標p_width和p_length為piece的長與寬direct是其內容which_piece則是piece的編號(2) 先檢查在( dx,dy )處放入長p_width、寬p_length的piece會不會超出棋盤範圍(3) 讀取direct陣列，依序檢查如果放入棋盤，是否direct裡每一個為1的值，在棋盤上要放入處的值皆為0(4) 放入棋盤時，從( dx,dy )開始橫向放入p_length個之後，換行到(dx+1,dy)再放入p_length個，後再換行到(dx+2,d

7、y)直到放完所有direct裡的值，這樣piece的內容才能由一維陣列的形式還原至二維陣列。(5) 如在(3)的檢查中有任一不符合的情形，則代表棋盤上已有積木，使得積木無法再放入，然後回傳假值。(6) 如在(3)的檢查中全部都可以順利放入，才將piece真正放到棋盤上。對於每一個direct對應值為1的棋盤位置，將棋盤的0值給改為which_piece+1，因為which_piece的值為0 積木的總塊數-1，而我們不能再填入02. void table : clear( int dx, int dy, int p_width, int p_length, int *direct )此函數是給

8、使用者清除掉放在棋盤上的某一塊積木。(1) 變數的命名方式同前(2) 清除掉積木的過程就是放入過程的逆操作。三、積木的模擬利用class將積木作成一個類別Piece，對於積木的各種操作則透過呼叫成員函數來執行。（一） 建構子（二） 成員函數1. void Piece : assign (int w, int l, int *data)將在主程式中輸入的Piece資料暫存到floppy這個一維陣列，將floppy的指標及積木的長寬傳給此函數，它會將floppy的值拷貝下來並還原成一個二維陣列。(1) w和l為積木的長與寬data則是floppy的指標 (2) 動態記憶體配置開出一個存放整數的二維

9、陣列database，其長寬分別是w和l(3) 依序將floppy裡的值複製到database裡，每橫列填完則到下一列繼續(4) 呼叫left1_right2( ) left2_right1( )upper1_down2( )upper2_down1( )四個函數2. void left1_right2( )void left2_right1( )void upper1_down2( )void upper2_down1( ) 透過這些能依一塊積木正反方向及旋轉角度不同的八種放置方式，從左上角依序讀成八個一維陣列。如下圖，如令有圈的為1，其他的是0。則從八個不同方向依序讀取可得到下列的數據：d

10、owntwo upperoneuppertwoleftone lefttwo rightone downone rigthtwo leftone：1 1 0 0 1 0 0 1 1 0 1 0 lefttwo：0 1 0 0 1 1 0 1 0 1 1 0rightone：0 1 1 0 1 0 1 1 0 0 1 0righttwo：0 1 0 1 1 0 0 1 0 0 1 1upperone：1 0 0 0 1 1 1 1 0 0 1 0 uppertwo：0 0 1 0 1 1 1 1 1 0 0 0 downone：0 0 0 1 1 1 1 1 0 0 1 0 downtwo：0

11、1 0 0 1 1 1 1 0 0 0 1 若將其中每一組數碼的1以圈表示，配合長寬的互換，從左上角依序填入，則就達到把積木換方向的目的。 leftone：1 1 0 0 1 0 0 1 1 0 1 0 lefttwo：0 1 0 0 1 1 0 1 0 1 1 0 rightone：0 1 1 0 1 0 1 1 0 0 1 0 righttwo：0 1 0 1 1 0 0 1 0 0 1 1 upperone：1 0 0 0 1 1 1 1 0 0 1 0 uppertwo：0 0 1 0 1 1 1 1 1 0 0 0 downone：0 0 0 1 1 1 1 1 0 0 1 0 do

12、wntwo：0 1 0 0 1 1 1 1 0 0 0 1 (1) 動態記憶體配置出元素個數為width*length的一維陣列(2) 各個函數從database分別依leftone, lefttwo, rigthone, rigthtwo, upperone, uppertwo, downone, downtwo八種方向讀到陣列中存入3. void Piece : check( )int Piece : eqaul(int a, int b) 由於有些積木的形狀有對稱性，所以八個方向轉置出來的擺置方式會有所重複，這兩個函數可以幫忙找出這些重複的擺置方式，有重複的部分則不用予以嚐試。 1.左右

13、對稱 如果leftone和rightone兩個陣列的內容是一樣的，則表示此圖形是左右對稱的，此時令整數left_right為1。此時，upperone = uppertwo donwone = donwtwo lefttwo = righttwo 2.上下對稱 如果leftone和lefttwo兩個陣列的內容是一樣的，則表示此圖形是上下對稱的，此時令整數upper_down為1。 此時，upperone = downone uppertwo = downtwo rightone = righttwo 3.旋轉對稱 如果leftone和righttwo兩個陣列的內容是一樣的，則表示此圖形是旋轉對

14、稱的，此時令整數reverse為1。此時，lefttwo = rightone upperone = downtwo uppertwo = downone以下是方陣的： 4.左上右下對角線對稱 如果leftone和upperone兩個陣列的內容是一樣的，則表示此圖形是左上右下對角線對稱的，此時令整數left_upper為1。leftone:111100100upperone:111100100此時，lefttwo = uppertwo rightone = downone righttwo = dwontwo 5.右上左下對角線對稱 如果leftone和downtwo兩個陣列的內容是一樣的，則

15、表示此圖形是左上右下對角線對稱的，此時令整數right_upper為1。leftone:100100111downtwo:100100111此時，upperone = righttwo uppertwo = rightone lefttwo = downone另外的情況： 1.如果同時左右、旋轉對稱，此時上下對稱亦成立。在這種情況下只有leftone和upperone是不同的擺置方式。 2. 如果同時左上右下對角線、右上左下對角線對稱，此時左右、上下對稱亦成立。在這種情況下只有leftone這一種擺置方式。 (1) int Piece : equal(int a, int b)可檢查傳入的兩個

16、陣列是否相同。void Piece : check( )此一函數中依不同可能的對稱條件，使用不同的參數呼叫equal(int a, int b)，並讓equal回傳的值存入left_right, upper_down, reverse, left_upper, right_upper五個整數中。4. bool get_leftone( )bool get_lefttwo( )bool get_rightone( )bool get_righttwo( )bool get_upperone( )bool get_uppertwo( )bool get_downone( )bool get_dow

17、ntwo( )這八個函數可以在拿取其對應的積木前，透過裡面的判斷式知道此塊積木擺置的形狀是否跟之前的有所重複，若有則回傳假值。對於這些判斷式的說明，延續(4)裡的分析，有重複的部分刪去等號後者，列成下表可知哪些狀況成立時需回傳假值： 方向判斷條件leftonelefttworightonerighttwoupperoneuppertwodownonedowntwoleft_right ××××upper_down ××××reverse××××left_upper ×

18、;×××right_upper××××left_right && reverse××××××left_upper && right_upper×××××××根據上面的歸納，便可寫出這八個布林函數內所需的判斷式。四、主程式（一）流程簡圖輸入table的長寬並宣告board這個table物件輸入有幾塊積木，令為n。宣告長度為n的piece一維陣列pi輸入每塊的長寬、內容

19、，依照piece的次序依序將這些值存入一維陣列pi中判斷積木的總體積是否剛好可填滿棋盤函數able_putif( put piece )呼叫函數over_next_pieceelse 呼叫函數direct_over 呼叫函數next_row_end函數 next_row_end 1.根據對稱性減少第一 塊積木所需試的位置 2.所有的位置都被試過 呼叫函數back 呼叫函數 next_row_end函數over_next_pieceif( 最後一塊 ) 1.印出此組解答 2.呼叫函數clear_direct 3.呼叫函數back 4.呼叫函數 next_row_endelse換下一塊繼續試函數b

20、ack1.清掉最後一塊2.改試倒數第二塊下一方向3.呼叫函數direct_over函數direct_over if( 現在試的這塊的八種方向都已試完 ) 呼叫函數move_to_nextif( 第一塊所有需放的位置都已試過)break;for( ; ; )結束(二) 程式細部說明1. void able_put(stack &store_x, stack &store_y, stack &store_direct, table &board, int eight_direct, int &dx, int &dy, Piece *pi, int &

21、amp;which_piece, int &solution,int n)這個函數可以分類當現在這塊積木可以放入棋盤時接下來的動作，以及無法放入時的後續做法。(1) store_x , store_y及store_direct分別為儲存x,y座標及積木方向的stack甲、board為棋盤，資料型態為table乙、eight_direct用來紀錄積木已經試到哪個方向。leftone, lefttwo, rightone, righttwo, upperone, uppertwod, downone, downtwo八個方向分別對應0, 1, 2, 3, 4, 5, 6, 7。陣列長度和積

22、木塊數同，eight_direct0的方向值對應第0塊積木，以下類推丙、dx, dy分別為x,y座標丁、pi為積木的陣列，pi0為第0塊積木，以下類推戊、which_piece用來紀錄現在試到第幾塊，值為0積木總塊數-1己、solution紀錄有幾個解庚、n積木總塊數(2) 呼叫put_piece此一布林函數，回傳值有兩個意義甲、積木本身有沒有與其他重複，若有則不用試，回傳值為假乙、積木可不可以放入棋盤上(3) put_piece的回傳值若為真甲、分別紀錄(dx, dy)及eight_direct到store_x , store_y和store_direct乙、呼叫函數over_next_pi

23、ece，檢查現在這塊放下去之後，是否已經放完全部的積木。(4) put_piece的回傳值若為假甲、則試同一塊積木的下一個方向，即eight_directwhich_piece+乙、呼叫函數direct_over，判斷方向增加後有沒有超過72. bool put_piece(table &board, int &dx, int &dy, Piece *pi, int which_piece, int direct) 利用這個函數，對於可以放入棋盤上的積木於放入後，回傳真值；而對於不能放入的，回傳假值。在下面的說明中，我們以direct為1時舉例，而實際上的程式我們以sw

24、itch將每種情況分開處理。(1)變數的命名方式同前(2)如果piwhich_piece.get_lefttwo()=0代表這塊積木在lefttwo這個方向的圖形和之前的重複，不用試，直接回傳假值(3)如果piwhich_piece.get_lefttwo()0此塊積木在這個方向需要試，直接回傳函數board.put。如果能放入棋盤上回傳值為真；反之則為假。3. void direct_over(int eight_direct,int &dx, int &dy, table &board, Piece *pi,int which_piece)若eight_direct

25、which_piece8，則表示此塊積木在這個位置的所有旋轉方向都已經試過，換下一個位置，從第0個方向重新開始試(1) 變數的命名方式同前(2) 若eight_directwhich_piece81、 ight_directwhich_piece=02、 呼叫move_to_next函數，換下一個位置 4. void move_to_next(int &dx, int &dy, table &board, Piece *pi,int which_piece) 將(dx,dy)換到下一個要試的座標。(1) 變數的命名方式同前(2) 令整數table_length=boar

26、d.get_table_length()-代表積木的短邊(3) dx=dx+(dy+1)/table_length甲、dy=(dy+1)/table_length+(dy+1)%table_length乙、當(dx,dy)已超過棋盤範圍的時候便換到(dx+1,1) 5. void over_next_piece(stack &store_x, stack &store_y, stack &store_direct, table &board, int eight_direct, int &dx, int &dy, Piece *pi, int &

27、amp;which_piece, int &solution,int n)當所有積木都已經放入棋盤上，也就是已找到一個解時，此函數會將其輸出至檔案，並呼叫其他的函數將其此時已展到葉的樹狀結構回溯，繼續展開；如果仍有積木未放入，則換下一塊積木試。(1) 變數的命名方式同前(2) 如果which_piece = n-1，則此時所有的積木都已放完1、 紀錄幾解的 solution+2、 呼叫board的成員函數print()輸出棋盤面上的數值至檔案，可得其解3、 呼叫clear_direct函數清掉最後放下去的積木4、 呼叫back函數，將倒數第二塊積木換個方向試(3) 如果which_pi

28、ece n-1將which_piece+，也就是改成下一塊積木，並將(dx,dy)改成(1,1)，當下次進入迴圈時，函數able_put從棋盤最左上角開始試新的積木。 6. void clear_direct(stack &store_x, stack &store_y, stack &store_direct, table &board, int &dx, int &dy, Piece *p, int which_piece) 使用此函數可將stack中存的最後一塊積木清掉。 (1) 變數的命名方式同前(2) pop分別存於stack_x, s

29、tack_y, stack_direct的值(3) 呼叫board.clear函數清掉存於棋盤上的值7. void back(stack &store_x, stack &store_y, stack &store_direct, table &board, int &dx, int &dy, Piece *pi, int &which_piece, int eight_direct)此函數會拿起此時存在stack裡的最後一塊，並增加方向數eight_directwhich_piece以試下一個方向。(1) 變數的命名方式同前(2) 在o

30、ver_next_piece函數中已將最後一塊清掉，但未將which_piece的紀錄值更改，在這裡將which_piece-1(3) 呼叫clear_direct函數清掉此時存在stack裡最後的積木(4) eight_directwhich_piece+試此塊積木下一個方向(5) 呼叫函數direct_over，判斷方向增加後有沒有超過78. void next_row_end(stack &store_x, stack &store_y, stack &store_direct, table &board, int eight_direct, int &a

31、mp;dx, int &dy, Piece *pi, int &which_piece) 此函數針對幾個積木可能試到的特殊位置進行分類處理：(1) 對於第一塊積木可根據對稱性減少其所需試的位置，在下圖中以表示。據此提早換行可以加快整個程式進行的速度。 在方形的棋盤上：在矩形的棋盤上： 順帶一提的是，此時我們亦可以察知當第一塊積木在下圖上的這個位置時，即代表所有的可能性都已經試完，可終止程式跳出無窮迴圈，這就是我們在主程式最後一行給的迴圈中止條件。 (2) 如果非第一塊積木 則當它因試過所有位置而仍未能找到可以放的地方，而來到下圖所標示的位置時，表示倒數第二塊積木的放置方式是錯的

32、，必須將倒數第二塊積木換個方向試。 (3) 變數的命名方式同前(4) 如果是第一塊積木甲、方形棋盤若dx > dy即可換行乙、矩形棋盤(5) 若dy 過棋盤橫長的一半即可換行(6) 若不是第一塊積木且dx 棋盤width-1 且 dy 1甲、呼叫back函數，將倒數第二塊積木換方向試乙、呼叫next_row_end函數，因換方向時有可能超過方向數而換至下一個位置，故我們必須再次檢查伍、結論：根據程式執行結果發現，程式執行速度與棋盤大小以及積木塊數有一定的關係，且棋盤越大、積木塊數越多，則所需執行時間越長，這個是較顯而易見的結果。而另外一項結果顯示執行速度與積木形狀也有密切關係，當積木的形

33、狀越對稱，則所需的時間越少，因為重複而可以不要做的情況較多。我們曾經嘗試先排序，讓較大的積木塊先進入棋盤中排列，希望能在樹的較低層就發現不可行的狀況，以減少嘗試次數。但奇妙的是，在某些狀況中，這樣的確比其他積木排列方式快；但在其他狀況中，卻不是最快的。這項結果顯示出，影響程式執行時間長短的因素很多，所以很難找出一個適用於所有棋盤的演算法，因為棋盤的變因太多，只能從經驗上，盡量找出較快的一種演算法，但對於個別情況，卻不一定是最適用的。對於小的棋盤，例如6*6的方形棋盤，我們的程式可以在很快的時間之內，就將所有的答案跑完。但如果進階到10*10、12塊積木、少許對稱情況，程式跑三天也沒跑完，所以可

34、以看出，縮短程式執行時間，是最需要改進的地方。陸、討論：一、 我們曾經根據自己的遊戲經驗發現，對於某些角落而言，當人腦知道角落將產生 死角時，就絕對不會再放積木下去。但是我們原本的程式是最原始的想法，沒有讓電腦檢查是否有無法填入的空格，只是一再的找尋新位置，這樣子可能會增加許多無謂的時間，因為在我們已經發現棋盤絕對無解的情況下，其實就已經可以跳出步驟，節省接下來積木的嘗試時間。也就是在每次放下新的一塊積木時，我們就掃一棋盤，看看是否產生了無解的空白。我們根據這個想法，寫出了一張流程圖，可供未來發展使用。所有的棋子排序函數able_putif(put_piece)呼叫函數 over_next_p

35、ieceelse呼叫函數direct_over函數 over_next_pieceif(最後一塊)1 印出解答2 呼叫函數clear_director3呼叫函數backelse1 呼叫balnk_search.get_data 方 法2 if(blank_search.scan) 呼叫函數max_sqrelse 換下一塊 繼續迴圈函數direct_overif(八個方向試完) if(which_piece=0) break; else 呼叫back函數else 繼續進入迴圈函數back1 清掉最後一塊2 改試倒數第二塊的下一個方向3 呼叫函數direct_over函數(max_sqr)1.找出

36、最大連續空白2呼叫rest_able函數if(rest_able) 呼叫over_next_pieceelse 呼叫函數back_d函數back_d1.試棋盤上最後一塊的下一個方向2.呼叫direct_over結束迴圈流程圖上的的blank_search函數，可執行的工作如下：(一) scan：尋找棋盤上是否產生區域性空白。(二) Get_data：傳回棋子鄰邊的位置值è下一塊棋子的放置位置。二、 另外，對於根據減少時間，我們還想出另一種方法，就是在程式執行前，先行進行解析，看是否有不同的積木可以重組成一樣的圖形。另如積木A、B可以拼成和C、D一樣的形狀，如此一來，每當A、B拼成一塊

37、時，就可以馬上跑出用C、D組成的另一個解。三、 現行的程式棋盤，侷限於矩陣圖形這類，未來應可以設計出一個能讓使用者任意輸入棋盤形狀、大小的類別。四、 平面上的問題解析，是否可以推廣到空間中？在3D立體的空間中，可以試著把空間剖析成數個平面，再引用現在程式寫好的平面解題法解構，相信如此一來就可以把問題簡化許多。五、 現在結果輸出採用的有兩種，一種是在DOS系統下直接觀看程式的執行結果，而另外一個則是將答案輸出，另存一個新檔將所有解答存起。關於這點，可能會有人覺得DOS的黑白介面十分不人性化。我們也曾經想要改進過。在指導老師董致平老師的建議與教導下，我們有機會接觸到BCB這個新的程式語言，可以有機

38、會將我們的執行結果或者是過程，用更人性的視窗介面展現出來。但是因為某些因素，使得這方面的改進無法在預定時間如期完成，對我們來講，也算是一種遺憾，也許在不久的將來，我們還有機會繼續這項工作，可能可以將它完成，讓它更能被大家接受。柒、謝誌：一、感謝董致平老師不辭辛勞地回答我們的問題，以及常常在我們心理上有壓力時，給予適時的鼓勵。二、感謝陳怡芬老師雖然不是我們正式的顧問，但是卻能夠忍受我們三不五時的擾，並切給予中肯的建議，使我們的專研能夠持續進行。三、感謝資訊專研的同學給予我們的腦力激盪，讓我們想出更多的好點子。四、感謝在研究過程中，曾經給予我們無論是實質上或是精神上鼓勵的每一個人，謝謝你們。捌、附

39、註一、完整的程式碼#include <iostream.h>#include <stdlib.h>#include <fstream.h>#include <time.h>class Pieceprivate: int width; int length; int *database; int left_right; int upper_down; int reverse; int left_upper; int right_upper; int how_many_pieces;public: Piece()width=-1; void assi

40、gn(int w,int l,int* data); Piece(); void show(int* ptr); void left1_right2(); void left2_right1(); void upper1_down2(); void upper2_down1(); int get_width()return width; int get_length()return length; int get_piece()return how_many_pieces; void check(); int equal(int a,int b); bool get_leftone(); bo

41、ol get_lefttwo(); bool get_rightone(); bool get_righttwo(); bool get_upperone(); bool get_uppertwo(); bool get_downone(); bool get_downtwo(); int* leftone; int* lefttwo; int* rightone; int* righttwo; int* upperone; int* uppertwo; int* downone; int* downtwo;void Piece:left1_right2() leftone=new int w

42、idth*length; righttwo=new int width*length; int count=0; for(int i=0;i<width;i+) for(int j=0;j<length;j+) leftonecount=*(*(database+i)+j); righttwowidth*length-count-1=*(*(database+i)+j); count+; void Piece:left2_right1() lefttwo=new int width*length; rightone=new int width*length; int count=0

43、; for(int i=width-1;i>=0;i-) for(int j=0;j<length;j+) lefttwocount=*(*(database+i)+j); rightonewidth*length-count-1=*(*(database+i)+j); count+; void Piece:upper1_down2() upperone=new int width*length; downtwo=new int width*length; int count=0; for(int j=0;j<length;j+) for(int i=0;i<width

44、;i+) upperonecount=*(*(database+i)+j); downtwowidth*length-count-1=*(*(database+i)+j); count+; void Piece:upper2_down1() uppertwo=new int width*length; downone=new int width*length; int count=0; for(int j=length-1;j>=0;j-) for(int i=0;i<width;i+) uppertwocount=*(*(database+i)+j); downonewidth*

45、length-count-1=*(*(database+i)+j); count+; void Piece:assign(int w,int l,int* data) width=w; length=l; how_many_pieces=0; database=new int *width; int count=0; for(int i=0;i<width;i+) databasei=new intlength; for(int i=0;i<width;i+) for(int j=0;j<length;j+) *(*(database+i)+j)=datacount; if(

46、datacount=1) how_many_pieces+; count+; left1_right2(); left2_right1(); upper1_down2(); upper2_down1(); check();int Piece:equal(int a,int b) int same=1; for(int i=0;i<width*length;i+) if(ai!=bi) same=0; break; return same;void Piece:check() left_right=equal(leftone,rightone); upper_down=equal(left

47、one,lefttwo); reverse=equal(leftone,righttwo); left_upper=(width=length)&&equal(leftone,upperone); right_upper=(width=length)&&equal(leftone,downtwo);bool Piece:get_leftone() return true;bool Piece:get_lefttwo() return(upper_down|(left_right&&reverse)? false:true;bool Piece:g

48、et_rightone() return(left_right|reverse|right_upper)? false:true;bool Piece:get_righttwo() return(left_right|upper_down|reverse|right_upper)? false:true;bool Piece:get_upperone() return(left_upper&&right_upper|left_upper)? false:true;bool Piece:get_uppertwo() return(left_right|(left_right&&reverse)|left_upper)? false:true;bool Piece:get_downone() return(upper_down|reverse|left_upper|right_upper)? false:true;bool Piece:get_downtwo() return(left_right|upper_down|reverse|left_upper|right_upper)? false:tru