搜索(計(jì)算機(jī)編程算法pascal)

搜索搜索算法是人工智能中的一種基本方法，利用計(jì)算機(jī)的高性能來(lái)有目的、有方法地窮舉一個(gè)問(wèn)題的部分或所有的可能情況，從而求出問(wèn)題的解的一種方法。在建立搜索算法時(shí)，首先需要關(guān)注的問(wèn)題是以什么作為狀態(tài)，這些狀態(tài)之間有什么樣的聯(lián)系。其實(shí)，在這樣的思考過(guò)程中，我們已經(jīng)不知不覺(jué)地將一個(gè)具體的問(wèn)題抽象成一個(gè)圖論的模型一樹(shù)，即搜索算法的使用第一步在于搜索樹(shù)的建立。根結(jié)耳、第0層弋0^丿一個(gè)成功的解X、、｝第1層/\/ '丿目標(biāo)巔第2層/第3匡由上圖可以知道，這樣形成的一棵樹(shù)叫搜索樹(shù)。初始狀態(tài)對(duì)應(yīng)著根結(jié)點(diǎn)，目標(biāo)狀態(tài)對(duì)應(yīng)著目標(biāo)結(jié)點(diǎn)。排在前的結(jié)點(diǎn)叫父結(jié)點(diǎn)，其后的結(jié)點(diǎn)叫子結(jié)點(diǎn)，同一層中的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)，由父結(jié)點(diǎn)產(chǎn)生的子結(jié)點(diǎn)叫擴(kuò)展。完成搜索的過(guò)程就是找到一條從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑，找出一個(gè)最優(yōu)的解。這種搜索算法的實(shí)現(xiàn)類似于圖或樹(shù)的遍歷，通?？梢杂袃煞N不同的實(shí)現(xiàn)方法：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）o深度優(yōu)先搜索（DFS）一、DFS的含義深度優(yōu)先搜索（DFS,DepthFirstSearch）是一種常見(jiàn)的搜索方法。常用來(lái)求一解、全部解或者是最優(yōu)解。它所遵循的搜索策略是盡可能“深”的搜索，在搜索樹(shù)的每一層始終先只擴(kuò)展一個(gè)子結(jié)點(diǎn)，不斷地向紐深前進(jìn)直到不能再前進(jìn)（到達(dá)葉子結(jié)點(diǎn)或受到深度限制）時(shí)，才從當(dāng)前結(jié)點(diǎn)返回到父親結(jié)點(diǎn)，沿另一個(gè)方向又繼續(xù)前進(jìn)，如此反復(fù)，直到求得最優(yōu)解。這種方法的搜索樹(shù)是從樹(shù)根開(kāi)始，一枝一枝逐漸形成的，即在搜索的過(guò)程中產(chǎn)生搜索樹(shù)。在深度優(yōu)先搜索過(guò)程中，常用作標(biāo)記的方法記錄訪問(wèn)過(guò)的狀態(tài),這種處理方法使得深度優(yōu)先搜索法與回溯沒(méi)什么區(qū)別了，DFS與回溯成為同一算法的兩個(gè)不同的名稱。二、DFS算法的程序深度優(yōu)先搜索算法可以簡(jiǎn)單地表述為“能深則深，不能深則回”的策略，具體表現(xiàn)在以下三個(gè)方面：1?搜索策略——能深則深如果擴(kuò)展到當(dāng)前i階段的一個(gè)k方案（樹(shù)中的結(jié)點(diǎn)）符合條件，則擴(kuò)展（用入棧）表示，并繼續(xù)按縱深方向向下一個(gè)結(jié)點(diǎn)擴(kuò)展（符合遞歸的思路），表示階段號(hào)的參數(shù)i表現(xiàn)為從小到大的變化趨勢(shì)。2.控制策略——不能深則回如果當(dāng)前要擴(kuò)展的結(jié)點(diǎn)不符合條件，則立即放棄此后的結(jié)點(diǎn)擴(kuò)展（此處的擴(kuò)展即為搜素，用出棧表示，階段號(hào)i則體現(xiàn)為由大變小這樣一種變化），換另一種方案擴(kuò)展?；氐臅r(shí)候常會(huì)遇見(jiàn)兩種情況：1）一種情況是i階段的所有方案已經(jīng)試探過(guò)，此時(shí)只能回到i-1階段，在i-1階段換一種方案試探，i-1階段的搜索方式依次類推；2）另一種情況是i階段還有試探方案，則在i階段換另一種方案，在程序中常用窮舉i階段的方案來(lái)實(shí)現(xiàn)。3.數(shù)據(jù)結(jié)構(gòu)常用棧來(lái)保存搜索過(guò)程中的狀態(tài)和路徑，所需空間大小為搜索所需最長(zhǎng)路徑的長(zhǎng)度。根據(jù)以上描述，每個(gè)階段的擴(kuò)展方式是一樣的，常用遞歸程序描述擴(kuò)展第i階段：procedureDFS（i:integer）;｛對(duì)第i階段進(jìn)行擴(kuò)展試探｝beginforr:=1tomaxrdo｛窮舉當(dāng)前階段所有可能的決策k（方案、結(jié)點(diǎn)）｝if子結(jié)點(diǎn)符合條件thenbegin擴(kuò)展子結(jié)點(diǎn)（入棧）if子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出結(jié)果else調(diào)用DFS（i+1）棧頂元素出棧 ｛回溯｝end;end;或者：procedureDFS（i:integer）;｛對(duì)第i階段進(jìn)行擴(kuò)展試探｝vark:integer;beginif所有階段都已經(jīng)求解thenbegin比較最優(yōu)解并保存；回溯；EndElseBegin窮舉當(dāng)前階段所以可能的方案k（方案、結(jié)點(diǎn)）Ifk方案可行thenBegin記錄狀態(tài)；DFS(i+1)(能深則深)狀態(tài)恢復(fù)(不能深則回)EndEnd;end;【注意】DFS常用來(lái)求一解、全部解或最優(yōu)解對(duì)于上述算法可以歸結(jié)為以下幾點(diǎn)：①邊界條件②搜索范圍 ③可行性判斷④目標(biāo)狀態(tài)三、DFS的應(yīng)用對(duì)于可以用深度優(yōu)先搜索算法解決的題目，可以按部就班，運(yùn)用填充教學(xué)同模式教學(xué)的思想構(gòu)建出程序框架。同時(shí)，在解題的實(shí)際過(guò)程中必須運(yùn)用同中求異的變式思維，根據(jù)不同的題目，對(duì)程序框架進(jìn)行適當(dāng)調(diào)整、優(yōu)化等，從而改進(jìn)時(shí)間和空間的效率?！厩笏薪鈤~模式的運(yùn)用】【構(gòu)造子串】生成長(zhǎng)度為n的子串，其字符從26個(gè)英文字母的前p(pW26)個(gè)字母中選取，使得沒(méi)有相鄰的子序列相等。例如p=3,n=5時(shí)：abcba滿足條件ababc不滿足條件【輸入】np【輸出】所有滿足條件的子串及總數(shù)【分析】狀態(tài)at：待擴(kuò)展的字母序號(hào)at。實(shí)際上字串s亦參與了遞歸運(yùn)算，但是由于該變量的存儲(chǔ)量太大，因此我們將s設(shè)為全局變量；邊界條件和目標(biāo)狀態(tài)：at=n+l；產(chǎn)生一個(gè)滿足條件的字串搜索范圍(可選方案)：'a'<ch<chr(ord('a')+p-l)：第at位置可填字母約束條件(可行性判斷)：當(dāng)前字符串沒(méi)有相鄰字串相等的情況Varn,p:integer;｛字符串長(zhǎng)度和可選字母的個(gè)數(shù)｝total:longint;｛滿足條件的字串?dāng)?shù)｝maxchr:char;｛可選字母集中的最大字母｝s:string; ｛滿足條件的字串｝proceduresolve(at:integer);varch:char;i:integer;beginifat=n+1then｛若產(chǎn)生了一個(gè)滿足條件的字串，則輸出｝beginwriteln(s);inc(total); ｛回溯｝exit;end;forch:='a'tomaxchrdo｛搜索每一個(gè)可填字母｝begins:=s+ch;i:=1;while(i<=atdiv2)and(copy(s,length(s)-i+1,i)<>copy(s,length⑸②i+1,i))do ｛檢查當(dāng)前字串是否符合條件｝inc(i);ifi>atdiv2thensolve(at+1);｛若當(dāng)前字串符合條件，則遞歸擴(kuò)展｝

