四色方柱問題

1、算法與分析課程設(shè)計報告題 目：四色方柱問題專 業(yè)：軟件工程班 級：學 號：姓 名：太原工業(yè)學院計算機工程系2012年 11 月 23 日一、算法問題描述設(shè)有4個立方體，每個立方體得每一面用紅、黃、藍、綠4種顏色之一染色。 要把這4個立方體疊成一個方形柱體，使得柱體使得 4個側(cè)面的每一側(cè)均有4 種不同的顏色。同時，4個頂面和4個底面也有4種不同的顏色。試設(shè)計一個回 溯算法，計算出4個立方體的一種滿足要求的疊置方案。二、算法問題形式化表示對于給定的四個立方體及每個立方體各面的顏色，給出一種疊置方案，使柱體的四個側(cè)面都有四種不同的顏色。三、期望輸入與輸出期望輸入：第一行輸出1表示頂面，2表示底面3表

2、示左面，4表示右面，5表 示前面，6表示后面。期望輸出：輸出每個立方體每個面的著色方案，即問題的解決方案。四、算法分析與步驟描述事實上，這個四色方柱問題，如果用逆推想會好理解一些，現(xiàn)在設(shè)將這四個 立方體組合成了一個方形柱體，我們可以先選擇一個立方體的符合條件的頂面和 底面，之后我們可以將它的側(cè)面展開這樣會形成一個4*4的矩陣，該4*4矩陣上每行的四個值相當于原小立方體的四個側(cè)面的著色(左、右、前、后對應(yīng)于1、2、3、4)列上的四個值就是表示四個小立方體合成方形柱體后柱體上某個側(cè)面 的著色了，這樣就可以利用類似于 N皇后的回溯算法的思路了， N皇后的要求是 不能相互攻擊而這個題根據(jù)要求就是使每列

3、上的著色值都不同。用4元數(shù)組Xi，j,(i=1、2、3、4, j=1、2、3、4)表示第i個立方體第j個面所圖顏色，由于不允許將兩個顏色放在同一列，所以解向量中的Xi互不相同。將n*n格棋盤看作二維矩陣，其行號從上到下以此表示四個立方體，列號從左到右依次表示左、右、前、后立方體的六個面。從棋盤自上來下同一豎直線 上，因此，兩個顏色放置的位置分別是(i,j )和(k，I),且i!=k、 j=l&X(l,j)!=X(k,I)，此條件下確保四方柱的每個側(cè)面都有四種不同的顏色。由此可知，只要i=k、j=l&X(l,j)!=X(k,I)就說明兩個顏色在同一側(cè)面上。根據(jù)對四色方柱問題算法分析，我們用回朔法

4、求解，遞歸方法backtrack實現(xiàn)對整個解空間的回朔搜索。Backtrack(i)搜索解空間的第 i層樹。類FourColorProblem的數(shù)據(jù)成員記錄解空間中結(jié)點信息，以減少傳給 backtrack 的參數(shù)。Sum記錄當前已找到的可行方案數(shù)，result叩 記錄可行方案。五、問題實例及算法運算步驟給定四個立方體和四種顏色紅綠黃藍，把它們放置成一個長方柱體，要求四個側(cè)面、頂面、底面都有四種不同的顏色。把長方體的側(cè)面展開，看成4*4的矩陣，這就相當于n皇后的問題，只需要 每一列的顏色不同即可。所以兩個顏色放置的位置分別是( i,j )和(k，l), 且i!=k、j=l&X(l,j)!=X(k

5、,l)，就可以確保四方柱的每個側(cè)面都有四種不同的顏色。六、算法運行截圖felue yellow red green blue yellow green red tlue red yellow green bin亡 red green yellow blue green red yellow blue green yellow red green yellow blue red green yellow red blue green tine yellow red green blue red yellow green red blue yellow green red yellow bluered yellow 匕1口亡 green red yellow green blue red blue yell口坤 green red fclue green yellow red green blue yellow red green yellow blue yellow red bln皂 green yellow red green blue yellowred 卩工亡皂nyellow blue green red yellow green