南京信息工程大学学报2011，Vol.3Issue(1)：23-27,5.
一种基于稀疏优化的数独求解新方法
A novel sudoku solving method based on sparse optimization
摘要
Abstract
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 L0-norm to guarantee the sparsity of the solution.Moreover,the L1-norm was used to approximate the L0-norm on the basis of RIP and KGG condition.Finally,the slack vectors were introduced to transfer the L1-norm into a convex linear programming problem, which was solved by the primal-dual interior point method.Experiments demonstrate that this algorithm reach 100％ success rate on easy,medium, difficult, and evil levels, and reach 86.4％ success rate on only 17-clue 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 programning and Sinkhorn algorithm in terms of success rate and computation time.关键词
数独/约束规划/整数规划/线性规划/主对偶内点法Key words
sudoku/ constraint programming/ integer programming /linear programming/ primal-dual interior point method分类
数理科学引用本文复制引用
张煜东,王水花,霍元恺,吴乐南..一种基于稀疏优化的数独求解新方法[J].南京信息工程大学学报,2011,3(1):23-27,5.基金项目
资助项目国家自然科学基金(60872075) （60872075）
