序

在元旦之前，本想炫技生成漂亮的数独图案的题目然后发在朋友圈祝朋友们节日快乐。可惜是技术实在不过关。

数独图形

在资深的数独迷眼里,标准数独是指通过盘面上的所有提示数字，有且仅有唯一解。
以下四个图形，虽说有“元旦快乐”的四个字样，但是并不具备唯一解。

我们可以经由DLX算法可以快速得知
以上“元旦快乐”四个数字的可能解的个数是分别是512,8388,66,285。

标准数独的基本条件

盘面至少17个数字。
每一大行中没有两个空行,即第一，二，三行必须有两行存在数字。
每一大列中没有两个空列,即第一，二，三列必须有两列存在数字。
盘面至少有8个不同的已知数字。
即元字的r3c8会有个2的存在是为了避免第一和第三行可以互换,不满足数独唯一性的必要条件。

求解过程

以元字的表达式为例

1
2
3
4

// 元表达式
var before = new DanceLink().solution_count("000000000001234500000000020134659782000308000000402000000703004009006007070001358");
// 元的第一个已知数据和第二个已知数据交换
var after  = new DanceLink().solution_count("000000000002134500000000020134659782000308000000402000000703004009006007070001358");

输出的结果是

1
2

before = 512;
after  = 312;

所以最终解可以由after的表达式进行进一步的两两交换去生成。
由因为A的已知数据是30个，所以位置的交换有30*29/2=435种。
整个交换的执行流程如下：
1、建立一个尝试字典集tryDic,键是数独的表达式,值是数独的结果的可能个数。
2、30个位置进行组合，生成435个包含两个位置的集合。
3、数独表达式交换前后分别记为before,after,解的个数分别记作b,a,将before,after及其结果数存入tryDic。
4、对435个集合进行遍历,若a!=0,且a小于b,则before=after;
5、很有可能第一轮排列组合之后,a并不等于1;没有找到唯一解的数独表达式,选取tryDic的结果个数最多的字符串S出来作为下一轮循环的因子。
6、循环执行1~5的过程，注意步骤5中的字符串S应该是过往循环中没有使用过的，否则会陷入死循环。

书上以

1

001000009000200046007080000000001000003000200000500000000030800960007000200000500

这个18个提示数的数独作为例子作为讲解，我也通过以上流程生成了一个18个提示数的标准数独。

借助书上的说法,除了聪明和运气，我们别无他法。

标准数独(元旦快乐)

最终生成的结果如下，难度不大。

逆向思维

由以上位置找固定数独的位置可知，如果标准数独去掉某个提示数，不在构成唯一解，但是满足构成标准数独的基本条件,则可能通过两两交换的生成一个新的标准数独。

参考资料

• C#实现排列、组合
• C#源码

序

最近业余时间在研究排列组合的相关问题,话题涉及到了在不考虑花色的情况下？54张牌按照斗地主的方式以20，17，17的方式分给3个人有多少中可能解决方案？
我觉得这个问题有点意思，并以sql脚本的形式实现了问题的求解过程，希望大家能从这篇文章中所有收获。

问题分析

以4个3为例，分给地主1，农民2，农民3的所有组合情况如下：

既4个3在3个玩家中的可能情况有15种。在不考虑斗地主手牌数限制的情况下,因A到K有13张牌，则A到K的所有位置的组合数有$15^{13}$种可能性。
以大王为例,分给地主1，农民2，农民3的所有组合情况如下：

在不考虑斗地主手牌数限制的情况下,大王和小王在三家的可能性有3*3=9种可能性。
所以牌型组合的理论上限是$9*15^{13}$。接近于$1.75*10^{16}$。

根据计数原理,结合上图可知：
如果37在玩家1，2，3的手牌张数分别是20，0，0的可行方法是1种。
如果8Q在玩家1，2，3的手牌张数分别是0，17，3的可行方法是35种。
如果K到大王在玩家1，2，3的手牌张数分别是0，0，14的可行方法是1种。
所以三个步骤组合起来的总可行方法是$1*35*1=35$种方法。

具体细节参考Sql server版斗地主牌型组合统计的代码,最终的出来的结果是138712181744994,即$1.3871*10^{14}$。即在不区分花色的情况下，斗地主所有的牌型组合数。

总结

记录斗地主的所有牌型这种方式来做AI是不切实际的，毕竟普通PC机是没有办法存储$1.3871*10^{14}$条数据的。

参考资料

