稀疏优化算法求解

稀疏优化算法求解数独什么是数独数独（Sudoku，也叫九宫格，如下图）是一种数字游戏，在格的大九宫格中有9个格的小九宫格，并提供一定数量的数字。根据这些数字，利用逻辑和推理，在其它的空格上填入1到9的数字。每个数字在每个小九宫格内只能出现一次，每个数字在每行、每列也只能出现一次。传统数独求解算法关于数独的求解方法有暴力破解法、约束规划、比较排除法等，比较排除法是一系列直观的求解方法。（能否更加具体点说明比较排除法）暴力破解（Brute-Force）法，缺陷就是需要大量的时间和内存；而约束规划是通过设置一个目标函数与约束函数，采用分支定界法求解，由于它本质上为一个NP-C问题，所以需要的时间较多，而且对初值的选取很敏感，相对约束规划求解方法的一种改进方法是采用随机搜索或智能优化，随机生成解，然后计算误差，通过不断迭代使得误差为0，这种方法比前面的稍快，但同样需要大量的时间，而且性能不稳定。基于稀疏优化算法的数独求解基本思想是通过将数独的填字数字1-9映射为只含有0和1的向量，对数独所要满足的求解条件，建立相应的线性方程。这时，数独的求解问题就转化为求解线性方程的最大稀疏解问题，即所谓的0-范数问题。0-范数问题由于近年来压缩感知理论的盛行，得到极大的关注。•基本思想和原理给出一个数独，假设解为x，则依据数独的约束条件可得一约束规划问题：(1)其中row，col，box分别表示每行、每列、每个小九宫格只出现一次数字1-9。min1()1,2,,9,()1,2,,9,.()1,2,,9,(),1,2,,9,iiiiiijrowxcolxstboxxCluexCluex•实数编码由于问题（1）也是一个整数规划问题，求解困难，因此采用一种编码方法，将x放宽到实数域，然后去除整数约束。所要的编码方法，将原来的整数编码中的每一个ijx用9个0-1之间的实数ijkx（k=1,2，，9）表示，它们之间的转换关系如下：(),ijijxIxk（2）(max()).ijijkijkkxkxx（3）上述式中I（）是指示函数，等式成立时为1，不成立是为0.图2实数编码•约束条件依据上述的实数编码方法去除整数约束，同时转换成为一个线性方程组。下面我们分别描述行、列等所要满足的约束条件。•行约束条件第1行可以写为：999999964891901IIIx第2行可以写为：9819999999567919001IIIx•列约束条件第1列可以写为：9997299972919001IIx•第2列可以写为：9999963999996391900001IIx•小九宫格约束条件（以左上角的小九宫格开始编号，编号为1，第一行小九宫格从左到右编号，再到第二行小九宫格，再到第三行小九宫格，右下角的小九宫格编号为9）9999999549999999549999999540910001IIIIIIIIIx•第2个小九宫格：•第3个小九宫格：9279999999279279999999279279999999513910000001IIIIIIIIIx95499999995499999995499999994869100001IIIIIIIIIx•填充约束条件（每一个格子中的数必须是1-9之间的数，以第一行第一列的格子为列）972011001x•提示数字约束条件依据已经给出的提出数字可以得出相应的约束条件：第1行，第3列的提示数字8：1870200000000010001x•第1行，第4列的提示数字3：2769900001001x则第i行，第j列的提示数字n（,,1,2,,9ijn）：设m=81(i-1)+9(j-1)+n-1720001001mmx•因此所有的约束条件转换成一个线性方程组简单的可以表示为：其中在约束条件中可以让x在实数范围内取值，而且依照上述所表达的式子中可以知道此约束是线性的。这时矩阵的行数为324+，表示已知数独提示的数字数目，而的维数为729，因此上述方程显然是一个欠定方程组。eq.eqAxb•稀疏优化Mins.t.0x.eqeqAxbijx0ijx1000000000.50.5000000000.50.40.1000000000.50.30.10.1000000000.50.20.10.10.10000000012345已知提示数目34芬兰数学家设计的世界“最难”数独。•作业:1.编程得到关于数独求解的线性方程组2.将问题1的数独形式推广到任意阶的情形,如16*16,25*25等.