摘 要：数独益智游戏（Sudoku）是近年来全球流行的一种智力游戏。本文通过分析数据结构、“非循环判断”预处理算法和回溯算法，深入探讨了数独问题的解决方案，并给出了该方案的实现算法，实验证明该算法是正确高效的。

关键词：数独；非循环判断；算法；回溯法

中图分类号：TP302

“数独”益智游戏（Sudoku）是瑞士数学家欧拉发明的，目前在国内外非常流行。游戏在9*9的单元表格中进行，单元表格不仅被分为9行、9列，也被分为3*3个九宫格。单元表格中已存在若干数字，其余为空格。游戏规则要求玩家在每个空格中填入1～9之间的数字，使每个数字在每行、每列、每个九宫格仅出现一次。国内许多论文对数独游戏的教学意义做了深入讨论，但研究其求解算法的论文不多[1]，用计算机进行快速求解的算法更少，参考文献[2]使用“有限递推”预处理提高了算法的执行速度，但其本身每次都要处理候选数字也耗时不少；参考文献[3]提出了效率较高的算法，但其冲突检测还可提高效率。本文对“数独”游戏进行深入研究后用C语言设计出一种基于“非循环判断”预处理的回溯算法，然后用参考文献[2]中的三个实例及号称世界上迄今难度最大的数独游戏[4]（芬兰数学家因卡拉花费3个月时间设计的）进行测试，实践证明该算法正确且高效。

1 数据结构与回溯法简介

1.1 数据结构

精心设计的数据结构可让算法更加高效[5]。主要的数据结构是5个整型数组，其中2个一维数组，3个二维数组：

（1）int aResult [81]，该数组的用途是接收题目（空白处则初始值为0）以及保存最终结果（所有的9*9个数字按序存储在该数组中）；……