估計(jì)在100位讀者中，有99位知道井字棋的玩法(假如不幸成為百里挑一，請(qǐng)用兩分鐘的時(shí)間上網(wǎng)了解一下弈棋規(guī)則)。在課堂上，簡(jiǎn)單的井字棋編程通常只是繪制一個(gè)井字棋棋盤，兩位玩家輪流弈棋，由計(jì)算機(jī)判斷輸贏本篇內(nèi)容暫不涉及計(jì)算機(jī)與玩家對(duì)弈的人工智能，而是聚焦程序，研究其判斷玩家輸贏的過程。最常見的方法是，用二維數(shù)組存儲(chǔ)每一步弈棋的狀態(tài)，然后按橫線、豎線以及對(duì)角線的位置取出相應(yīng)數(shù)組空間中的數(shù)據(jù)，分析這8條線中是否有任意一條線同一棋子數(shù)為3。本文的問題是，能不能找到其他判斷輸贏的方法呢?

來自古老洛書的啟示

《周易·系辭上》載有“河出圖，洛出書”。傳上古時(shí)代，有神龜出洛水，殼上所繪圖(見右圖)稱洛書。洛書圖案中藏著眾多數(shù)學(xué)奧妙，本文只提及其中很容易看出的幻方特性，即其九宮中各點(diǎn)數(shù)縱橫與對(duì)角相加均為15，這個(gè)特性恰能用來解決井字棋輸贏判定的問題。

按洛書的點(diǎn)數(shù)分別為井字棋棋盤各個(gè)空格編號(hào)，玩家著子后，不需要以二維數(shù)組的方式存儲(chǔ)數(shù)據(jù)，只要記錄下每個(gè)玩家著子位置所對(duì)應(yīng)的洛書編號(hào)即可，設(shè)先者棋子為X，后者為○，下表是假想某局對(duì)弈局面的變化。

X與○的對(duì)弈過程可逐步存儲(chǔ)到兩個(gè)一維的數(shù)組中。到第四回合，X在對(duì)角線上實(shí)現(xiàn)了三子連排，雖然人腦很容易分辨出來，但計(jì)算機(jī)卻不具有天生的圖形判別優(yōu)勢(shì)，怎么辦呢?聯(lián)系洛書的幻方特性，可發(fā)現(xiàn)x所存儲(chǔ)的數(shù)組中的數(shù)據(jù)中，一、三、四這三個(gè)回合中的編號(hào)數(shù)相加等于15。于是，判斷三子連排的模式，實(shí)際上等同于判斷X或○所存儲(chǔ)數(shù)據(jù)中，哪一方先取得任意三個(gè)編號(hào)相加等于15的局面。接下來的難點(diǎn)就在于，完成一局井字棋對(duì)弈可能需要三個(gè)回臺(tái)、四個(gè)回合甚至五個(gè)回合，計(jì)算機(jī)如何知曉呢?應(yīng)該如何“任意”取出三個(gè)數(shù)據(jù)做加法呢?

“排排坐，吃果果”

計(jì)算機(jī)不具備人類的“直覺”，不過利用數(shù)學(xué)的排列組合以及CPU速度的“蠻勁”，就能窮盡所有“任意”的狀態(tài)了。例如，將X數(shù)組中存儲(chǔ)的“5、4、2、8”取出后，按各種可能的次序重新排列，于是得到“4、2、8、5”、“2、8、5、4”、“8、5、4、2”等共24種序列，任一序列中再取前三位數(shù)字相加，一旦發(fā)現(xiàn)其和為15，則可判為獲勝。不過，這樣的排列組合方案并不是效率最高的，你能對(duì)此進(jìn)行優(yōu)化嗎?

怎么樣進(jìn)行排列組合的編程呢?這本來需要耗費(fèi)比較多的精力，但現(xiàn)在許多軟件開發(fā)工具都提供了功能強(qiáng)大的函數(shù)庫(kù)或類庫(kù)。例如，Python中的itertools中提供了permutations函數(shù)，Ruby中可使用permutation類，即使是Basic，在網(wǎng)絡(luò)上也能找到由熱心網(wǎng)友提供的函數(shù)代碼。你能自己找到其他方便的排列組合工具嗎?(答案在本期找)