序

最近业余时间迷上了数独求解,所以试图用计算机的方式来解答数独。
接下来，我用四宫的数独为例子，示例怎么利用多项式求解数独。

四宫数独

我们以四宫的每个单元格标上序号,如下图所示

因为每行每列每宫都包含1,2,3,4且不重复。
所以第一行满足 x00+x01+x02+x03=10,x00*x01*x02*x03=24。
其余列的关系依次类推,其余宫的关系也是如此。
若数独题目如下图所示

根据坐标和格子的关系可知:
x00=1,x01=4,x14=1,x15=2

通过以下Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

from sympy import *
x00=Symbol('x00')
x01=Symbol('x01')
x02=Symbol('x02')
x03=Symbol('x03')
x04=Symbol('x04')
x05=Symbol('x05')
x06=Symbol('x06')
x07=Symbol('x07')
x08=Symbol('x08')
x09=Symbol('x09')
x10=Symbol('x10')
x11=Symbol('x11')
x12=Symbol('x12')
x13=Symbol('x13')
x14=Symbol('x14')
x15=Symbol('x15')
print(solve([
    # 行之和为10
   x00+x01+x02+x03-10,
   x04+x05+x06+x07-10,
   x08+x09+x10+x11-10,
   x12+x13+x14+x15-10,

   # 行之积为24
   x00*x01*x02*x03-24,
   x04*x05*x06*x07-24,
   x08*x09*x10*x11-24,
   x12*x13*x14*x15-24,

   #列之和为10
   x00+x04+x08+x12-10, 
   x01+x05+x09+x13-10,
   x02+x06+x10+x14-10,
   x03+x07+x11+x15-10,

   #列之积为24
   x00*x04*x08*x12-24,
   x01*x05*x09*x13-24,
   x02*x06*x10*x14-24,
   x03*x07*x11*x15-24,

   #宫之和为10
   x00+x01+x04+x05-10,
   x02+x03+x06+x07-10,
   x08+x09+x12+x13-10,
   x10+x11+x14+x15-10,

   #宫之积为24
   x00*x01*x04*x05-24,
   x02*x03*x06*x07-24,
   x08*x09*x12*x13-24,
   x10*x11*x14*x15-24,

   # x00=1,x01=4,x14=1,x15=2
   x00-1,
   x01-4,
   x14-1,
   x15-2
    ],[x00,x01,x02,x03,x04,x05,x06,x07,x08,x09,x10,x11,x12,x13,x14,x15]))

我们可以快速得知结果是

1
2
3
4

1,4,2,3,
3,2,4,1,
2,1,3,4,
4,3,1,2

其余标准数独(只有唯一解)的四宫数独也可以通过该种方式进行求解。

九宫数独

既然4宫可以用多项式求解？那么九宫是不是也可以这样呢？
答案是可以，但是又有点不同。
∵4+4+4+9=3+4+6+8=21
∵4*4*4*9=3*4*6*8=576
∴ x1+x2+x3+x4+x5+x6+x7+x8+x9=45 和x1*x2*x3*x4*x5*x6*x7*x8*x9=362880
存在{1,2,3,4,5,6,7,8,9}和{1,2,4,4,4,5,7,9,9}两组解。
若我们把8当做-1看待,9当做-2看待
则每行每列每宫之和变成了x1+x2+x3+x4+x5+x6+x7+x8+x9=1+2+3+4+5+6+7+(-1)+(-2)=25
则每行每列每宫之积变成了x1*x2*x3*x4*x5*x6*x7*x8*x9=1*2*3*4*5*6*7*(-1)*(-2)=10080
参考四宫数独中Python代码的实现,可以写出(9行+9列+9宫)*(和表达式1个+积表达式1个)共54个表达式,
若已知提示数为N个,则加上这个N个表达式,则可以借助Python的强大的计算能力实现求解。
再将-1还原成8,-2还原成9,则完成了标准数独的求解。

锯齿数独

众所周知,DLX算法求解数独比回溯法要来得快很多，但是锯齿数独并不适合于用DLX算法(稀疏矩阵精准覆盖算法求解)
因为锯齿数独依旧满足每行每列1到9不重复,只是9个宫中9个来源的坐标有变化了。
若坐标序号如下图所示

以下图第一宫为例：

1
2
3
4

x00+x01+x02+x03+x09+x10+x18+x27+x28-25=0 //每宫之和为25  
x00*x01*x02*x03*x09*x10*x18*x27*x28-10080=0 //每宫之积为10080  
x27-4=0    //x27=4  
x03-(-2)=0 //先用-2代替9  

其他宫的逻辑表达式依次类推,这样就能快速求解锯齿数独了。

推翻九宫结论

如下图有39个提示数的标准数独

