在手中找到街道和同类的算法

Question

这其实是一道麻将题，但有罗姆甚至扑克背景也能轻松理解。

在麻将中，14 张牌(牌类似于扑克牌中的牌)排列成 4 组和一对。一条街道(“123”)总是恰好使用 3 个方 block ，不多也不少。一组相同类型的牌(“111”)也恰好由 3 block 牌组成。这导致总和为 3 * 4 + 2 = 14 个图 block 。

有各种异常(exception)情况，例如 Kan 或 Thirteen Orphans，与此处无关。颜色和值范围 (1-9) 对于算法也不重要。

我正在尝试确定一手牌是否可以按上述方式排列。由于某些原因，它不仅应该能够处理 14 个，而且可以处理任意数量的图 block 。 (下一步是找出需要交换多少张牌才能完成一手牌。)

例子:

11122233344455 - 很简单，4 组和一对。
12345555678999 - 123、456、789、555、99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - 不是有效的手

我目前尚未实现的想法是:对于每个图 block ，尝试制作 a) 一条街道 b) 一组 c) 一对。如果没有效果(或者会有 > 1 对)，返回上一次迭代并尝试下一个选项，或者，如果这是最高级别，则失败。否则，从剩余瓦片列表中删除使用过的瓦片并继续下一次迭代。

我相信这种方法行之有效，而且速度也相当快(性能是一个“不错的奖励”)，但我很想知道您对此的看法。你能想到替代解决方案吗？这个或类似的东西是否已经存在？

(不是作业，I'm learning to play Mahjong.)

Answer 1

街道和集合中的值之和可以除以 3:

• n + n + n = 3n
• (n-1) + n + (n + 1) = 3n

因此，如果您将已解决的牌中的所有数字加在一起，您将得到 3N + 2M 形式的数字，其中 M 是这对牌中的牌值。对于 M 的每个值，除以三的余数(total % 3)是:

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

因此，您不必测试九个可能的对，只需基于简单的加法尝试三个。对于每个可能的对，删除具有该值的两个图 block ，然后继续算法的下一步以确定它是否可能。

一旦你有了这个，从最低值开始。如果具有该值的图 block 少于三个，则意味着它们必然是街道的第一个元素，因此删除该街道(如果您不能，因为图 block n+1 或 n+2 丢失，则意味着手无效)并移至下一个最低值。

如果至少有三个具有最低值的图 block ，将它们作为一个集合移除(如果您问“如果它们是街道的一部分怎么办？”考虑如果它们是，那么也有三个图 block n+ n+2 block 的 1 和 3，也可以变成集合)并继续。

如果到达空手，则该手牌有效。

例如，对于您的无效手，总数是 60，这意味着 M = {3,6,9}:

Remove the 3: 112244556789
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there is only one

Remove the 9: impossible, there is only one

对于第二个示例 12345555678999，总数是 78，这意味着 M = {3,6,9}:

Remove the 3: impossible, there is only one

Remove the 6: impossible, there is only one

Remove the 9: 123455556789
 - Start with 1: there is only one, so remove a street
   -> 455556789
 - Start with 4: there is only one, so remove a street
   -> 555789
 - Start with 5: there are three, so remove a set
   -> 789
 - Start with 7: there is only one, so remove a street
   -> empty : hand is valid, removals were [99] [123] [456] [555] [789]

你的第三个例子11223378888999也是一共78，导致回溯:

Remove the 3: 11227888899
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there are none

Remove the 9: 112233788889
 - Start with 1: there are less than three, so remove streets
   -> 788889
 - Start with 7: there is only one, so remove a street
   -> 888
 - Start with 8: there are three, so remove a set
   -> empty, hand is valid, removals were : [99] [123] [123] [789] [888]