delete(s,length(s),1);｛恢復(fù)填前的字串｝end;end;beginreadln(n,p); ｛輸入字串長(zhǎng)度和前綴長(zhǎng)短｝maxchr:=chr(ordCa')+p-1);｛計(jì)算可選字母集中的最大字母｝s:="; ｛滿足條件的字串初始化為空，字符串?dāng)?shù)為0｝total:=0;solve(1);｛從第一個(gè)字母開(kāi)始遞歸搜索｝writeln(total);end.四、DFS的優(yōu)化優(yōu)化經(jīng)常從最優(yōu)性剪枝、可行性剪枝兩方面來(lái)考慮，當(dāng)可行性與最優(yōu)性都不明顯時(shí)可以采用預(yù)處理方式來(lái)實(shí)現(xiàn)程序的優(yōu)化。1?剪枝優(yōu)化所謂剪枝，就是通過(guò)某種判斷條件，避免一些不必要的遍歷過(guò)程。形象地說(shuō)，就是剪去了搜索樹(shù)中的某些“枝條”。下圖是一個(gè)求最短路徑擴(kuò)展的搜索樹(shù)，描述了剪枝的過(guò)程。當(dāng)葉子結(jié)點(diǎn)D以找到了一個(gè)值為30的最短路徑，這時(shí)在搜索到G(50),H(35),J(30)時(shí)，其路徑長(zhǎng)度已經(jīng)大于或等于當(dāng)時(shí)最優(yōu)值，因此再搜索下去毫無(wú)意義，其下的結(jié)點(diǎn)都可以剪除，此時(shí)叫最優(yōu)剪枝；同理，如果G(50),H(35),J(30)這些結(jié)點(diǎn)已不符合約束條件，那么再搜索下去也毫無(wú)意思，此時(shí)的剪枝叫可行性剪枝?！臼圬泦T的難題】某鄉(xiāng)有n個(gè)村莊(lvnv40),有一個(gè)售貨員，他要到各個(gè)村莊去售貨，各村莊之間的路程s(0<s<1000)是已知的，且A村到B村與B村到A村的路大多不同。為了提高效率，他從商店出發(fā)到每個(gè)村莊一次，然后返回商店所在的村，假設(shè)商店所在的村莊為1,他不知道選擇什么樣的路線才能使所走的路程最短。請(qǐng)你幫他選擇一條最短的路?！据斎搿看迩f數(shù)n和各村之間的路程(均是整數(shù))?！据敵觥孔疃痰穆烦??！緲永縮alesman.insalesman,out3 ｛村莊數(shù)｝021｛村莊1到各村的路程｝102｛村莊2到各村的路程｝210｛村莊3到各村的路程｝3【算法分析】本題屬最優(yōu)化問(wèn)題，采用試探的深度優(yōu)先搜索策略。題目給定的村莊數(shù)不多(n<40),所以可以用回溯的方法，當(dāng)村莊數(shù)n比較大時(shí)，這種方法就不太適用To在中間搜索過(guò)程中(不是目標(biāo)狀態(tài))，假如已經(jīng)找到了一組比最小值大的解,那么它的最終結(jié)果一定大于先前找到的最小值，但是計(jì)算機(jī)仍然會(huì)義無(wú)反顧地去搜索比它更“劣”的其他解。為了避免出現(xiàn)這種情況，我們需要在搜索的過(guò)程中進(jìn)行最優(yōu)性剪枝。程序如下：vari,j,n,min:integer;a:array[1..40,1..40]ofinteger; ｛儲(chǔ)存圖｝v:array[1..40]ofboolean; ｛判斷該點(diǎn)是否訪問(wèn)過(guò)｝proceduredfs(step,line,m:longint);｛step步數(shù)，line當(dāng)前擴(kuò)展到的結(jié)點(diǎn)｝variinteger;beginifstep=nthen｛到達(dá)終點(diǎn)｝beginifm+a[line,1]<minthenmin:=m+a[line,1]endelsefori:=2tondoif(a[line,i]>O)andv[i]then｛當(dāng)前點(diǎn)未訪問(wèn)｝beginv[i]:=false;ifm+a[line,i]<minthen｛最優(yōu)剪枝｝dfs(step+1,i,m+a[line,i]);v[i]:=true;｛恢復(fù)遞歸前的值｝end;end;beginreadln(n);fori:=1tondoforj:=1tondoread(a[i,j]);fillchar(v,sizeof(v),true);min:=maxint;v[1]:=false;dfs(1,1,0);writeln(min);end.[導(dǎo)游](07年寧波市中小學(xué)程序設(shè)計(jì)決賽題guide.pas)寧波市的中小學(xué)生們?cè)阪?zhèn)海中學(xué)參加程序設(shè)計(jì)比賽之余，熱情的主辦方邀請(qǐng)同學(xué)們參觀鎮(zhèn)海中學(xué)內(nèi)的各處景點(diǎn)，已知鎮(zhèn)海中學(xué)內(nèi)共有n處景點(diǎn)?，F(xiàn)在有n位該校的學(xué)生志愿承擔(dān)和講解任務(wù)。每個(gè)學(xué)生志愿者對(duì)各個(gè)景點(diǎn)的熟悉程序是不同的，如何將n為導(dǎo)游分配至n處景點(diǎn)，使得總的熟悉程度最大呢？要求每個(gè)景點(diǎn)處都有一個(gè)學(xué)生導(dǎo)游?！据斎搿枯斎胛募uide,in有若干行；第一行只有一個(gè)正整數(shù)n,表示有n個(gè)景點(diǎn)和n個(gè)學(xué)生導(dǎo)游。第二行至第n+1行共n行，每行有n個(gè)以空格分隔的正整數(shù)。第i+1行的第j個(gè)數(shù)k(l<k<1000)，表示第i個(gè)學(xué)生導(dǎo)游對(duì)景點(diǎn)j的熟悉程度為k【輸出】輸出文件guide,out只有一行，該行只有一個(gè)正整數(shù)，表示求得的熟悉程序之和的最大值。【輸入輸出樣例】guide,inguide,out3106892317224【樣例說(shuō)明】第1個(gè)學(xué)生負(fù)責(zé)第3個(gè)景點(diǎn)，第2個(gè)學(xué)生負(fù)責(zé)第1個(gè)景點(diǎn)，第3個(gè)學(xué)生負(fù)責(zé)第2個(gè)景點(diǎn)時(shí)，熟悉程度綜合為24,達(dá)到最大值。【數(shù)據(jù)范圍】50%的數(shù)據(jù)，lWnW9100%的數(shù)據(jù)，lWnW17【分析】采用方法：深度優(yōu)先搜索+調(diào)整剪枝。問(wèn)題的實(shí)質(zhì)就是在搜索二維數(shù)組中的值，要求每行每列只能取一個(gè)值，然后求該數(shù)值的和，找出其中最大的和。根據(jù)樣例，首先建立一棵搜索樹(shù)。根據(jù)以樣例建立的搜索樹(shù)可以看出，可以采用深度優(yōu)先搜索遍歷搜索樹(shù)的方法求得該問(wèn)題的解，但是根據(jù)數(shù)據(jù)限制“100%”的數(shù)據(jù)lW:nW17,采用遍歷全部的方式肯定會(huì)超時(shí)。變通思維方式，題意中最大景點(diǎn)的值是1000,轉(zhuǎn)換二維數(shù)組的值，用1000減去該值，變求二維數(shù)組中最大的值為求最小值，然后在深度遍歷的過(guò)程中，比較所獲取的和值，和當(dāng)前已獲得的最小值比較，小則遞歸處理下一個(gè)數(shù)值，大或者等于則剪枝回溯，直到depth>nvara:array[1..20,1..20]oflongint;f:array[1..2O]ofboolean;傭于標(biāo)識(shí)景點(diǎn)、導(dǎo)游是否被分配過(guò)｝n,i,j,ans:longint;proceduredfs(i,s:longint);varj:longint;beginifi>nthen｛當(dāng)完成一次導(dǎo)游搜索組合，得出當(dāng)前最佳的熟悉程度值｝beginifans>sthenans:=s;exit;end;ifs>=ansthenexit;｛當(dāng)前得到的熟悉程度值大于先前最佳熟悉程度值時(shí)則剪枝｝forj:=1tondo｛按導(dǎo)游對(duì)各景點(diǎn)的熟悉程度搜索｝iff[j]then｛假如該景點(diǎn)未被分配過(guò)導(dǎo)游｝beginf[j]:=false;｛標(biāo)識(shí)景點(diǎn)使用標(biāo)識(shí)｝dfs(i+1,s+a[ij]);｛累加景點(diǎn)熟悉程度值，并進(jìn)入下一層景點(diǎn)熟悉程度的搜索｝f[j]:=true; 成以該景點(diǎn)為前提的搜索，恢復(fù)現(xiàn)場(chǎng)，為同層下一景點(diǎn)搜索做準(zhǔn)備｝end;end;beginreadln(n);fori:=1tondoforj:=1tondobeginread(a[i,j]);a[ij]:=1000-a[ij];｛變求最大值為最小值｝end;fillchar(f,sizeof(f),true);ans:=maxlongint;dfs(1,0);｛深度搜索調(diào)用｝writeln(n*1000-ans); ｛求得最大熟悉程度的值｝end.[數(shù)的拆分](snumber.pas)對(duì)于正整數(shù)n,輸出其和等于n且滿足以下限制條件的所有正整數(shù)的和式，以及和式的總數(shù)。組成和式的數(shù)字自左向右構(gòu)成一個(gè)非遞增的序列。如n=4,程序輸出為：4=44=3+14=2+24=2+1+14=1+1+1+1【輸入】輸入文件snumber.in僅一行，該行只有一個(gè)正整數(shù)n(Kn<50)【輸出】輸出文件snumber.out包含若干行，最后一行輸出和式的數(shù)目，除此之外，前面每一行輸出一個(gè)和式，組成和式的數(shù)字自左向右構(gòu)成一個(gè)非遞增的序列，不同行的和式先按照等號(hào)右邊的第一個(gè)數(shù)字降序排列，若第一個(gè)數(shù)字相同，則按第二個(gè)數(shù)字降序排列，依次類推，直到輸出所有和式為止?！据斎胼敵鰳永縮number.insnumber.out55=55=4+15=3+25=3+l+l5=2+2+l5=2+l+l+l11+1+1+1+17【分析】采用方法：深度優(yōu)先搜索+調(diào)整剪枝。問(wèn)題的實(shí)質(zhì)就是對(duì)輸入的n進(jìn)行拆分。根據(jù)樣例建立一棵如下圖所示的搜索樹(shù)。由樣例圖可知，每一組數(shù)據(jù)存在兩個(gè)數(shù)字，前一個(gè)數(shù)字為依次需要拆分的數(shù)字，另一個(gè)為下一拆分起點(diǎn)最大數(shù)值(該數(shù)值在取值過(guò)程中需要進(jìn)行適當(dāng)?shù)恼{(diào)整,與先前所拆分的數(shù)值進(jìn)行比較，取兩者較小數(shù)值為再次拆分對(duì)象，即為下一層搜索對(duì)象的起始值，目的避免重復(fù)拆分?jǐn)?shù)值，進(jìn)行適度調(diào)整減枝），然后對(duì)該數(shù)值進(jìn)行遞歸處理，判斷剩余的數(shù)值是否為0,是則打印，并回溯至上一層，繼續(xù)該層中其他數(shù)值的拆分；不是則按序窮舉當(dāng)前層的所有取值，并遞歸深搜下一層剩余數(shù)值的拆分。以上圖拆分5=2+2+1和5=2+1+1+1為例，首先在完成前一組數(shù)值拆分恢復(fù)現(xiàn)場(chǎng)，回溯窮舉至2（第一層），得第一個(gè)拆分?jǐn)?shù)值2,余下的數(shù)值5-2,即為3,剩下數(shù)值3與已拆分前一個(gè)所得數(shù)值比較取較小值（避免5再次拆分成2和3）,獲得拆分?jǐn)?shù)值窮舉范圍即2-1。進(jìn)入第二層搜索，首先是窮舉2,獲得第二個(gè)拆分?jǐn)?shù)值2,計(jì)算剩余數(shù)值得1,然后遞歸調(diào)拆分余下的數(shù)值1.首先判斷剩下的數(shù)值是否為0（拆分完畢），不是，該數(shù)值與前一個(gè)拆分所得的數(shù)值2比較取小數(shù)值得1,獲得該數(shù)的數(shù)值拆分范圍為1-1?進(jìn)入第三層搜索，即第三個(gè)拆分?jǐn)?shù)值1,同時(shí)剩下的數(shù)值減去該數(shù)值得0,遞歸調(diào)用，拆分余下的數(shù)值0,在遞歸調(diào)用過(guò)程中，發(fā)現(xiàn)剩余數(shù)值為0,遞歸調(diào)用結(jié)束，即打印該拆分?jǐn)?shù)即5=2+2+1,恢復(fù)現(xiàn)場(chǎng)至上一層，得剩余數(shù)值為1,再次恢復(fù)現(xiàn)場(chǎng)至上一層（第二層），得剩余數(shù)值為3,窮舉下一個(gè)拆分值1,據(jù)悉完成5=1+1+1+1+1的拆分。vara:array[0..50]ofinteger;傭于存放拆分的數(shù)值｝left,n:integer;｛left用于存放n拆分以后所剩下的值｝total:longint;｛left用于存放n拆分以后所剩下的值｝proceduredfs（k:integer）;vari,min:integer;beginifleft=Othenbeginwrite（n；=',a[1]）;total:=total+1;fori:=2tok-1dowrite（'+',a[i]）;writein;endelsebeginifleft<a[k-1]thenmin:=leftelsemin:=a[k-1];fori:=mindownto1dobegina[k]:=i;left:=left-i;dfs(k+1);left:=left+i;end;end;end;beginassign(input,'snumber.in');reset(input);assign(output,'snumber.out');rewrite(output);readln(n);a[0]:=n;left:=n;total:=0;dfs⑴；writeln(total);close(input);close(output);end.[棋盤(pán)](checker.pas)檢查一個(gè)如下的6*6的跳棋棋盤(pán)，有6個(gè)棋子被放置在棋盤(pán)上，使得每行、每列只有一個(gè)，每條對(duì)角線（包括兩條主對(duì)角線的所有平行線）上至多有一個(gè)棋子，如下圖所示：3III| | |0|410I11111&111011116| | | | |O|I上面的布局可以用序列246135來(lái)描述，第i個(gè)數(shù)字表示在第i行的相應(yīng)位置有一個(gè)棋子，如下：行號(hào)123456歹！]號(hào)246135這只是跳棋放置的一個(gè)解。請(qǐng)編程找出所有跳棋放置的解，并以上面的序列方法輸出解(按字典順序排列)。請(qǐng)輸出前3個(gè)解，最后一行是解的總個(gè)數(shù)。【輸入】輸入文件checker,in僅一個(gè)數(shù)字n(6<n<13)表示棋盤(pán)是n*n大小的。【輸出】輸出文件checker,out前三行為前三個(gè)解，每個(gè)解的兩個(gè)數(shù)字之間用一個(gè)空格隔開(kāi)，第四行只有一個(gè)數(shù)字，表示解的總數(shù)。【輸入輸出樣例】checker,inchecker,out64613562514152634【分析】解決方法：深搜+優(yōu)化問(wèn)題的實(shí)質(zhì)就是類似八皇后問(wèn)題。首先建立一棵搜索樹(shù)，如圖所示以6*6的跳棋棋盤(pán)建立的搜索樹(shù)，在深度搜索解的過(guò)程中最為主要的是檢查判斷，即檢查同一行、同一列、對(duì)角線是否有其他棋子存在，為此可以通過(guò)建立標(biāo)志數(shù)組b[i]、c[i-k]和d[k+i]0數(shù)組b[i]控制同一列只能有一個(gè)棋子存在；c[i-k]控制“\”對(duì)角線是否有棋子存在，在同一“\”對(duì)角線上其行列坐標(biāo)之差是相等的；d[k+i]控制“/”對(duì)角線是否有棋子存在，在同一“/”對(duì)角線上其行列坐標(biāo)之和是相等的。這樣在放置下一個(gè)棋子的時(shí)候，判斷需要放置棋子位置的所在的列、對(duì)角線上是否有棋子，即該棋子的列、對(duì)角線標(biāo)志值是否為初始值“0”，是則可以放置該棋子，然后遞歸調(diào)用，直到depth〉!!，回溯；反之，枚舉同一行中的其他列放置位置。繼續(xù)判斷，一