基于区域序列枚举法的蜂巢数独求解算法研究-计算机工程与应用.PDF

36 2014 ，50（23 ） Computer Engineering and Applications 计算机工程与应用 ⦾理论研究、研发设计⦾ 基于区域序列枚举法的蜂巢数独求解算法研究 肖华勇，杨菲菲，黄奔茹 XIAO Huayong, YANG Feifei, HUANG Benru 西北工业大学 理学院 数学系，西安 710129 Department of Mathematics, School of Science, Northwestern Polytechnical University, Xi ’an 710129, China XIAO Huayong, YANG Feifei, HUANG Benru. Equation model for honeycomb sudoku based on regional sequence enumeration method. Computer Engineering and Applications, 2014, 50 （23 ）：36-40. Abstract ：Honeycomb sudoku is a kind of deformation of sudoku which is similar to the honeycomb and difficult to solve. Section 1 of the full paper presents the linear programming equation set equivalent with the honeycomb sudoku puzzle. Section 2, the properties of the solution algorithm of honeycomb sudoku are derived from the equation set, such as the property of removing the candidate numbers, the contradictoriness, the unique certainty and the invariance of enumera- tion. Section 3 solves the honeycomb sudoku with a regional sequence enumeration method, and the difference of solving algorithm between the honeycomb sudoku and standard sudoku is compared. The proposed algorithm is proved effective for the honeycomb sudoku of medium level by examples. Key words ：honeycomb sudoku; deformation of sudoku; equation set; regional sequence enumeration method 摘 要：蜂巢数独是类似蜂巢难度又高的变形数独，它有着重要的研究意义。由蜂巢数独谜题提出与之等价的线性 规划方程组；从方程组出发推导出求解数独算法的性质，如候选数删除性质、矛盾性质、唯一确定性质、枚举不变性 质；基于以上性质，提出用区域序列枚举方法求解蜂巢数独。结合实例计算，提出的算法对中度难度级别的蜂巢数 独是有效的。 关键词：蜂巢数独；变形数独；方程组；区域序列枚举 文献标志码：A 中图分类号：O 157 doi ：10.3778/j.issn. 1002-8331.1305-0513 1 引言 类似蜂巢，所以称为蜂巢数独。如图1所示，蜂巢数独 数独（Sudoku）是一种基于逻辑推理的数学谜题，是 有行，没有列和九宫格，但有正斜线、反斜线。它要求每 18世纪末由瑞士数学家欧拉发明的，后在美国发展，并 行、正斜线、反斜线所填数字不能重复，且每行、正斜线、 在日本得以发扬光大。数独的玩法逻辑上非常简单，但 反斜线所填数字序列是连续数列（例如 1~6 ，3~8 ，4~ 数字排列方式千变万化。谜题中会预先填入若干数字