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