麻将胜利手算法

Question

我正在寻找一种算法，以确定当前的麻将手牌是否是一种获胜的手牌。如果您不熟悉这个游戏，这是基本思想（简化版）：

- 有三种花色的牌，每种花色都包含1-9的牌。还有特殊牌，共七种类型。每张牌都有四张复制品，因此每种花色有36张牌，特殊牌有28张。 - 手中有14张牌。 - “吃”是由同一花色的三张连续牌组成的一副牌。 - “碰”是由三张相同的牌组成的一副牌。 - “杠”是由四张相同的牌组成的一副牌。 - “对子”是由两张相同的牌组成的一副牌。 - 获胜的手牌是由任意数量的“吃”、“碰”和/或“杠”以及一个“对子”组成的。

手牌按花色和点数排序。我的想法是这样的：

- 将所有牌标记为未访问和非获胜状态。 - 访问第一张未访问的牌。 - 检查后续牌，直到遇到“吃”、“碰”或“杠”，或者没有可能性为止。如果完成了组合，则将所有参与的牌标记为已访问和获胜。 - 如果所有牌都被访问了，请检查它们是否都是获胜的。如果没有访问所有牌，则返回步骤2。 问题在于，一旦一张牌成为组合的一部分，它就不能成为任何其他可能使手牌获胜的组合的成员。

有关可行算法的任何想法？

- Igor

---

乒和空是同一件事吗？你说它们都是“三个相同的瓷砖组成的一套”。 - Marc B

如果获胜的手牌必须包含一对牌，那么您可以通过选择每个可能的对子并查看其余部分是否形成了“吃/碰/杠”（而不是将手牌分组并查看这些组是否恰好有一对牌）来大大缩小搜索空间。 - Ben Jackson

这个答案中的算法可以找到一个有效的手牌。 - Christian Ammer

Answer 1

如果你将算法嵌入到回溯算法中（http://en.wikipedia.org/wiki/Backtracking），那么你的算法就完全没问题了。最简单的方法是在找到匹配的一对/顺子/……时，通过递归调用你的方法，但如果不匹配，则放弃当前选择。伪代码如下所示：

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中的返回。

- Howard