对应的python代码如下,仅仅实现了使CPU达到了100%的效果,迟迟出不来结果
所以该种方式求解9宫格的数独要么需要有强悍的电脑，要么还是直接使用DanceLink算法直接求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

from sympy import *
x00= Symbol('x00')
x01= Symbol('x01')
x02= Symbol('x02')
x03= Symbol('x03')
x04= Symbol('x04')
x05= Symbol('x05')
x06= Symbol('x06')
x07= Symbol('x07')
x08= Symbol('x08')
x09= Symbol('x09')
x10= Symbol('x10')
x11= Symbol('x11')
x12= Symbol('x12')
x13= Symbol('x13')
x14= Symbol('x14')
x15= Symbol('x15')
x16= Symbol('x16')
x17= Symbol('x17')
x18= Symbol('x18')
x19= Symbol('x19')
x20= Symbol('x20')
x21= Symbol('x21')
x22= Symbol('x22')
x23= Symbol('x23')
x24= Symbol('x24')
x25= Symbol('x25')
x26= Symbol('x26')
x27= Symbol('x27')
x28= Symbol('x28')
x29= Symbol('x29')
x30= Symbol('x30')
x31= Symbol('x31')
x32= Symbol('x32')
x33= Symbol('x33')
x34= Symbol('x34')
x35= Symbol('x35')
x36= Symbol('x36')
x37= Symbol('x37')
x38= Symbol('x38')
x39= Symbol('x39')
x40= Symbol('x40')
x41= Symbol('x41')
x42= Symbol('x42')
x43= Symbol('x43')
x44= Symbol('x44')
x45= Symbol('x45')
x46= Symbol('x46')
x47= Symbol('x47')
x48= Symbol('x48')
x49= Symbol('x49')
x50= Symbol('x50')
x51= Symbol('x51')
x52= Symbol('x52')
x53= Symbol('x53')
x54= Symbol('x54')
x55= Symbol('x55')
x56= Symbol('x56')
x57= Symbol('x57')
x58= Symbol('x58')
x59= Symbol('x59')
x60= Symbol('x60')
x61= Symbol('x61')
x62= Symbol('x62')
x63= Symbol('x63')
x64= Symbol('x64')
x65= Symbol('x65')
x66= Symbol('x66')
x67= Symbol('x67')
x68= Symbol('x68')
x69= Symbol('x69')
x70= Symbol('x70')
x71= Symbol('x71')
x72= Symbol('x72')
x73= Symbol('x73')
x74= Symbol('x74')
x75= Symbol('x75')
x76= Symbol('x76')
x77= Symbol('x77')
x78= Symbol('x78')
x79= Symbol('x79')
x80= Symbol('x80')
print(solve([
    x00+x01+x02+x03+x04+x05+x06+x07+x08-25,
    x00+x09+x18+x27+x36+x45+x54+x63+x72-25,
    x00+x01+x02+x09+x10+x11+x18+x19+x20-25,
    x00*x01*x02*x03*x04*x05*x06*x07*x08-10080,
    x00*x09*x18*x27*x36*x45*x54*x63*x72-10080,
    x00*x01*x02*x09*x10*x11*x18*x19*x20-10080,
    x09+x10+x11+x12+x13+x14+x15+x16+x17-25,
    x01+x10+x19+x28+x37+x46+x55+x64+x73-25,
    x03+x04+x05+x12+x13+x14+x21+x22+x23-25,
    x09*x10*x11*x12*x13*x14*x15*x16*x17-10080,
    x01*x10*x19*x28*x37*x46*x55*x64*x73-10080,
    x03*x04*x05*x12*x13*x14*x21*x22*x23-10080,
    x18+x19+x20+x21+x22+x23+x24+x25+x26-25,
    x02+x11+x20+x29+x38+x47+x56+x65+x74-25,
    x06+x07+x08+x15+x16+x17+x24+x25+x26-25,
    x18*x19*x20*x21*x22*x23*x24*x25*x26-10080,
    x02*x11*x20*x29*x38*x47*x56*x65*x74-10080,
    x06*x07*x08*x15*x16*x17*x24*x25*x26-10080,
    x27+x28+x29+x30+x31+x32+x33+x34+x35-25,
    x03+x12+x21+x30+x39+x48+x57+x66+x75-25,
    x27+x28+x29+x36+x37+x38+x45+x46+x47-25,
    x27*x28*x29*x30*x31*x32*x33*x34*x35-10080,
    x03*x12*x21*x30*x39*x48*x57*x66*x75-10080,
    x27*x28*x29*x36*x37*x38*x45*x46*x47-10080,
    x36+x37+x38+x39+x40+x41+x42+x43+x44-25,
    x04+x13+x22+x31+x40+x49+x58+x67+x76-25,
    x30+x31+x32+x39+x40+x41+x48+x49+x50-25,
    x36*x37*x38*x39*x40*x41*x42*x43*x44-10080,
    x04*x13*x22*x31*x40*x49*x58*x67*x76-10080,
    x30*x31*x32*x39*x40*x41*x48*x49*x50-10080,
    x45+x46+x47+x48+x49+x50+x51+x52+x53-25,
    x05+x14+x23+x32+x41+x50+x59+x68+x77-25,
    x33+x34+x35+x42+x43+x44+x51+x52+x53-25,
    x45*x46*x47*x48*x49*x50*x51*x52*x53-10080,
    x05*x14*x23*x32*x41*x50*x59*x68*x77-10080,
    x33*x34*x35*x42*x43*x44*x51*x52*x53-10080,
    x54+x55+x56+x57+x58+x59+x60+x61+x62-25,
    x06+x15+x24+x33+x42+x51+x60+x69+x78-25,
    x54+x55+x56+x63+x64+x65+x72+x73+x74-25,
    x54*x55*x56*x57*x58*x59*x60*x61*x62-10080,
    x06*x15*x24*x33*x42*x51*x60*x69*x78-10080,
    x54*x55*x56*x63*x64*x65*x72*x73*x74-10080,
    x63+x64+x65+x66+x67+x68+x69+x70+x71-25,
    x07+x16+x25+x34+x43+x52+x61+x70+x79-25,
    x57+x58+x59+x66+x67+x68+x75+x76+x77-25,
    x63*x64*x65*x66*x67*x68*x69*x70*x71-10080,
    x07*x16*x25*x34*x43*x52*x61*x70*x79-10080,
    x57*x58*x59*x66*x67*x68*x75*x76*x77-10080,
    x72+x73+x74+x75+x76+x77+x78+x79+x80-25,
    x08+x17+x26+x35+x44+x53+x62+x71+x80-25,
    x60+x61+x62+x69+x70+x71+x78+x79+x80-25,
    x72*x73*x74*x75*x76*x77*x78*x79*x80-10080,
    x08*x17*x26*x35*x44*x53*x62*x71*x80-10080,
    x60*x61*x62*x69*x70*x71*x78*x79*x80-10080,
    x00-7,
    x02-5,
    x03-6,
    x06+1,
    x08-4,
    x09-6,
    x10-4,
    x16-2,
    x17-7,
    x18-1,
    x19-2,
    x20+1,
    x21-4,
    x22-7,
    x25-5,
    x26-6,
    x27-2,
    x28-5,
    x29-1,
    x31-6,
    x35+1,
    x45+1,
    x49-5,
    x51-2,
    x52-6,
    x55+1,
    x58-3,
    x61-7,
    x63-5,
    x65-2,
    x66-7,
    x67-4,
    x70+1,
    x71-3,
    x72-3,
    x74-7,
    x75-5,
    x78-4,
    x80-2,
     1-1
],[x00,x01,x02,x03,x04,x05,x06,x07,x08,x09,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20,x21,x22,x23,x24,x25,x26,x27,x28,x29,x30,x31,x32,x33,x34,x35,x36,x37,x38,x39,x40,x41,x42,x43,x44,x45,x46,x47,x48,x49,x50,x51,x52,x53,x54,x55,x56,x57,x58,x59,x60,x61,x62,x63,x64,x65,x66,x67,x68,x69,x70,x71,x72,x73,x74,x75,x76,x77,x78,x79,x80]))

