簡(jiǎn)介C麻將胡牌算法實(shí)現(xiàn)包面向游戲開發(fā)愛好者與算法學(xué)習(xí)者完整演示普通胡牌與癩子胡牌兩種規(guī)則的核心編碼思路。項(xiàng)目以回溯法遍歷順子、刻子、對(duì)子等基礎(chǔ)牌型組合逐一驗(yàn)證胡牌條件并通過(guò)剪枝減少無(wú)效搜索癩子部分則根據(jù)當(dāng)前手牌與潛在胡牌組合動(dòng)態(tài)判斷最優(yōu)替代對(duì)象同時(shí)兼顧額外番數(shù)計(jì)算清晰展示萬(wàn)能牌在麻將判定中的處理技巧。資源中的cpp文件負(fù)責(zé)牌型判斷與主流程控制h文件負(fù)責(zé)相關(guān)類與函數(shù)聲明代碼量不多但層次分明便于對(duì)照理解牌組表示、遞歸返回與邊界判定。壓縮包體積僅23KB共4個(gè)文件包含2個(gè)cpp與2個(gè)h結(jié)構(gòu)緊湊可直接閱讀調(diào)試。目前已有1361人學(xué)習(xí)下載適合希望快速掌握麻將胡牌流程、提升C算法實(shí)現(xiàn)能力的開發(fā)者參考。 做棋牌游戲后臺(tái)的同學(xué)十有八九都會(huì)在胡牌判斷上栽過(guò)跟頭。尤其癩子玩法一開手里那張萬(wàn)能牌能當(dāng)萬(wàn)、能當(dāng)條、能當(dāng)筒甚至兩張癩子還能湊一對(duì)將牌改來(lái)改去總有漏判。前陣子幫一個(gè)麻將項(xiàng)目重構(gòu)算法模塊把帶癩子的胡牌判斷完整寫了一遍今天把思路、C代碼實(shí)現(xiàn)和調(diào)試過(guò)程中踩過(guò)的坑一起整理出來(lái)。這篇適合兩類人看一是做棋牌游戲服務(wù)端的開發(fā)者二是準(zhǔn)備面試時(shí)被問(wèn)到麻將胡牌怎么判斷的C崗位候選人。看完你至少能直接抄一份能跑的代碼再遇到兩張癩子能不能胡七對(duì)帶癩子怎么判這類問(wèn)題也不會(huì)慌。1. 先想清楚胡牌的本質(zhì)到底是什么1.1 牌型編碼與狀態(tài)表示麻將牌不管什么地區(qū)玩法核心結(jié)構(gòu)就兩類數(shù)字牌和字牌。數(shù)字牌分為萬(wàn)、條、筒三門每門從1到9各四張字牌包括東南西北中發(fā)白一共七種。編碼時(shí)最常用的做法是給34種牌各分配一個(gè)下標(biāo)0到8代表萬(wàn)子9到17代表?xiàng)l子18到26代表筒子27到33代表字牌。這個(gè)編碼方案最大的好處是判斷順子時(shí)可以直接用下標(biāo)連續(xù)性。比如下標(biāo)3、4、5對(duì)應(yīng)的就是4萬(wàn)、5萬(wàn)、6萬(wàn)只要這三個(gè)位置都有牌就能組成一組順子。字牌因?yàn)椴粎⑴c順子單獨(dú)放到最后一段判斷時(shí)只需要處理刻子邏輯上天然隔離。手牌的存儲(chǔ)用int count[34]數(shù)組即可count[i]表示第 i 種牌的數(shù)量。比如手里有兩張紅中下標(biāo)32對(duì)應(yīng)的值就是2。相比用vector存儲(chǔ)每一張牌數(shù)組計(jì)數(shù)的方式在遞歸回溯時(shí)更方便減法加法都直接作用于下標(biāo)不需要頻繁查找和刪除元素。這一步是整個(gè)算法的地基選對(duì)了后面少踩很多坑。1.2 為什么回溯法是最合適的方案麻將胡牌判定標(biāo)準(zhǔn)的定義是手牌能夠拆成一副將牌兩張相同以及若干組順子或刻子。以14張手牌為例就是1副將牌加4組面子如果是7對(duì)子玩法則另算。順著這個(gè)定義往后推最直觀的思路是枚舉所有拆分方式逐一驗(yàn)證但手牌組合數(shù)量非常大直接枚舉不現(xiàn)實(shí)。回溯法是這類問(wèn)題最常用的解法。它的核心邏輯是每次從手牌里取出一組面子順子或刻子遞歸處理剩余牌直到所有牌都被拆完就返回成功任何分支走不通就回溯換一種拆法。因?yàn)槊恳粚舆f歸都明確地消耗掉三張牌遞歸深度最大也只有4層到5層搜索空間非常小實(shí)際運(yùn)行幾乎瞬間完成。相比動(dòng)態(tài)規(guī)劃或者查表法回溯法還有一個(gè)優(yōu)點(diǎn)擴(kuò)展癩子規(guī)則時(shí)非常自然。癩子本質(zhì)上就是這張牌缺什么就能補(bǔ)什么在遞歸過(guò)程中只需要額外維護(hù)一個(gè)癩子數(shù)量在需要湊順子、刻子、將牌時(shí)優(yōu)先消耗癩子。這個(gè)思路后面會(huì)展開講先扎實(shí)把不帶癩子的常規(guī)判斷寫對(duì)。2. 不帶癩子的基礎(chǔ)胡牌判斷2.1 將牌必須單獨(dú)拎出來(lái)處理普通胡牌的判斷邏輯可以拆成兩步第一步選定將牌第二步判斷剩余牌能不能全部拆成順子或刻子。為什么一定要先把將牌拎出來(lái)因?yàn)橐桓焙评镏挥幸粚?duì)將牌它的位置是唯一的如果不單獨(dú)處理遞歸拆面子時(shí)很容易把兩張相同的牌分別拆進(jìn)兩個(gè)不同的組最后整個(gè)拆分結(jié)果變得混亂。將牌的選取只需要遍歷計(jì)數(shù)數(shù)組找到任何count[i] 2的位置先減去2張?jiān)賹?duì)剩余牌做面子拆分判斷。如果剩余牌能全部拆完說(shuō)明這副牌能胡如果不能就把減掉的2張加回去繼續(xù)嘗試下一種將牌。這一步要注意如果某一種牌正好有2張它有可能是將牌也有可能分別被用進(jìn)兩個(gè)不同的順子或刻子里所以必須讓回溯搜索覆蓋到所有可能性不能看到2張就默認(rèn)是將牌。2.2 遞歸拆面的核心函數(shù)面子拆分的核心函數(shù)只有一個(gè)找到第一個(gè)非零計(jì)數(shù)的牌然后嘗試把它拆成刻子或順子。這里有個(gè)細(xì)節(jié)為什么只處理第一張非零牌因?yàn)椴还茏罱K怎么拆這張牌必須屬于某個(gè)面子而且它是最左邊的牌意味著它不可能作為順子里的第二張或第三張去依賴更小的牌只能作為刻子的三張之一或者順子的第一張。這大大減少了分支數(shù)量。拆刻子的情況比較簡(jiǎn)單條件是count[i] 3直接減掉3張遞歸判斷剩余牌。拆順子的情況就要檢查下標(biāo)是否落在數(shù)字牌范圍內(nèi)且不是該門的最后兩檔然后看count[i1]和count[i2]是否都大于0如果滿足則各減1張繼續(xù)遞歸。兩個(gè)分支只要有一個(gè)能走通就返回成功都走不通就回溯恢復(fù)原狀?；A(chǔ)版C代碼如下先跑通這個(gè)再上癩子bool canSplit(int* cnt) { int i 0; while (i 34 cnt[i] 0) i; if (i 34) return true; // 嘗試拆刻子 if (cnt[i] 3) { cnt[i] - 3; if (canSplit(cnt)) { cnt[i] 3; return true; } cnt[i] 3; } // 嘗試拆順子只針對(duì)數(shù)字牌且下標(biāo)不能是本門第7、8、9張 if (i 27 i % 9 6 cnt[i 1] 0 cnt[i 2] 0) { cnt[i]--; cnt[i 1]--; cnt[i 2]--; if (canSplit(cnt)) { cnt[i]; cnt[i 1]; cnt[i 2]; return true; } cnt[i]; cnt[i 1]; cnt[i 2]; } return false; } bool isHuBasic(int* cnt) { for (int i 0; i 34; i) { if (cnt[i] 2) { cnt[i] - 2; if (canSplit(cnt)) { cnt[i] 2; return true; } cnt[i] 2; } } return false; }這里有個(gè)容易忽略的地方canSplit里的 while 循環(huán)每次都要從頭掃描數(shù)組聽著效率不高但實(shí)際牌型只有34種遞歸層數(shù)很淺一次完整的胡牌判斷大概也就幾百次循環(huán)耗時(shí)在微秒級(jí)別。真正上線跑服務(wù)端也完全扛得住不需要過(guò)度優(yōu)化。3. 癩子加入后如何處理3.1 處理癩子的三種思路對(duì)比加入癩子后最容易想到的方案是把癩子牌的所有可能性枚舉一遍。比如有兩張癩子就把每一張依次當(dāng)成34種牌去嘗試組合數(shù)最高會(huì)膨脹到34^kk是癩子數(shù)量第一次跑就把我嚇到了三層循環(huán)下去直接超時(shí)。第二種思路是預(yù)先打表把34種牌的所有胡牌組合預(yù)生成到一個(gè)哈希表里查詢時(shí)直接看手牌是否匹配。這個(gè)方案在癩子數(shù)量固定、牌型范圍小的場(chǎng)景下可行但工作量大而且遇到多種地方規(guī)則修改比如七對(duì)、十三幺時(shí)又要重新生成維護(hù)成本太高。真正可行的是第三種思路在遞歸過(guò)程中動(dòng)態(tài)消耗癩子。癩子不是某一張具體的牌而是一種抽象的補(bǔ)齊能力。當(dāng)遞歸發(fā)現(xiàn)手牌缺一張牌才能組成面子時(shí)直接從癩子池里扣掉一張當(dāng)癩子數(shù)量不夠補(bǔ)這個(gè)分支就走不通。這個(gè)思路在搜索過(guò)程中自動(dòng)覆蓋了癩子變成任意牌的所有可能不需要顯式枚舉復(fù)雜度只跟癩子數(shù)量和遞歸深度有關(guān)效率高得多代碼也簡(jiǎn)潔。3.2 遞歸中消耗癩子的三條規(guī)則理解動(dòng)態(tài)消耗癩子核心就三條規(guī)則。第一條組成刻子時(shí)如果某種牌只有1張或2張可以用癩子補(bǔ)足剩余數(shù)量比如1張真牌加2張癩子就湊一個(gè)刻子如果已經(jīng)有3張及以上就正常拆刻子。第二條組成順子時(shí)如果相鄰位置上缺牌可以用癩子代替。例如手里有5萬(wàn)和7萬(wàn)缺6萬(wàn)遞歸處理到5萬(wàn)作為順子起點(diǎn)時(shí)發(fā)現(xiàn)6萬(wàn)位置為空就直接消耗1張癩子補(bǔ)上。如果癩子池里不夠補(bǔ)則放棄順子分支。第三條將牌也可以由癩子參與。一種情況是一張真牌加一張癩子組成將牌另一種是兩張癩子直接當(dāng)一對(duì)將牌。這兩個(gè)分支要在選將的枚舉里單獨(dú)加進(jìn)去否則手里只剩兩張癩子時(shí)就會(huì)誤判為不能胡。還有第四條隱藏規(guī)則所有手牌都拆完后如果癩子還有剩余剩余數(shù)量必須是3的倍數(shù)。因?yàn)槭Ｏ碌陌]子每3張可以組成一副刻子如果只剩1張或2張說(shuō)明這副牌多出來(lái)了沒(méi)法成組的牌不能判胡。這個(gè)邊界條件特別容易被忽略我第一次寫漏了導(dǎo)致手里多一張癩子也誤報(bào)胡牌。3.3 完整C代碼帶癩子的胡牌判斷把上面幾條規(guī)則落到代碼里canSplitWithLaizi作為核心遞歸函數(shù)先處理第一張非零牌再看刻子和順子的分支。刻子分支注意要區(qū)分cnt[i] 3直接拆和cnt[i] 3用癩子補(bǔ)兩種情況。順子分支也是類似分別統(tǒng)計(jì)i1和i2位置缺幾張癩子缺了就從癩子池里扣。bool canSplitWithLaizi(int* cnt, int laizi) { int i 0; while (i 34 cnt[i] 0) i; // 所有真牌都用完了只剩癩子 if (i 34) { return laizi % 3 0; } // 分支1拆刻子 if (cnt[i] 3) { cnt[i] - 3; if (canSplitWithLaizi(cnt, laizi)) { cnt[i] 3; return true; } cnt[i] 3; } // 分支2用癩子補(bǔ)齊刻子適用于 cnt[i] 1 或 2 if (cnt[i] 3 laizi 3 - cnt[i]) { int need 3 - cnt[i]; int save cnt[i]; cnt[i] 0; if (canSplitWithLaizi(cnt, laizi - need)) { cnt[i] save; return true; } cnt[i] save; } // 分支3拆順子 if (i 27 i % 9 6) { // 統(tǒng)計(jì)順子后兩張各缺幾張癩子 int need1 (cnt[i 1] 0) ? 0 : 1; int need2 (cnt[i 2] 0) ? 0 : 1; if (laizi need1 need2) { int temp1 cnt[i 1]; int temp2 cnt[i 2]; cnt[i]--; if (cnt[i 1] 0) cnt[i 1]--; else laizi--; if (cnt[i 2] 0) cnt[i 2]--; else laizi--; if (canSplitWithLaizi(cnt, laizi)) { cnt[i]; cnt[i 1] temp1; cnt[i 2] temp2; return true; } cnt[i]; cnt[i 1] temp1; cnt[i 2] temp2; } } return false; }主入口isHu在選將時(shí)擴(kuò)展癩子的能力。原來(lái)的遍歷真牌選將保留再額外加兩種分支真牌加癩子做將以及雙癩子做將。這里注意雙癩子做將要在最后嘗試因?yàn)槿绻媾票旧硪呀?jīng)能當(dāng)將盡量?jī)?yōu)先用真牌避免浪費(fèi)癩子導(dǎo)致后續(xù)面子拆不開。不過(guò)對(duì)于最終正確性來(lái)說(shuō)順序不影響結(jié)果因?yàn)槊總€(gè)分支只要能走通最終都會(huì)返回true。bool isHuWithLaizi(int* cnt, int laizi) { // 分支1普通真牌做將 for (int i 0; i 34; i) { if (cnt[i] 2) { cnt[i] - 2; if (canSplitWithLaizi(cnt, laizi)) { cnt[i] 2; return true; } cnt[i] 2; } } // 分支2一張真牌 一張癩子做將 if (laizi 1) { for (int i 0; i 34; i) { if (cnt[i] 1) { cnt[i]--; if (canSplitWithLaizi(cnt, laizi - 1)) { cnt[i]; return true; } cnt[i]; } } } // 分支3兩張癩子自己做將 if (laizi 2) { if (canSplitWithLaizi(cnt, laizi - 2)) return true; } return false; }調(diào)用入口需要先把癩子牌從計(jì)數(shù)數(shù)組里拆出來(lái)。比如癩子固定為紅中那就是int laizi cnt[32]; cnt[32] 0;然后把普通牌數(shù)組和癩子數(shù)量一起傳進(jìn)去。這里有個(gè)容易犯的錯(cuò)如果把癩子牌本身留在數(shù)組里又同時(shí)傳入癩子數(shù)量遞歸時(shí)會(huì)把它既當(dāng)作普通牌又當(dāng)作萬(wàn)能牌數(shù)量就重復(fù)計(jì)算了。4. 實(shí)戰(zhàn)中的坑與性能建議4.1 數(shù)組拷貝與恢復(fù)的坑寫這個(gè)算法時(shí)有一個(gè)非常隱蔽的坑在canSplitWithLaizi里操作順子時(shí)我一開始圖省事沒(méi)有保存cnt[i1]和cnt[i2]的原始值而是走完分支后手工加回來(lái)。表面看沒(méi)問(wèn)題但一旦某個(gè)分支里遞歸函數(shù)提前返回true后面的代碼就不執(zhí)行了狀態(tài)恢復(fù)被跳過(guò)。特別是遞歸返回true時(shí)我們根本不需要恢復(fù)現(xiàn)場(chǎng)因?yàn)檎麄€(gè)函數(shù)要結(jié)束了但如果后續(xù)還要嘗試其他分支就必須確保現(xiàn)場(chǎng)已經(jīng)完全恢復(fù)。我的做法是每個(gè)分支在遞歸調(diào)用前保存涉及的所有修改點(diǎn)的原值遞歸返回后立即恢復(fù)如果遞歸返回true直接return不需要再恢復(fù)。代碼里的temp1、temp2就是干這個(gè)的。另外整個(gè)判斷過(guò)程中cnt數(shù)組是會(huì)被反復(fù)修改的所以調(diào)用isHuWithLaizi之前一定要傳一份數(shù)組副本進(jìn)去避免外層函數(shù)的手牌被破壞。4.2 處理特殊牌型七對(duì)與十三幺上面的算法只能判斷平胡牌型也就是常規(guī)的將牌加面子結(jié)構(gòu)。但很多麻將規(guī)則里有七對(duì)、豪華七對(duì)甚至十三幺。七對(duì)的判斷其實(shí)非常簡(jiǎn)單14張牌每一種牌的張數(shù)必須都是偶數(shù)1對(duì)、2對(duì)或3對(duì)再加癩子補(bǔ)對(duì)子。用癩子時(shí)更加寬松因?yàn)榘]子可以補(bǔ)任意對(duì)子。一個(gè)常見需求是七對(duì)帶癩子判斷方式可以先統(tǒng)計(jì)真牌中的對(duì)子數(shù)量再算需要多少個(gè)癩子去補(bǔ)足7對(duì)。如果真牌里奇數(shù)張的存在數(shù)量不超過(guò)癩子數(shù)量再把多余癩子成對(duì)處理整體滿足7對(duì)即可。這個(gè)邏輯和平胡判斷完全獨(dú)立通常放在isHuWithLaizi之前單獨(dú)分支判斷哪個(gè)規(guī)則返回true就算胡。十三幺是比較特殊的地域玩法一手牌全是幺九和字牌再加任意一個(gè)對(duì)子。判斷時(shí)枚舉幺九字牌的種類是否齊全缺幾個(gè)用癩子補(bǔ)最后看有沒(méi)有對(duì)子或癩子補(bǔ)對(duì)子。這類牌型頻率低對(duì)性能影響不大但千萬(wàn)別漏掉否則玩家摸到十三幺報(bào)不了胡投訴電話很快就會(huì)打過(guò)來(lái)。4.3 性能實(shí)測(cè)與優(yōu)化建議這套算法在遞歸深度上非常克制正常情況下處理14張牌的判斷耗時(shí)不到1微秒單機(jī)每秒能跑上百萬(wàn)次。但如果癩子數(shù)量有4張甚至更多遞歸分支會(huì)變多最壞情況耗時(shí)可能到幾十微秒。對(duì)于服務(wù)端來(lái)說(shuō)仍然可以接受但如果某個(gè)房間同時(shí)有大量玩家頻繁操作還是值得做一層緩存。我的優(yōu)化經(jīng)驗(yàn)有兩條。第一在遞歸函數(shù)最前面加一個(gè)快速剪枝統(tǒng)計(jì)所有剩余真牌數(shù)量加上癩子數(shù)量如果不是3的倍數(shù)直接返回false。這個(gè)剪枝看似簡(jiǎn)單實(shí)際能省掉大量無(wú)效遞歸分支。第二利用牌總數(shù)較少的特性把所有非法分支概率最高的牌先處理優(yōu)先處理字牌和數(shù)量大于等于3的牌因?yàn)樽峙撇荒芙M順子能拆就拆拆不了就盡早返回。另外服務(wù)端多線程跑房間時(shí)每個(gè)房間可以獨(dú)立使用一份計(jì)數(shù)數(shù)組避免線程間共享狀態(tài)。遞歸函數(shù)本身是無(wú)狀態(tài)的只要入口保證傳入的是副本并發(fā)安全就沒(méi)有問(wèn)題。5. 常見問(wèn)題速查表問(wèn)題原因解決方案手里剩兩張癩子卻判胡不了雙癩子做將的枚舉分支沒(méi)加在選將階段增加 laizi 2 時(shí) canSplit(cnt, laizi - 2) 的判斷癩子數(shù)量被重復(fù)計(jì)算癩子牌同時(shí)留在 count 數(shù)組里又傳入 laizi 參數(shù)入口處先把癩子牌從數(shù)組中清零再傳參遞歸返回后死循環(huán)或結(jié)果錯(cuò)亂回溯時(shí)沒(méi)有恢復(fù)修改過(guò)的數(shù)組元素每個(gè)分支進(jìn)入前保存原值return 前恢復(fù)現(xiàn)場(chǎng)剩余癩子不是3的倍數(shù)也判胡結(jié)束條件只判斷了真牌用完真牌用完時(shí)加判斷l(xiāng)aizi % 3 0七對(duì)帶癩子場(chǎng)景漏判主流程只走了平胡分支單獨(dú)寫七對(duì)判斷函數(shù)在平胡判斷之前或之后并行走字牌被當(dāng)成順子拆分字牌范圍 27 到 33下標(biāo)連續(xù)導(dǎo)致誤判順子分支加i 27且i % 9 6的條件再補(bǔ)充一個(gè)調(diào)試技巧測(cè)試胡牌算法時(shí)不要只看幾個(gè)正常case要把缺一張癩子補(bǔ)順子、兩張癩子補(bǔ)刻子、一張真牌一張癩子做將、雙癩子做將這四種情況各寫進(jìn)單元測(cè)試?yán)?。我?dāng)初整理了一個(gè)用例文件包含二十多組手牌數(shù)據(jù)每次改動(dòng)算法后跑一遍基本能攔住99%的回歸問(wèn)題。6. 寫在最后的工程建議癩子胡牌算法寫完只是第一步真正考驗(yàn)人的是它和整體業(yè)務(wù)代碼怎么整合。我習(xí)慣把胡牌判斷封裝成一個(gè)純函數(shù)模塊輸入是手牌數(shù)組和癩子數(shù)量輸出只有 true 或 false不依賴任何全局狀態(tài)。這樣不管是做三人麻將、四人麻將還是血流成河只要把癩子定義和特殊牌型開關(guān)作為配置傳進(jìn)來(lái)同一個(gè)函數(shù)都能復(fù)用。實(shí)際項(xiàng)目里還有一個(gè)細(xì)節(jié)每次玩家摸牌、出牌、碰杠后都要調(diào)用一次胡牌判斷所以在接入消息循環(huán)時(shí)一定要控制調(diào)用頻率。我見過(guò)有項(xiàng)目直接在每幀全量判斷房間內(nèi)所有玩家的手牌結(jié)果造成明顯卡頓。正確的做法是只在有胡需求的時(shí)候判斷自己摸牌后、別人出牌后并且每次都基于當(dāng)前玩家的手牌獨(dú)立判斷不緩存舊結(jié)果。這樣既不會(huì)有性能問(wèn)題代碼邏輯也清晰。最后再說(shuō)一句個(gè)人心得這個(gè)算法寫一次不難寫對(duì)是真的考細(xì)節(jié)。遞歸回溯的核心代碼只有幾十行但每一步都得想清楚癩子從哪里來(lái)狀態(tài)什么時(shí)候恢復(fù)邊界條件是什么。把上面幾個(gè)坑都踩一遍再回頭看你會(huì)發(fā)現(xiàn)麻將胡牌判斷也不過(guò)如此。本文還有配套的精品資源點(diǎn)擊獲取