一种基于稀疏优化的数独求解新方法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(60872075)"


A novel sudoku solving method based on sparse optimization
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    为了更好地求解数独问题,提出一种新的求解方法:采用实数编码去除整数约束,同时采用0范数作为目标函数来保证解的稀疏性.在此基础上,根据RIP(Restricted Isometry Property)与KGG(Kashin Garnaev Gluskin)条件,用1范数近似0范数.最后引入松弛矢量,使1范数转换为一个凸线性规划问题.采用主对偶内点法求解该线性规划问题.实验表明:该方法对简单、中等、困难、恶魔级别的数独,可达到100%成功率;对最小提示数目的17数独,达到864%的成功率.另外,该算法耗时短,且与数独的难度无关.因此,该算法在成功率与运行时间上均优于约束规划与Sinkhorn算法

    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 L0norm to guarantee the sparsity of the solution.Moreover,the L1norm was used to approximate the L0norm on the basis of RIP and KGG condition.Finally,the slack vectors were introduced to transfer the L1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 programming and Sinkhorn algorithm in terms of success rate and computation time.

    参考文献
    相似文献
    引证文献
引用本文

张煜东 王水花 霍元恺 吴乐南.一种基于稀疏优化的数独求解新方法[J].南京信息工程大学学报,2011,(1):23~27

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-07-20
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:

地址:江苏南京,宁六路219号,南京信息工程大学    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn    QQ交流群号:344646895

南京信息工程大学学报 ® 2021 版权所有  技术支持:北京勤云科技发展有限公司