algorithm - 麻将胜手算法

Question

我正在寻找一种算法来确定当前麻将牌是否获胜。如果您不熟悉这个游戏，这里是基本思路(简化版):

• There are three suits of tiles, each containing tiles ranked 1-9. There are also special tiles, seven types of them. Each tile exists in four copies, so there are 36 tiles of each suit and 28 special tiles.
• A hand has 14 tiles in it.
• A chow is a set of three tiles of a single suit with consecutive ranks.
• A pong is a set of three identical tiles.
• A kong is a set of four identical tiles.
• A pair is a set of two identical tiles.
• A winning hand is one in which the tiles form any number of chows, pongs, and/or kongs and one pair.

这手牌先按花色排序，然后再按等级排序。我的想法是这样的:

1. 将所有板 block 标记为未访问和未获胜。
2. 访问第一个未访问的图 block 。
3. 检查后续的牌，直到遇到吃牌、乒乓球或杠牌，或者直到不可能遇到。如果组合完成，将所有参与的牌标记为已访问和获胜
4. 如果所有的牌都被访问过，检查它们是否都赢了。如果不是所有的磁贴都被访问过，转到 2。

问题是，一旦一张牌成为组合的一部分，就不能成为任何其他组合的成员，而其他组合可能使这手牌成为赢牌。

对工作算法有什么想法吗？

Answer 1

如果您将算法嵌入到回溯算法 (http://en.wikipedia.org/wiki/Backtracking) 中，您的算法就很好了。最简单的方法是在找到匹配的 pair/chow/... 后递归调用您的方法，但如果没有则丢弃当前选择。在伪代码中，这看起来像这样:

1. Mark all tiles as nonwinning
2. Call function Backtracking

Function Backtracking:
1. If all tiles are marked winning return WINNING else NONWINNING
2. Visit tiles as described in your algorithm
3. When found a chow/pong/... or the first pair    
   3.1. Mark those tiles as winning.     
   3.2. Afterwards call method Backtracking.    
   3.3. If return value of 3.2 is WINNING also return WINNING    
   3.4. Else unmark the tiles as nonwinning again    
4. If not finished search for pair/chow/... by looping to 3.
5. All combinations are done and no winning movewas found so return NONWINNING

背后的想法是，您首先尝试将每一对/...作为获胜手的一部分，但如果这不起作用，则假设它不是获胜手的一部分，然后尝试相同的方法。

如果您不仅对获胜的手牌感兴趣，而且对获胜对子/顺子/的所有可能组合感兴趣，请跳过步骤 3.3 中的返回。