• 计数原理
• m个球放到n个箱子中几种解法
• 欢乐斗地主出牌方式统计

序

该文的诞生源于一个问题:斗地主有多少种牌型组合?
众所周知,斗地主共54张牌分别给三个人20,17,17张牌，因为方块3和梅花3在斗地主中无区别，转化一下问题就是13种不同的颜色（不包括黑白）的球各4个,黑球，白球各1个,放到容积分别为20,17,17的三个箱子中有多少种方法？
第一想法是想到采取排列组合的方式去解，但是多久没有做排列组合的习题，我发现3红3黄3蓝1黑1白共11个球放到容积为5,3,3的三个箱子中,不考虑顺序总共有多少种方法？这个问题我都计算困难,该文简单讲一下该问题的两种解法。

正文

方案1：全排列

方案1.1 考虑黑白球

假设11个球的颜色全不相同,则所有排列顺序是1~11的全排列是11!=39916800。
再假设1,4,7为红球,2,5,8为黄球,3,6,9为蓝球，10为黑球,11为白球。
也可以1,2,3为红球,4,5,6为黄球,7,8,9为蓝球，10为白球,11为黑球。给球编号是为了计算全排列方便。
以全排列元素中的一个链表X(全排列的取值之一) **{9,8,3,5,6,4,11,7,1,2,10}**为例,
可以分成 **{9,8,3,5,6}**和 **{4,11,7}**和 **{1,2,10}三组。
将每组数据中≤9的对3取余,结果变成了A:{0,2,0,2,0}和B:{1,1,11}和C:{1,2,10}**三组数据。
∵ 在箱子中 **{4,11,7}**和 {4,7,11}是等价的。
∴ A、B、C三组都需要排序，排序后为{0,0,0,2,2}，{1,1,11},{1,2,10}
∴{9,8,3,5,6,4,11,7,1,2,10} 表示A箱子有3个蓝球，2个黄球；B箱子有2个红球,1个白球；C箱子有1个红球,1个黄球,1个黑球。
∴链表X的表达式是0,0,0,2,2,1,1,11,1,2,10
∴将39916800链表的表达式去重就可以算出序中提到的问题的解为355个。

方案1.2 先不考虑黑白球

∵黑球的可能位置只有3种,白球的可能位置也只有3种。
即黑白球都在A箱,都在B箱,都在C箱,分别在AC箱,分别在BC箱，分别在AB箱。
所有组合情况如下

这样就只需要计算9的全排列9!=362880次数据。
计算方式如方案1.1,再次不再赘述。
结果依旧为355。
具体计算代码请参考方案一代码

方案2：笛卡尔积

在不考虑各箱子容积的前提下；
每个球都有3个箱子可以选择，则11个球的位置有3的11次方=177147中可能性。
若箱子A,B,C编号为{1,2,3}。大小分别为{5,3,3}。
则第一个球和第二球的箱子可能组合是{1,2,3}和{1,2,3}的笛卡尔积

1

{   {1,1},{1,2},{1,3},   {2,1},{2,2},{2,3},   {3,1},{3,2},{3,3}  }  

将每个球所有的可能性做笛卡尔积之后，会得到一个177147个元素个数为11的链表L的集合S。
若链表L中有5个元素1，有3个元素2，有3个元素3。则链表L符合球进入箱子的逻辑。否则不符合球进入箱子的逻辑。
假若链表L为{1,2,3,2,3,2,1,1,1,1,3}且11个球的顺序为红,红,红,黄,黄,黄,蓝,蓝,蓝,黑,白
则箱子内的颜色情况如下:
A箱：红蓝蓝蓝黑
B箱：红黄蓝
C箱：红黄白
所以链表L的表示式为 A-红蓝蓝蓝黑 B-红黄蓝 C-红黄白
将所有符合进箱逻辑的链表的表达式算出来去重,算出来结果依旧为355。
具体计算代码请参考方案二代码

注意：相同颜色的球的顺序应该连在一起，否则箱子内的球需要再做一次排序去重。

总结

该文是对排列组合知识的一个补充。如果有更好的解决m个不同颜色的球放到n个箱子中的更好的解法，欢迎留言或者直接联系我。
如果能有算出斗地主有多少种牌型组合的方法，则更希望能联系我。
方案2在箱子不够多,球不够多的情况下,的确是不错的一个计算方案。

参考资料

• C# 用Linq的方式实现组合和笛卡尔积（支持泛型T）
• 终于有个高效率的排列组合算法
• 欢乐斗地主出牌方式统计