俄羅斯塊中兩個數學問題的解決方案

俄羅斯塊中兩個數學問題的解決方案

1生成的問題及求解首先，本文必須解決1999年提出的兩個數學問題。(1)俄羅斯方塊中的5個方塊(每個的面積都為4個單位格),各一片放入面積為4×5的矩形區(qū)域內(每一片都可以順時針逆時針旋轉,正反面翻轉與翻轉后旋轉后擺放在該矩形區(qū)域中,即可以任意擺放),有沒有正好將其完全覆蓋的方案?(2)在面積為6×6的正方形區(qū)域內,從5個方塊中任選1個方塊填充該區(qū)域(任意擺放),對于每一個方塊來說有沒有解?以上兩個問題目前的討論還僅局限于“有沒有解”,而通過本文的算法,不但知道有沒有解,有多少個解,每個解的具體內容,而且還可以將其可解決的問題范圍擴充到:對于任何面積為m×n的矩形區(qū)域,5個俄羅斯方塊每片都可以任意次擺放到該區(qū)域里(每片可以擺任意次,也可以不擺),共有多少種擺放方法,并計算每種擺放方法的圖形。而上面提到的兩個問題僅是這個問題的特例而已。當然,(m×n/4)的結果必須是整數,因為每個俄羅斯方塊的面積都是4,所以覆蓋區(qū)域面積必須要能被4整除。需要注意的是本文所謂的“所有解決方案個數”是沒有考慮到對稱性的,即圖形上對稱的兩個解或者是通過翻轉,反轉以后為相同的兩個解仍算做是兩個解。此外只要覆蓋的區(qū)域是由單位面積為1×1的小正方形組成的話,即使是不規(guī)則的區(qū)域,方塊不是俄羅斯方塊中的那5個,不管是任何的大小與形狀,不管有多少塊,都可以采用該算法解決。下面以6×6的矩形擺放區(qū)域,每塊俄羅斯方塊都可以擺放任意次(任意擺放,可以不擺)的情況為例,介紹算法的思想。2問題的算例1:某君之訴對6×6的區(qū)域中的每一個面積為1×1的單位小正方形,從左到右、從上到下的依次標上數字以標志每個小方格,如圖2所示。假設將方形的俄羅斯方塊放到該區(qū)域的左上角,則其覆蓋的區(qū)域的標號為:1,2,7,8。用一個長為36的1,0字符串,從前到后,在字符串第n位的字符對應正方形內n的編號的位置,其中1代表該位置被覆蓋,0代表該位置為空,用字符串表示如下:110000110000000000000000000000000000共36位而將方形放到該區(qū)域最中間的位置,表示這個覆蓋情況的0,1串為:000000000000001100001100000000000000共36位由上可知,5個俄羅斯方塊中任何一片的所有的覆蓋情況都可以用這樣的0,1串表示?，F在將俄羅斯方塊的每一塊的所有覆蓋該區(qū)域的情況都表示成這種長度為36的0,1串,每塊都要經過翻轉,反轉,在該區(qū)域內移動并擺放,以將其所有的擺放可能全部表示出來,并將所有的串作為一個0,1矩陣的行全部加入到這個矩陣里,對于該問題這個矩陣共有221行,36列。后文將這個矩陣稱為A。則由于如果存在完全覆蓋的可行解的話,每個單位小正方形就必須被某塊俄羅斯方塊覆蓋過,并且只被覆蓋過一次,則問題的算法思想可以抽象成:在該矩陣A內任意取出n行作為一個新的矩陣B的行,如果B當中的每一列都有且僅有一個1,那么這組行便是該問題的一個解。這個結論很好理解,一旦其中的某一行,即某個方塊的擺放方法將該區(qū)域的某個位置覆蓋的話,那其它方塊就不能再次覆蓋該位置,又因為要求是完全覆蓋,所以是每列有且僅有一個1。而對于該問題,這個n的值就為9,因為面積為36的區(qū)域需要9塊面積為4的俄羅斯方塊才能完全覆蓋。選擇其中的一行就相當于在該區(qū)域內擺了一個俄羅斯方塊,所以只能擺9個才可能有解。這樣就可以得出下面的算法1思想:算法1如果矩陣A為空并且已經選過了9行,則找到一組可行解,成功的返回;否則選取1個列,c,如果在c列中不存在1的話,不成功的結束該過程;選擇c列中每一個A[r,c]=1的行,r;將r值作為解決方案的一個步驟記錄下來;對于r行中每一個A[r,j]=1的j值,從矩陣A中將第j列刪除;對于j列中每一個A[i,j]=1的i值,從矩陣A中將第i行刪除;將已經縮小的矩陣重復進行以上運算;算法中,將r值作為解決方案的一個步驟記錄下來就是嘗試進行一種擺放并記錄這種擺放的操作,在這之后的那些刪除操作是要排除選擇第r行以后就不能再選的行,之后就是遞歸的進行下一步擺放的嘗試。3標志長形的俄羅斯配方有了這個思想,就可以知道其它的任何m×n的覆蓋區(qū)域問題或者是其它問題只是初始矩陣A的內容不同而已,都可以采用這種算法解決。像上文提到的問題(2),只要讓A中只有一種方塊的所有擺放情況,即如果只用長形俄羅斯方塊擺放的話,那么矩陣A中就只能有所有的標志長形俄羅斯方塊擺放的0,1串。只要分別對由每一塊方塊的所有擺放的5個矩陣A都分別進行這樣的運算,就可知僅擺放那一種俄羅斯方塊的所有解的情況;而問題(1),則只要在每個覆蓋0,1串后加入5位0,1串用來標志這5個方塊(是哪個方塊哪位就為1),假設長形的俄羅斯方塊為方塊1,那么標志長形的5位0,1串就為“10000”,對于第2塊方形的俄羅斯方塊,標志就為“01000”。將這5位數字與標志方塊的每一種擺放的情況,長為36位的0,1串連在一起,形成長為36+5=41位的串,這個長為41的串就標志著某個俄羅斯方塊的某種擺法。直接用該算法,就可以讓每個方塊“出現且僅出現一次”。原因是新加入的5個位是標志著哪一個方塊,如果讓其每一個位在使用該算法選擇時也“出現且僅出現一次”的話,也就使得每一個方塊也“出現且僅出現一次”了。4分布式表頭節(jié)點為了提高算法的效率,該算法并沒有直接采用0,1矩陣而是采用了“4向循環(huán)鏈表”的方式,后文將這種算法思想稱為“算法2”,加入了一個回溯過程和一個“S字段”以提高算法效率。首先清楚這個知識點:假設元素x屬于一個雙向鏈表,鏈表每一個元素由三個部分組成:①指向該元素前一個元素的指針;②指向該元素后一個元素的指針;③該元素本身的值。如果用L[x]與R[x]分別表示該元素的“前驅”與“后繼”的話,那么下面的操作(注:符號“←”表示將該符號右邊的值賦給其左邊):L[R[x]]←L[x];R[L[x]]←R[x](1)會把x從鏈表中移走,然后操作:L[R[x]]←x;R[L[x]]←x(2)會把已經被移走的x放回原來的位置。步驟(2)這個方法的最大好處就是:只需要x一個數據,就可以將該數據放回鏈表的原來位置。在這個算法當中,將矩陣A用“4向循環(huán)鏈表”來表示。將0忽略掉,為每一個1創(chuàng)建1個節(jié)點x,它包括5個部分:L[x](指向該節(jié)點的左面節(jié)點,如果該節(jié)點在最左面就循環(huán)指到最右面),R[x](指向該節(jié)點的右面節(jié)點,如果該節(jié)點在最右面就循環(huán)指到最左面),U[x](指向該節(jié)點的上面節(jié)點,如果該節(jié)點在最上面就循環(huán)指到最下面),D[x](指向該節(jié)點的下面節(jié)點,如果該節(jié)點在最下面就循環(huán)指到最上面),C[x](指向該節(jié)點所在列的“表頭”,下面將做說明)。而每一列比原來又多出一個特殊的“表頭”y,這個表頭在每列的最上端,y除了有正常節(jié)點的L[y],R[y],U[y],D[y],C[y]外,還比正常的結點多出兩個部分:S[y](該列里的節(jié)點個數,也就是1的個數,主要用于減少初始分支,提高運算效率,這很好理解,因為要是一個列里面的節(jié)點數少的話,在這個列所確定的所有備選行的數量就少,自然減少了遍歷的行數),N[y](該列的名字)。除此之外,矩陣A中還包含唯一一個叫“根”的節(jié)點h,它位于所有表頭節(jié)點的最左端,主要用于判斷是否找到合適的解,只用到L[h]與R[h],用于跟其它表頭左右循環(huán)相連。下面舉一個例子,假設矩陣A為:那么,用算法2的結構表示,則為圖3所示。記算法的名稱為Search(k),算法的基本思想如下:初始時k=0,算法里還有一個指針數組O,用于記錄解決方案所選擇的行。該算法里有一個特殊操作“覆蓋”,關于如何覆蓋將在后面說明。算法2Search(k)如果R[h]=h,找到一個解決方案,輸出并且返回;否則選取一列c(可以是第1列,也可以按S[c]選);覆蓋c列(什么是覆蓋操作在下面說明);對于每一個r←D[c],D[D[c]],……whiler不等于c(即是由上到下全訪問一次);賦值:O[k]←r;(將該行記錄)對于每一個j←R[r],R[R[r]],……whilej不等于r(即是由左到右全訪問一次);覆蓋第j列(下文說明);Search(k+1)(進入新一層的查找);賦值:r←O[k]并且c←C[r](從該行開始,以下的操作都是為了回溯,它們的操作順序與前面覆蓋的順序正好相反);對于每一個j←L[r],L[L[r]],……whilej不等于r;解除對第j列的覆蓋(下文說明);解除對c列的覆蓋并且返回。所謂覆蓋操作,就是將該列的表頭從“水平”方向移走,這一步僅斷開其L,R就可以起到避免訪問該列的效果了,這樣做不但運算量少,而且后面移動行的時候還要用到該列里面的元素。然后將該列的所有節(jié)點所對應的行上的節(jié)點從“豎直”的方向上移走,這樣就會消除與該列有沖突的行,而且還不干涉后面使用這些僅被在“豎直”方向移除的點。本質與算法1是一致的。具體方法如下:賦值:L[R[c]]←L[c]并且R[L[c]]←R[c];對于每一個j←D[c],D[D[c]],……whilei不等于c;對于每一個j←R[i],R[R[i]],……whilej不等于i;賦值:U[D[j]]←U[j],D[U[j]]←D[j];并且S[C[j]]←S[C[j]]-1。而解除覆蓋的順序正好與之相反:對于每一個i←U[c],U[U[c]],……whilei不等于c;對于每一個j←L[i],L[L[i]],……whilej不等于i;賦值:S[c[j]]←S[c[j]]+1;并且U[D[j]]←j,D[U[j]]←j賦值:L[R[c]]←c并且R[L[c]]←c。所謂順序相反,是指如果覆蓋的順序是由左至右的話,那么解除覆蓋的順序就是由右到左;如果覆蓋的順序是由上至下的話,那么解除覆蓋的順序就是由下到上,這樣才能按照原來覆蓋的順序返回到原來的鏈表狀態(tài)。該矩陣的4向循環(huán)鏈表的表示形式如圖3所示。如果現在按照算法2的頭一次覆蓋,要求覆蓋第A列的話,那么圖形表示如圖4所示,被曲線圍住的節(jié)點是將要被移除的節(jié)點,被曲線包圍的箭頭表示保留下來的指針箭頭。圖4不但演示了覆蓋的操作,同時對這個問題而言,也是第一步覆蓋以后的結果。表頭標號為A的那一列元素進行了覆蓋,也就是將A列中的兩個節(jié)點所在的行上的所有節(jié)點覆蓋,而且將A列的表頭覆蓋。只要覆蓋A的表頭就可以讓程序再也找不到該列元素。選擇列c的方法如下,先讓變量s←無窮大:對于每一個j←R[h],R[R[h]],……whilej不等于h;如果S[j]<s賦值:c←j并且s←S[j];結果的輸出方式如下:因為已經得到O這個數組,那么輸出第k個所選行只要輸出N[C[O[k]]],N[C[R[O[k]]]],N[C[R[R[O[k]]]]]……便可。即只要循環(huán)輸出從k=0到最后的情況,所選的某一行中的每一個元素就被輸出了。該問題共有1049組解。而在選擇這9個方塊的每一塊時,通過算法2的實驗,在每一個層次(就是在算法2中的Search(k)中的每一個k值,即表示算法運行的層次,也表示現在在選擇第幾塊)的運行分支情況由表1所示。通過實驗,得出采用算法1與算法2對于該問題的效率由表2、表3所示,其中增刪次數是指增加與刪除存儲單元的次數。由此可見,兩者的效率差距是巨大的,2.4G的CPU,512M的內存的電腦上,算法2可在一瞬間運算完畢,而算法1則需要在6個小時左右。其主要原因是算法2就不必像算法1那樣保存每一步計算以后的矩陣A,自然極大節(jié)省了存儲空間,同時減少了比較與賦值的次數。5未被覆蓋區(qū)域的r行算法這是針對俄羅斯方塊的特性進行的改進:每個俄羅斯方塊都是由在豎直或水平方向的連續(xù)4個小的1×1的單位小正方形組成,即其中的每個單位小正方形都在豎直或水平方向上至少與另一個單位小正方形相連,且這5個俄羅斯方塊是4個單位小正方形在豎直或水平方向相連的所有情況。根據這個特性,在算法1與算法2當中選擇一個方塊的擺放(在算法1,2中都是選定,記錄r行的那句話)之前加入一個判斷條件:如果在覆蓋區(qū)域中加入第r行的這種覆蓋以后,未被覆蓋的區(qū)域如果存在豎直,水平方向相連的所有單位小方塊的數量小于4,那么就不選擇r行,改試選r行的下一行。舉例來說,如果放入r以后,未被覆蓋的區(qū)域中有這樣的區(qū)域(見圖5)?；蛘呤峭ㄟ^旋轉或反轉本質是這幾種圖形,而周圍又都是被覆蓋的區(qū)域,即是說如果相連續(xù)的最大未覆蓋區(qū)域是這樣的話,那么就不要選擇r行。這種方法的目的與S字段一樣,就是要減少不必要的分支。表面看來似乎需要對每個未被覆蓋的單位小正方形(簡稱未覆蓋正方形)所相鄰的最大未覆蓋區(qū)域進行判斷,但實際上并不需要如此,通常情況僅需要判斷1個未覆蓋正方形所處的未覆蓋區(qū)域就可以確定r行是否可放了。首先遍歷該整個擺放區(qū)域找一個未覆蓋正方形,查找所有與其在豎直或水平方向相連的未覆蓋正方形,并對已經找到的未覆蓋的正方形進行同樣的遞歸查找其豎直或水平方向上未覆蓋小正方形(注意是所有相連的未覆蓋小正方形,即是其所處的最大未覆蓋區(qū)域),被判斷相連續(xù)的未覆蓋正方形就沒有必要再進行遍歷來判斷其所處的最大未覆蓋區(qū)域是否合理了,原因是當判斷完所有的連續(xù)情況時,如果這1塊未覆蓋正方形所連接未覆蓋的區(qū)域不合格,那么就沒有必要去判斷其他未覆蓋正方形而直接退出了,r行不能選;如果是合格的,那么對于處在該未覆蓋區(qū)域內的其它未覆蓋小正方形所處的未覆蓋區(qū)域也是這一個區(qū)域,所以沒有必要再去重復判斷,只要去判斷其它不