一种基于稀疏优化的数独求解新方法

• 作者: 吴乐南 张煜东 王水花 霍元恺
• 来源期刊: 南京信息工程大学学报
• 学科: 数学
• 关键词: 数独 约束规划 整数规划 线性规划 主对偶内点法
• 年，卷（期）: 2011,（1）
• 页码范围: 23-27
• 分类号: O29
• 字数: 2804字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-7070.2011.01.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴乐南	东南大学信息科学与工程学院	412	3936	29.0	45.0
2	张煜东	东南大学信息科学与工程学院	47	664	11.0	24.0
3	王水花	东南大学信息科学与工程学院	24	417	7.0	20.0
4	霍元恺	东南大学信息科学与工程学院	1	4	1.0	1.0