拉密数字牌(以色列麻将)破解程序

一、背景

这周去的攀岩馆是香蕉攀岩。

晚上 10 点多在回家的路上，我突然想吃点东西，便绕到 NC 攀岩馆看有啥吃的。

结果发现大家在玩桌游 ，中文名叫做拉密数字牌，也有人称为以色列麻将，英文名叫做 Rummikub。

我也加入玩了一把，回来后便想着可以使用程序破解，从而快速找到答案。

二、桌游规则

说是麻将，使用纸牌更恰当，因为牌的数字是从 1 到 13，也是四种颜色。
每个颜色数字出现两个，可以理解为有两副牌，共 104 张数字牌。

除了数字，还有两个花牌，称为“百搭”，可以变成任意花色任意数字的牌。
这样就共有 106 张牌。

介绍游戏规则之前，先介绍三个概念：群组、顺组、牌池。

顺组：至少 3 张颜色相同，数字不同且连续的一组牌（同花顺）。
群组：3 张或 4 张数字相同，颜色不同的一组牌。
牌池：打出去的牌放在一起，称为牌池。

游戏规则也很简单，分为几步。

发牌：开始的时候，所有牌在背面朝上，参与者分别随机选 14 张牌。

破冰：手上的牌需要能够打出几组群组或顺组，使得总和至少为30。
破冰时不可使用百搭牌。
如果不能打出，则从牌池里抽一张，这一轮结束。

碰：每一回合，可以优先尝试用自己的手上的牌与牌池去匹配，使得牌池的牌满足形成若干个群组或顺组。
如果可以匹配，则匹配结束后，这一轮结束。
如果无法匹配，则从牌池里抽一张，这一轮结束。

赢家：通过不断的碰或者打出群组或顺组，把自己手上的牌都打完，则算胜利。

游戏结束：所有人都打完牌，或者牌发完了但没人能继续打出去牌，游戏结束。

三、破解程序

弄清楚了棋牌的规则，我画了一天时间，做了一个网站，输入牌池，可以快速求出判断是否有答案，以及给出一组答案来。

另外为了能够自己模拟是否有答案，我使用可拖拽的画图程序，画了一个拖拽组件，可以自由拖拽。

手机端和桌面PC端差异很大，所以我分别找到对应端的画图库并画出了可拖拽的交互 UI。

感兴趣的小伙伴，可以后台输入“以色列麻将”获取网站地址。

四、实现原理

2月10号，我分享了《NC 攀岩馆的小程序挂了》。
有小伙伴说可以使用 docker compose 来管理多个服务。

2月6号，我分享了《读《Go语言从入门到进阶实战》》。
有小伙伴问我是否有计划使用 go 来写一些开源程序。

由此，我便打算设计一个系统，系统涉及到多个服务使用 docker compose 管理，核心破解算法服务使用 go 来计算。
架构图大概如下：

但是当我去想破解算法具体该如何实现时，发现实际情况并没有那么简单。

再来看下需要计算的数据：颜色有 4 种，每种颜色有 13 个数字，每个颜色的数字至少两个。

大家继续往下看之前，也可以自己先想象如果是你，会怎么设计这个算法。

一开始我增加一个 redis，就是想暴力打表，计算下所有合法情况的答案。
但是计算复杂度后，发现暴力搜索的话，状态太多了。

状态之所以多，是因为除了 13 个数字外，还有四种颜色。
由此我也找到一种突破点：先枚举群组，即枚举相同数字，之后四种颜色的数字没有关系单独判断。

每个数字单独判断的逻辑比较简单，26 个数字，可以预处理状态压缩，打表计算出所有合法答案。

对于枚举群组，就有点复杂了。

4 种颜色有 6 种群组。

[]
[红 粉 蓝]
[红 粉 黑]
[红 蓝 黑]
[粉 蓝 黑]
[红 粉 蓝 黑]

每种颜色又有 2 个数字，所以 4 种颜色的群组变成 21 个。

13 个数字，暴力搜索群组的复杂度就是 21^13。

一开始数字少时，可以毫秒级计算出答案。
但是数字多了，尤其是群组的数字多了，时间就会变得特别长。

比如下面这个样例，跑了 43.508s 才答案来。

五、最后

目前我的这个破解程序忘记添加 2 个”百搭“牌了。

即使先不管”白塔“牌，只处理数字，数据较多时，时间依旧比较长。

关于这点，目前我想了一些优化。
优化1：枚举之前先进行连通分支判断，每个连通图内部单独枚举判断。
优化2：优先枚举中间数组的群组，这样很大概率将一个连通图一分为 2。
优化3：优先枚举点少的的数字群组，少的话更大概率将连通图拆分为两个图。

但是，对于没有答案的情况，除了第一个优化，第二个优化都是无效的，最终都会枚举所有情况。
所以目前我没有想到其他好的优化算法。

你认为这个该如何优化呢？
是否有复杂度比较低的算法？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code