用于在手中查找街道和同类的算法

Question

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

在Mahjong中,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对),请返回上一次迭代并尝试下一个选项,或者,如果这是最高级别,则失败.否则,从剩余的切片列表中删除使用过的切片,然后继续下一次迭代.

我相信这种方法有效并且速度也相当快(性能是一个"不错的奖励"),但我对你的看法很感兴趣.你能想到其他解决方案吗？这个或类似的东西是否已存在？

(不是作业,我正在学习麻将.)

Answer 1

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

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

因此,如果您将已解决的手中的所有数字加在一起,您将获得3N + 2M形式的数字,其中M是该对中的图块的值.total % 3对于M的每个值,除以3()的余数为:

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瓦片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]