基于区域序列枚举法的蜂巢数独求解算法研究.pdfVIP

36 2014，50(23) ComputerEngineeringandApplications$[算机工程与应用 @理论研 究、研发设计@ 基于区域序列枚举法的蜂巢数独求解算法研究 肖华勇，杨菲菲，黄奔茹 XIAO Huayong，YANG Feifei，HUANG Benru 西北工业大学 理学院 数学系，西安 710129 DepartmentofM athematics，SchoolofScience，NorthwesternPolytechnicalUniversity,Xi’an710129，China XIAO Huayong，YANG Feifei，HUANG Benru．Equationmodelforhoneycombsudokubasedonregionalsequence enumerationmethod．ComputerEngineeringandApplications，2014，50(23)：36—40． Abstract：Honeycomb sudoku lSakindofdeformationofsudokuwhich 1Ssimilartothehoneycombanddifficultto solve．Section 1ofthefullpaperpresentsthelinearprogrammingequationsetequivalentwiththehoneycomb sudokupuzzle． Section2，thepropertiesofthesolutionalgorithm ofhoneycomb sudokuarederivedfrom theequation set，suchasthe propertyofremovingthecandidatenumbers，thecontradictoriness，theuniquecertaintyandtheinvarianceofenumera— tion．Section3solvesthehoneycomb sudokuwitharegionalsequenceenumerationmethod，andthedifferenceofsolving algorithm betweenthehoneycombsudokuandstandardsudoku iscompared．Theproposedalgorithm isprovedeffective forthehoneycombsudokuofmedium levelbyexamples． Keywords：honeycombsudoku；deformationofsudoku；equationset；regionalsequenceenumerationmethod 摘 要：蜂巢数独是类似蜂巢难度又高的变形数独，它有着重要的研究意义。由蜂巢数独谜题提 出与之等价的线性 规划方程组；从方程组出发推导 出求解数独算法的性质，如候选数删除性质、矛盾性质、唯一确定性质、枚举不变性 质；基于以上性质，提出用区域序列枚举方法求解蜂巢数独。结合 实例计算，提 出的算法对中度难度级别的蜂巢数 独是有效的。 关键词：蜂巢数独；变形数独；方程组；区域序列枚举 文献标志码 ：A 中图分类号：O157 doi：10．3778／j．issn．1002．8331．1305—0513 1 引言 类似蜂巢 ，所 以称为蜂巢数独。如图1所示 ，蜂巢数独 数独 (Sudoku)是一种基于逻辑推理的数学谜题，是 有行，没有列和九官格 ，但有正斜线 、反斜线。它要求每 18世纪末由瑞士数学家欧拉发明的，后在美国发展，并 行 、正斜线 、反斜线所填数字不能重复，且每行、正斜线、 在 日本得以发扬光大。数独的玩法逻辑上非常简单 ，但 反斜线所填数字序列是连续数列 (例如 1-6，3-8，4～ 数字排列方式千变万化 。谜题中会预先填入若干数字 ， 9，…)。除了中问的行、正斜线、反斜线所填数字是 1-9， 其他官格为空白，玩家需要根据谜题中的数字分布状 其他行 、正斜线 、反斜线所填数字不一定是从 1开始 ，也 况 ，逻辑推敲出剩余的空格所需数字。随着对数独研究 就是说其他行 、正斜线、反斜线所填数字不一定包括 1-9 的深入，出现了越来越多的变形，数