題目：已知馬走日。8*8的棋盤上，輸入馬的初始位置(x,y)，輸出一種能夠讓馬不重復(fù)地走遍整個(gè)棋盤的方法。（注：這題竟然沒要求最后必須回到出發(fā)點(diǎn)，什么鬼。）

解：看到這個(gè)題目，首先想到回溯法。用通俗的語(yǔ)言解釋，就是：

boolean 跳(棋盤b, 當(dāng)前點(diǎn)p) {

????如果b已完成，return true;

????否則，對(duì)于p的每一個(gè)可行的下一步位置p1，遞歸調(diào)用跳(去掉p1的b, p1)。然后如果其中有true則打印出來并return?true，否則return false;

}

說白了就是一個(gè)DFS。

于是我們首先構(gòu)造Point類，內(nèi)置x,y兩個(gè)參數(shù)并且實(shí)現(xiàn)一些有用的方法。

然后我們構(gòu)造棋盤類，其中內(nèi)置一個(gè)8*8的二維boolean數(shù)組，并實(shí)現(xiàn)clone()方法方便傳參。

然后構(gòu)造主類

然后就寫完了，是不是很簡(jiǎn)單？

我們只需要美滋滋的點(diǎn)擊運(yùn)行，然后。。

。。我擦，程序怎么卡住了？

。。三分鐘過去了

。。五分鐘過去了

。。十分鐘過去了，還是沒有算出東西來。

我擦，是哪里寫錯(cuò)了嗎？

我慌得要死，慌忙把棋盤大小改成6*6，卻發(fā)現(xiàn)程序一瞬間就給出了結(jié)果。

我忽而想起上次專欄里提到的沙雕同學(xué)的語(yǔ)錄，“指數(shù)復(fù)雜度的算法多少都沾點(diǎn)腦癱”。

凡事總須研究，才會(huì)明白。古來時(shí)常腦癱，我也還記得，可是不甚清楚。我翻開代碼一查，這代碼沒有注釋，歪歪斜斜的每葉上都寫著“深度優(yōu)先”幾個(gè)字。我橫豎睡不著，仔細(xì)看了半夜，才從字縫里看出字來，滿本都寫著兩個(gè)字是“腦癱”！

注：此時(shí)的算法實(shí)現(xiàn)了一個(gè)8叉n2層（n為棋盤邊長(zhǎng)），但下層比較稀疏的選擇樹，在最壞條件下的時(shí)間復(fù)雜度是O(8^(n2))。

但在這道題里，腦癱似乎不可避免。因此我們可以通過某種方式加快程序的運(yùn)行速度，這種方式就是（某種意義上的）貪心。即，在每一步跳躍時(shí)，優(yōu)先跳向那些鄰接點(diǎn)比較少的點(diǎn)，這樣可以盡量避免某些點(diǎn)成為所有鄰接點(diǎn)都用完的，不可訪問的“死點(diǎn)”。否則，在一個(gè)點(diǎn)成為“死點(diǎn)”后，程序仍然會(huì)傻乎乎的運(yùn)行半天，直到發(fā)現(xiàn)自己永遠(yuǎn)也達(dá)不到跳完的真實(shí)。為此，我們只需要對(duì)列表進(jìn)行排序：

然后重新運(yùn)行程序。

此時(shí)我們可以驚奇地發(fā)現(xiàn)，哇，新的算法算出結(jié)果只需不到一秒！

（但這并不影響它仍然是一個(gè)腦癱算法的本質(zhì)）

以上。