总结

这是我掌握的第三种通过计算机方式求解数独的第三种方式，前面两种分别是回溯法,DLX算法。
这种多项式求解的方法好处在于将数字之间的逻辑用多项式进行表达,将复杂的逻辑运算交由封装好的工具去处理。
稍微麻烦一点的就是书写多项式的表达式，通过数独的相关信息生成py文件再运行py文件,这是后话了。
该部分会在C#调用Python代码中会有详细介绍了(未完成,预计在2019年1月21日之前会补充这部分内容)。

最终总结

所有结论都需要实际验证正确之后，再形成文章，这是对自己的负责，也是对读者的负责。
也希望读者们能够不吝赐教,表示非常感谢！

序

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

数独图形

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

我们可以经由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#源码

序

该文目的是简单记载3*3数独的手写过程,并熟悉一下mathjax工具的运用。

正文

该文的整个过程可以用手写实现，也可以用编程语言实现，该文不对怎么用编程语言实现做详细描述。仅阐述手写的详细过程:

生成行

首先,我们可以手写一行包含19数据行A，不重复即可，顺序不重要,该文以19顺序排列做示例。
\begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \
\end{bmatrix}
然后将数据行A的前三位1,2,3移到数据行A的末尾,生成新的一行数据行B:
\begin{bmatrix}
4 & 5 & 6 & 7 & 8 & 9 &1 & 2 & 3 \
\end{bmatrix}
然后将数据行B的前三位4,5,6移到数据行B的末尾,生成新的一行数据行C:
\begin{bmatrix}
7 & 8 & 9 &1 & 2 & 3 & 4 & 5 & 6 \
\end{bmatrix}

