麻将胜牌算法

Question

我正在寻找一种算法来确定当前的麻将牌是否获胜。如果您不熟悉该游戏，请看以下基本概念（简化）：

• 共有三组牌，每组包含排名 1-9 的牌。还有特殊的瓷砖，有七种。每张牌都有四张，因此每种花色有 36 张牌和 28 张特殊牌。
• 一手牌有 14 块。
• chow是一组连续等级的单一花色的三张牌。
• 乒乓球是一组三块相同的牌。
• 杠是一组四块相同的牌。
• 对是一组两个相同的图块。
• 获胜牌是指牌组成任意数量的 chows、pongs 和/或 kongs 以及一对。

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

1. 将所有瓷砖标记为未访问和未获胜。
2. 访问第一个未访问过的图块。
3. 检查后续的牌，直到遇到 chow、pong 或 kong，或者直到不可能出现。如果组合完成，则将所有参与的图块标记为已访问并获胜。
4. 如果所有图块都已被访问，则检查它们是否全部都获胜。如果尚未访问完所有牌，请转到 2。

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

对于可行的算法有什么想法吗？

Answer 1

如果您将其嵌入到回溯算法中，您的算法就很好了（http://en.wikipedia.org/wiki /回溯）。最简单的方法是在找到匹配的对/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

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

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