1674-7070
2011
1
23
27
article
一种基于稀疏优化的数独求解新方法
A novel sudoku solving method based on sparse optimization
为了更好地求解数独问题,提出一种新的求解方法:采用实数编码去除整数约束,同时采用0范数作为目标函数来保证解的稀疏性．在此基础上,根据RIP（Restricted Isometry Property）与KGG(Kashin Garnaev Gluskin)条件,用1范数近似0范数．最后引入松弛矢量,使1范数转换为一个凸线性规划问题．采用主对偶内点法求解该线性规划问题．实验表明：该方法对简单、中等、困难、恶魔级别的数独,可达到100％成功率;对最小提示数目的17数独,达到864％的成功率．另外,该算法耗时短,且与数独的难度无关．因此,该算法在成功率与运行时间上均优于约束规划与Sinkhorn算法
In order to solve the sudoku more efficiently,a novel approach was proposed.We employed the realnumber coding to get rid of the integer constraint,meanwhile used the L0norm to guarantee the sparsity of the solution.Moreover,the L1norm was used to approximate the L0norm on the basis of RIP and KGG condition.Finally,the slack vectors were introduced to transfer the L1norm into a convex linear programming problem,which was solved by the primaldual interior point method.Experiments demonstrate that this algorithm reach 100％ success rate on easy,medium,difficult,and evil levels,and reach 864％ success rate on only 17clue sudokus.Besides,the average computation time is quite short,and has nothing to do with the difficulty of sudoku itself.In all,this algorithm is superior to both constraint programming and Sinkhorn algorithm in terms of success rate and computation time.
数独;约束规划;整数规划;线性规划;主对偶内点法
sudoku;constraint programming;integer programming;linear programming;primaldual interior point metho
张煜东 王水花 霍元恺 吴乐南
ZHANGYudong, WANG Shuihua,HUO Yuankai,WU Lenan
njqxxyxb/article/abstract/20110102