数独求解的候选数优化算法设计

摘要

从数独的候选数集合特性出发,通过分析数独游戏的要求,针对标准数独,提出了四条优化规则.避免了计算机回溯法的完全枚举,得到候选数优化回溯法,减少了搜索次数,提高了求解的速度.并且针对3×3的数独,分别给出显性候选数规则跟隐形候选数规则的两个特例,得到了3×3数独的相应的6条优化准则.用两个数独难题进行验证,可知本算法相对于回溯法,节省了三分之一的时间,证明了所提算法的有效性.%A new method is proposd to solve standard sudoku based on the properties of Sudoku. This method is given by four optimal properties of Sudoku , which come from the characteristics of the candidate set. Using this method, calculation speed has been improved because the backtrack is avoided. Then, the 3×3 sudouku is taken as a example. Six optimal properties are given as the special cases of the four optimal properties mentioned above. At last, two sudoku puzzles are demonstated and solved by using the mehod. According to the result,this algorithm saves can be see more than one-third of the time than backtracking algorithm. That shows the method is very effect.