_数独_游戏的算法研究与实现 (免费).pdf

ISSN1009-3044 电脑知识与技术 ComputerKnowledgeAndTechnology Vol.3,No.8,September2008,pp.1715-1717 “数独”游戏的算法研究与实现 李盘荣 (无锡市广播电视大学,江苏无锡 ) 214011 摘要:“数独”游戏是一种在全球范围内流行的数字拼图游戏。该文通过数据结构分析,提出了一种基于有序回溯的解决数独游戏的 算法并最终通过C语言编程实现了计算机解,实例数据表明程序非常高效。 关键词:数独;数据结构;算法;回溯 中图分类号: 文献标识码: 文章编号: TP312 A 1009-3044(2008)26-1715-03 TheResearchandImplementationoftheAlgorithmaboutSudoku LIPan-rong (WuxiRadioTVUniversity,Wuxi214011,China) Keywords:sudoku;datastructure;algorithm;backtracking 1引言 “数独”( )起源于瑞士,由十八世纪的瑞士数学家欧拉发明,于 年代由美国的一家数学逻辑游戏杂志首先发表,当 Sudoku 1970 时名为 ,于 年取名“数独”, 年 月 日“数独”游戏登上《泰晤士报》的版面,很快“数独”游戏就成为在世 NumberPlace1984 200411 12 界范围内流行的数字拼图游戏。如图 所示,拼图由一个 的九宫格组成,每个格子又分成一个小九宫格,共九九八十一个小格 1 3x3 子。游戏规则:游戏开始前会有一些格子上写好了 的数,在剩下的格子里填 的数,直到把所有格子填满,要求,任何一行或 1-9 1-9 [1] 一列或者任一个小九宫中没有相同的数字 。 图1 数独游戏示例图 本文就是试图通过数据结构分析和算法研究,利用计算机程序来快速完成数独游戏。 2简单分析 数独号称是数学问题,但几乎用不上数学运算方法,事实上,它是一个思维方式。由于某个格子填入数据时有可能要对原来已 填入的数据进行修正,程序可以考虑使用回溯法解决问题,实践证明,回溯法解决数独游戏问题,有着极快的效果。 解决问题的宏观考虑: 从界面或文本读取数独游戏数据; 判断题目合法性;(即验证给出数据本身是否符合游戏规则,行、列以及小九宫中不重复地出现数字 ); 1-9 逐个取得空白处; 有序递推,若可以填入数字则填入数字,并入栈以便回溯;否则回溯至前面填入数字处重新填数; 直到所有空白处填满数据; 输出结果至屏幕和文件。 如此一来需要细化的就是如何进行有序递推,填入数字或者通过回溯重新填入数字最终得到解,这个也就是本算法的核心,解 题的关键。 3数据结构与相关函数 [2] 数据结构 是计算机存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率的算法。一般 认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在 计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示。数独从形式上看是一个方阵,最适合用二维数组 收稿日期: 2008-05-04 作者简介:李盘荣( ),男,江苏无锡人,讲师,工程硕士,研究方向:智能计算,网络控制。 1971- 本栏目责任编辑:谢媛媛 软件设计开发 1715