3

我正在寻找一种算法来确定当前的麻将手是否是赢家。如果你不熟悉游戏，这里是基本的想法（简化）：

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

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

  1. 将所有图块标记为未访问且未中奖。
  2. 访问第一个未访问的图块。
  3. 检查随后的牌，直到遇到吃、碰或杠，或者直到没有可能。如果组合完成，将所有参与的瓷砖标记为已访问并获胜
  4. 如果所有的牌都被访问过，检查它们是否都赢了。如果不是所有的图块都被访问过，请转到 2。

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

关于工作算法的任何想法？

4

1 回答 1

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

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

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

于 2011-02-09T05:42:50.100 回答