数独问题求解算法的研究与实现

李祥琴

（荆楚理工学院计算机工程学院，湖北荆门448000）

数独问题求解算法的研究与实现

李祥琴

（荆楚理工学院计算机工程学院，湖北荆门448000）

数独是当前流行的一种填字游戏。本文介绍了几种常用的数独求解方法，并通过具体实例，探讨了数独问题的求解方案，最后使用C#语言编程实现。结果证明，该方案运行效率高，结果易于理解。

数独；初盘；候选数；回溯法

1 引言

数独（Sudoku）是一种运用纸、笔进行演算的逻辑智力游戏，起源于瑞士数学家欧拉等人研究的拉丁方阵（Latin Square），目前风靡全球。随着数独爱好者日益增多，数独也出现了许多变形，比如迷你数独、对角线数独，其规则种类数不胜数。

数独由方格、行、列、宫等元素组成，是将一个较大的正方形均分成9行9列，形成81个方格，也称九宫格，每个方格都是一个小正方形，水平方向的三横行与垂直方向的三纵列相交之处有9个方格，构成一个小九宫，称为宫。数独的游戏规则是：在方格中填入1到9的数字，并满足每一行只能填充1～9的数字，且不能重复；每一列只能填充1～9的数字，且不能重复；在每3×3的方格中填充1～9的数字，且不能重复。

2 数独的求解方法

数独在游戏开始时的状态称为初盘，包括数字和空格，游戏结束时的状态称为终盘，只包含数字[1]。每个数独初盘可得到一个或多个终盘，由于数独中的数字排列有各种组合，因而每个数独终盘又可以演变出无数个数独初盘。

数独中的数字千变万化，解法也随之灵活各样，主要有摒除法、余数法、隐含唯一数法、数对法和回溯法[2-4]。

（1）摒除法

在每行、每列以及小九宫中，每个数字只能出现一次，若某一行已经出现了一个数字8，该行其它方格候选数就不能填数字8。

（2）余数法

如果按行、列以及小九宫数字不可重复的规则依次给出候选数，若出现某个方格只含有一个候选数，那么这个方格必然填这个数字。比如，某一方格受其它20格的影响，假如这20格里面已经出现了1～5、7～9这8个数字，那么没有出现的唯一数字就是6。

（3）隐含唯一数法

如果按行、列以及小九宫数字不可重复的规则依次给出候选数，若在某一行、某一列或某个小九宫中有一个候选数只出现在某一个方格里，而其它方格都没有这个候选数，那么这个方格必然填这个数字。

（4）数对法

如果出现某一行、某一列或某个小九宫中有两个方格只使用了两个候选数，那么这两个方格必然会是这两个数字。

（5）回溯法

在一些复杂的问题中，若使用摒除法、余数法、数对法后仍然无法继续下去，这时可以采用回溯法。比如某个方格只有两个候选数1和8，但不知道选择候选数1还是8。可先选择其中一个候选数填入，然后往下判定其它的空格，若出现冲突现象，则代表前面的假设是错误的，可选择另一个候选数填入，再往下逐步求解。

3 计算机编程实现

下面以Visual Studio 2010为集成环境，通过C#语言编程求解数独问题。数独初盘如表1所示。

表1 数独初盘

3.1 数据结构和算法设计

定义一个类suduArray，其中创建函数inputarray()、outputarray()、isRepeat(int i,int j)和dfs(int count)，在Program类中执行main函数。

（1）数组array和函数inputarray()，用于键盘输入数据并存放于数组。

（2）函数outputarray()，用于输出结果。

（3）函数isRepeat(int i,int j)，用于判断行、列以及小九宫是否有重复的数字。

（4）函数dfs(int count)，对数独九宫格使用回溯法进行检索。

判断是否已到达最后一个方格，若是则返回；若不是，则判断当前方格是否需要填数字，如果不需要填，则跳到下一个方格，如果需要填，则对当前方格尝试所有解。若有解则继续下一个，无解则回溯。

（5）Main主函数，调用suduArray类中定义的函数进行求解。

3.2 结果测试

本实验是在win7操作系统下，利用Microsoft Visual Studio 2010软件集成开发工具编程实现。在Visual C#中创建一个控制台应用程序，运行时通过键盘输入表1所示的初始值，最后得到5组数据，结果如表2所示。从结果可以看出此数独初盘的终盘数量有5个。

测试过程中，为了计算出得到终盘所耗费的时间，在主函数中建立了一个Stopwatch类的对象watch1，通过调用该对象的Start函数、Stop函数和ElapsedMilliseconds属性，可得到求解九宫格的时间。由于计算机运算速度快，通过编程解决这类数独问题时，一般可在几秒或更短的时间内得到结果。

4 结束语

数独的游戏规则简单，它具有较强的趣味性和挑战性，能增进和锻炼人的推理和逻辑思维能力，但随着难度的增大，带来的挑战也越强。相对于人手求解法，使用计算机求解的研究更具有现实意义。本文探讨了解决数独问题的各种方法，并通过计算机编程进行求解，最后得出实验结果，可以看出本方案对解决这类数独问题是非常有效的。

表2 实验结果

[1] 曲海平，岳峻，王飞．数独问题的生成与求解算法的研究[J]．科技通报，2017，33(6)：14-17．

[2] 黄皓．数独问题的一种简单解法[J]．电脑知识与技术，2014，10(22)：5340-5344．

[3] 雷蕾，沈富可．关于数独问题的算法的设计与实现[J]．电脑知识与技术，2007(2)：481-523．

[4] 吴涛．基于排除法填充模型的数独求解算法[J]．西安航空学院学报，2014，32(3)：77-79．

The Study and Implementation of the Algorithm of Sudoku Problem

Li Xiangqin
（Jingchu University of Technology,Jingmen 448000,Hubei）

Sudoku is a kind of popular crossword puzzle.This paper introduces several commonly used methods of solving Sudoku problem.The solution of Sudoku problem is discussed through concrete examples.Finally,it is realized by C#language.The result shows that the scheme is running with high efficiency,and is easy to understand.

Sudoku;original layout;candidate numbers;backtrack

TP312

A

1008-6609(2017)09-0077-03

李祥琴（1979-），女，湖北荆门人，硕士，讲师，研究方向为数据库技术、数据挖掘、软件工程。