肖华勇，杨菲菲，黄奔茹

西北工业大学 理学院 数学系，西安 710129

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

肖华勇，杨菲菲，黄奔茹

西北工业大学 理学院 数学系，西安 710129

1 引言

数独（Sudoku）是一种基于逻辑推理的数学谜题，是18世纪末由瑞士数学家欧拉发明的，后在美国发展，并在日本得以发扬光大。数独的玩法逻辑上非常简单，但数字排列方式千变万化。谜题中会预先填入若干数字，其他宫格为空白，玩家需要根据谜题中的数字分布状况，逻辑推敲出剩余的空格所需数字。随着对数独研究的深入，出现了越来越多的变形，数独形状变化（蜂巢数独、环状数独等）和引入和式计算（Killer数独、Kakuro数独等）等[1]。

蜂巢数独是标准数独形状发生变化的数独，其外形类似蜂巢，所以称为蜂巢数独。如图1所示，蜂巢数独有行，没有列和九宫格，但有正斜线、反斜线。它要求每行、正斜线、反斜线所填数字不能重复，且每行、正斜线、反斜线所填数字序列是连续数列（例如 1～6，3～8，4～9，…）。除了中间的行、正斜线、反斜线所填数字是1～9，其他行、正斜线、反斜线所填数字不一定是从1开始，也就是说其他行、正斜线、反斜线所填数字不一定包括1～9这9个数字。由于蜂巢数独并没有九宫，最特殊的是蜂巢连线（行、正斜线、反斜线）数字序并不固定，所以不能完全沿用传统数独解题技法。

国内外学者针对数独求解方面展开了大量研究，他们把数独问题转化成不同的数学模型。A.C.Bartlett等[2-3]针对对角线数独、金字塔数独等特殊形式的数独建立了0-1整数规划模型，并运用Matlab中的优化函数求得模型的解。……