13

这实际上是一个基于麻将的问题，但是基于 Romme 甚至扑克的背景也很容易理解。

在麻将中，14 张牌（牌就像扑克牌中的牌）被排列成 4 组和一对。一条街道（“123”）总是使用恰好 3 个瓷砖，不多也不少。一组相同类型（“111”）也正好由 3 个牌组成。这导致总和为 3 * 4 + 2 = 14 个图块。

有各种例外，例如 Kan 或十三孤儿，在这里不相关。颜色和值范围 (1-9) 对算法也不重要。

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

例子：

11122233344455- 很简单，4 套和一对。
12345555678999- 123, 456, 789, 555, 99
11223378888999- 123, 123, 789, 888, 99
11223344556789- 无效手牌

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

我相信这种方法有效并且速度也相当快（性能是一个“不错的奖励”），但我对您对此的看法很感兴趣。你能想到替代解决方案吗？这个或类似的东西已经存在了吗？

（不是作业，我在学打麻将。）

4

3 回答 3

17

一条街道和一个集合中的值之和可以除以 3：

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

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

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

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

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

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

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

例如，对于您的无效手牌，总数为 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]
于 2010-11-11T14:06:40.293 回答
3

有一种特殊情况，您需要进行一些返工才能使其正确。这种情况发生在三人组和一对具有相同价值（但花色不同）的情况下。

设 b 为竹子，c 为字符，d 为点，试试这个手：

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

但是因为 3 个“c4”牌出现在 2 个 d4 牌之前，所以前 2 个 c4 牌将作为对被拾取，留下一个孤立的 c4 和 2 个 d4，这 3 个牌不会形成有效的集合。

在这种情况下，您需要将 2 个 c4 牌“归还”给手牌（并保持手牌排序），并搜索下一个符合条件的牌（值 == 4）。为此，您需要让代码“记住”它曾尝试过 c4，因此在下一次迭代中，它应该跳过 c4 并查找值 == 4 的其他图块。代码会有点混乱，但可行。

于 2012-10-31T04:52:05.820 回答
1

我会把它分成两个步骤。

  1. 找出可能的组合。我认为对这些数字进行详尽的检查是可行的。此步骤的结果是一个组合列表，其中每个组合都有一个类型（集合、街道或对）和使用的卡片模式（可能是位图）。
  2. 使用前面的信息，确定可能的组合集合。这是位图派上用场的地方。使用按位运算符，您可以看到不同组合器在使用相同图块时出现重叠。

您还可以执行步骤 1.5，您只需检查每种类型是否足够可用。这一步和第 2 步将是您能够创建通用算法的地方。对于所有数量的瓷砖和可能的组合，第一步将是相同的。

于 2010-11-11T14:06:24.607 回答