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 回答