俄羅斯塊中兩個(gè)數(shù)學(xué)問(wèn)題的解決方案

俄羅斯塊中兩個(gè)數(shù)學(xué)問(wèn)題的解決方案

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