用多项式解标准数独或锯齿数独

序

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

四宫数独

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

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

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

通过以下Python代码

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,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个来源的坐标有变化了。
若坐标序号如下图所示

以下图第一宫为例：

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算法直接求解。

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日之前会补充这部分内容)。

最终总结

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