生成块

再将数据行依次组合，生成一个3行9列的数据块 $X_1$
\begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \
\end{bmatrix}
将数据块$X_1$的第一列
\begin{bmatrix}
1 \
4 \
7 \
\end{bmatrix}
移到最后一列生成新的数据块$X_2$
\begin{bmatrix}
2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 1\
5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4\
8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7\
\end{bmatrix}
再将数据块$X_2$的第一列
\begin{bmatrix}
2 \
5 \
8 \
\end{bmatrix}
移到最后一列生成新的数据块$X_3$
\begin{bmatrix}
3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2\
6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5\
9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\
\end{bmatrix}
再将数据块$X_1$,$X_2$,$X_3$依次组合,就形成了如下图所示的数独$Y_1$。
\begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \
2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 \
5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 \
8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \
3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 \
6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 \
9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \
\end{bmatrix}
所以说手写数独是很简单的，那怎么样让别人看不出来这是一个手写的?

行交换

可以将 **[1,2,3]**行中两两任意互换;
可以将 **[4,5,6]**行中两两任意互换;
可以将 **[7,8,9]**行中两两任意互换;
第一行和第三行交换用 $1\Leftrightarrow3$ 表示。
依次执行$1\Leftrightarrow3$ ，$4\Leftrightarrow5$ 和 $8\Leftrightarrow9$
生成新的数独$Y_2$。如下:
\begin{bmatrix}
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \
5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 \
2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 \
8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \
3 & 4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 \
9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \
6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 \
\end{bmatrix}

列交换

可以将 **[1,2,3]**列中两两任意互换;
可以将 **[4,5,6]**列中两两任意互换;
可以将 **[7,8,9]**列中两两任意互换;
第一列和第三列交换用 $1\Longleftrightarrow3$ 表示。
依次对$Y_2$执行$1\Longleftrightarrow3$ ，$4\Longleftrightarrow5$ 和 $8\Longleftrightarrow9$
生成新的数独$Y_3$。如下:
\begin{bmatrix}
6 & 5 & 4 & 8 & 7 & 9 & 1 & 3 & 2 \
9 & 8 & 7 & 2 & 1 & 3 & 4 & 6 & 5 \
3 & 2 & 1 & 5 & 4 & 6 & 7 & 9 & 8 \
7 & 6 & 5 & 9 & 8 & 1 & 2 & 4 & 3 \
4 & 3 & 2 & 6 & 5 & 7 & 8 & 1 & 9 \
1 & 9 & 8 & 3 & 2 & 4 & 5 & 7 & 6 \
5 & 4 & 3 & 7 & 6 & 8 & 9 & 2 & 1 \
2 & 1 & 9 & 4 & 3 & 5 & 6 & 8 & 7 \
8 & 7 & 6 & 1 & 9 & 2 & 3 & 5 & 4 \
\end{bmatrix}

数值交换

将数独$Y_3$中的数字任意两个数字互换局组成了新的数独,如数独$Y_3$的2和7互换，就生成了新的数独$Y_4$
\begin{bmatrix}
6 & 5 & 4 & 8 & 2 & 9 & 1 & 3 & 7 \
9 & 8 & 2 & 7 & 1 & 3 & 4 & 6 & 5 \
3 & 7 & 1 & 5 & 4 & 6 & 2 & 9 & 8 \
2 & 6 & 5 & 9 & 8 & 1 & 7 & 4 & 3 \
4 & 3 & 7 & 6 & 5 & 2 & 8 & 1 & 9 \
1 & 9 & 8 & 3 & 7 & 4 & 5 & 2 & 6 \
5 & 4 & 3 & 2 & 6 & 8 & 9 & 7 & 1 \
7 & 1 & 9 & 4 & 3 & 5 & 6 & 8 & 2 \
8 & 2 & 6 & 1 & 9 & 7 & 3 & 5 & 4 \
\end{bmatrix}

行交换，列交换，数值交换次数越多,就越来越没有手写的痕迹。掌握了数独的一个相关规律,手写数独就再是遥不可及的事情。

总结

该文简单地介绍了手写数独的过程,希望那些对数独感兴趣的人读了这篇文章后有所收获。

参考资料

• 如何在hexo中支持Mathjax