| 一种基于稀疏优化的数独求解新方法 |
| 投稿时间：2010-07-20 点此下载全文 |
| 引用本文：张煜东 王水花 霍元恺 吴乐南.一种基于稀疏优化的数独求解新方法[J].南京信息工程大学学报,2011,(1):23~27 |
| 摘要点击次数: 3016 |
| 全文下载次数: 1948 |
|
| 基金项目:国家自然科学基金(60872075)" |
|
| 中文摘要:为了更好地求解数独问题,提出一种新的求解方法:采用实数编码去除整数约束,同时采用0范数作为目标函数来保证解的稀疏性．在此基础上,根据RIP（Restricted Isometry Property）与KGG(Kashin Garnaev Gluskin)条件,用1范数近似0范数．最后引入松弛矢量,使1范数转换为一个凸线性规划问题．采用主对偶内点法求解该线性规划问题．实验表明：该方法对简单、中等、困难、恶魔级别的数独,可达到100％成功率;对最小提示数目的17数独,达到864％的成功率．另外,该算法耗时短,且与数独的难度无关．因此,该算法在成功率与运行时间上均优于约束规划与Sinkhorn算法 |
| 中文关键词:数独 约束规划 整数规划 线性规划 主对偶内点法 |
| |
| 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 real number 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 864％ 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 programming and Sinkhorn algorithm in terms of success rate and computation time. |
| keywords:sudoku constraint programming integer programming linear programming primal dual interior point metho |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
