钱丽丹
摘 要： 以数独游戏为切入点研究IOS平台下的游戏开发技术。介绍了数独游戏的起源与游戏规则，对系统进行功能模块划分，介绍了系统使用到的关键技术如Cocos2D游戏框架、舞蹈链算法等，给出了系统运行界面。该游戏可以在任何IOS移动终端上运行，界面美观，性能稳定。
关键词： IOS； 数独游戏； Cocos2D游戏框架； 舞蹈链算法
中图分类号：TP311 文献标志码：A 文章编号：1006-8228（2016）04-58-03
Development of Sudoku game for IOS
Qian Lidan
（Department of Information & Technology， ZheJiang Economic & Trade Polytechnic， Hangzhou， Zhejiang 310018， China）
Abstract： Taking Sudoku game as an entry point， the game development technology on IOS platform is studied. The origin and the play rules of the game are introduced in this paper， the system function module is divided and some key technologies such as Cocos2D， Dancing Links algorithm etc. are introduced， and the system operation interface are given. The game can be run on any IOS mobile terminal， with beautiful interface and stable performance.
Key words： IOS； Sudoku game； Cocos2D game framework； Dancing Links algorithm
0 引言
伴随着智能手机普及和4G网络的发展，中国的手机游戏市场得到了迅猛发展，尤其近四年以来发展更为迅速。在2011年整个中国手机游戏手场收入不过62.4亿元，但是在2015年则达到了416亿[1]。2014年手机游戏销售收入首次超越网页游戏，手机游戏成为了网络游戏的主力军。
IOS作为主流的开发平台，与Android相比，IOS平台硬件统一，这使得程序开发人员需要考虑的兼容性问题变得相对容易，维护及修复成本也较低。IOS游戏开发收入是Android游戏开发收入的6倍，IOS已经成为了手机游戏开发的首选平台。本文以数独游戏为切入点，研究IOS平台下的游戏开发技术。
1 数独游戏分析与设计
1.1 游戏介绍
数独[2]最早起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵，经历了一系列的演变，从早期的“拉丁方块”、“数字拼图”到现在的“数独”，游戏规则逐步确定。正式的数独游戏最早出现在20世纪70年代的美国，后来逐渐被介绍到日本、英国、中国等，在全球范围内确立了谜题领域的世界地位。
数独盘面是个九宫，每一宫又分为九个小格，在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字，使1-9每个数字在每一行、每一列和每一宫中都只出现一次。这游戏全面考验玩家观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，使得数独成为了训练头脑的绝佳方式。
1.2 系统功能模块划分
游戏共分为8个功能模块：游戏主体模块、解题器模块、谜题自动生成器模块、关卡编辑器模块、游戏菜单模块、关于游戏模块、背景音效模块和游戏分享模块。系统功能模块划分如图1所示。
[数独游戏][谜题自动生成器][游戏主体][解题器][关于游戏][关卡编辑器][游戏菜单][游戏分享][背景音效]
图1 系统功能模块
在系统模块划分中，游戏主体模块、解题器模块、谜题自动生成器模块、关卡编辑器模块这四个模块的设计相当重要。游戏主体模块用于实现游戏界面的生成，接收用户的输入，并根据用户输入，通过调用解题器模块，判断用户输入的正误；解题器模块采用了无论在时间效率还是空间效率都有着明显优势的舞蹈链算法实现；谜题自动生成器模块是为了使游戏更加生动有趣，系统已经内置四个等级（初试身手、渐入佳境、龙潭虎穴、巅峰时刻）共800套谜题，对于希望自定义游戏内容的用户，可以通过谜题自动生成器模块建立自己的谜题库；关卡编辑器模块使得用户在完成低级别的谜题后，才可以继续挑战更高等级的谜题，关卡编辑器是基于HTML和javascript写的网页版工具；游戏菜单模块在主菜单里提供了一系列常用的按钮，方便用户选择相应的功能；关于游戏模块为用户提供了游戏说明，帮助用户快速掌握游戏使用方法；为了在解题时增加乐趣，用户可以选择开启游戏背景音效模块；游戏分享模块用于通过短信或邮件的方式向其他用户分享该款游戏。
2 系统实现的关键技术
系统采用多种技术实现数独游戏的各个功能模块。其中，开发硬件环境为MacBook Pro，测试环境为iphone simulator，开发的软件环境为Mac OS 10.11+Xcode 7.1+ Cocos2D-iphone，编程语言采用Objective-C，数据库采用SQLite。在解题方面，采用了舞蹈链算法，解题效率极高。
2.1 Objective-C
系统开发采用Objective-C。Objective-C[3]是非常实用的编程语言，它是一个用C写成的很小的运行库，是一种扩充了C的面向对象的编程语言。Objective-C可以在支持GCC的系统上编译并运行。利用Objective-C可以编写如IOS操作系统、IOS应用程序等一系列程序。
Objective-C不支持多重继承，且不支持运算符重载。Objective-C使用动态运行时类型（dynamicaly typed），所有的方法都是函数调用（包括系统调用），它的类库比C++更容易操作，Objective-C在运行时可以允许根据字符串名字来访问方法和类，还可以动态连接和添加类。
2.2 Cocos 2D开发框架
Cocos2D[4]是用于构建iPhone游戏的开源框架，是基于iPhone核心SDK之上架构而成，用于构建2D游戏、演示程序和其他图形界面交互应用等。它可以让程序员在创建自己的iPhone游戏时节省很多时间。它具有很多功能，比如sprite（精灵）扶持、非常酷的图形效果、动画效果、物理库、音频引擎等。
Cocos2D也拥有几个主要版本，包括Cocos2D-
iPhone、Cocos2D-X。在系统开发过程中采用Cocos2D-iPhone版本的框架。虽然Cocos2D-X是一个跨平台的框架，开发的应用程序可以适用于不同的平台，但是在实际开发过程中，需要处理很多与平台相关的问题，而Cocos2D-iPhone版本仅针对IOS平台，以Objective-C为编程语言，和苹果的硬件系统结合非常好，因此它是开发IOS游戏的不二选择。
2.3 Xcode开发工具
Xcode[5]是运行在操作系统Mac OS X上的集成开发工具（IDE），由苹果公司开发。Xcode是开发Mac OS X和iOS应用程序的最快捷的方式。Xcode具有统一的用户界面设计，编码、测试、调试都在一个简单的窗口内完成。
Xcode支持多种开发语言，如C、C++、Objective-C、Java、Python等，Xcode由苹果公司开发，是一款免费的开发工具，与Mac OS X一起发行，可以在苹果公司官方的网站下载，目前最新版本是Xcode 7.1。
2.4 舞蹈链算法
舞蹈链算法[6]（Dancing Links）的发明者是Don Knuth，利用该算法可以使很多搜索问题得到优化，舞蹈链算法不仅可以解决精确覆盖问题，还可用于重复覆盖问题。Dancing Links用的数据结构是交叉十字循环双向链，Dancing Links中每个元素有六个分量，分别为：Left指向左边的元素、Right指向右边的元素、Up指向上边的元素、Down指向下边的元素、Col指向列标元素、Row指示当前元素所在的行。
利用舞蹈链算法求解数独问题需要下列四个步骤：①把数独问题转换为精确覆盖问题；②设计出数据矩阵；③用舞蹈链算法求解该精确覆盖问题；④把该精确覆盖问题的解转换为数独的解。
与此相对应，也可以利用暴力破解法解决数独问题，暴力破解法基本思想是：根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。通过测算，舞蹈链算法无论在时间效率还是空间效率方面都优于暴力破解法，因此它是最适合用于解决数独问题的算法。
3 系统运行界面
本应用安装完成后，包括了开始游戏、谜题生成器、快速解题器、背景音效开启、排行榜与成就、关于游戏、游戏分享、获取更多游戏共八部分系统界面，其主界面如图2所示。当点击开始游戏后进入到游戏难度等级选择界面，难度等级共划分成四类（初试身手、渐入佳境、龙潭虎穴、巅峰时刻），用户从最低难度等级的谜题开始。每一类难度等级有200题，系统共内置800个谜题，每题下方显示答题时长，谜题关卡界面如图3所示，对于尚未完成的谜题则显示为灰色。选择一个谜题进入游戏界面，游戏界面如图4所示，游戏界面以咖啡色为主色调，包含了9行9列共81个格子，大部分区域已经填写好数字，用户只需选择空白区域，并填入合适的数字即可，用户也可以利用右上角的重置按钮，将游戏恢复到原始状态。用户的状态数据保存在本地数据库SQLite中。
4 结束语
数独游戏看似简单，但由于数字排列可以做到千变万化，因此成了考验玩家耐心与逻辑推理能力的一款益智类游戏，深受大众喜爱。该游戏基于IOS平台，可以运行在任意的IOS移动终端上，其界面美观，性能稳定。随着智能手机的普及以及4G时代的全面开启，这一类益智游戏将具有更大的市场空间。
参考文献（References）：
[1] 天极网.2015手游市场报告：中国成全球最大市场[EB/OL].
http：//gameonline.yesky.com/482/95650482.shtml，2015.9.
[2] 王阳，褚治广.基于Android 平台的数独游戏设计[J].辽宁工
业大学学报（自然科学版），2013.8.
[3] 杨正洪，郑齐心等.IOS编程揭秘——Objective-C程序设计
入门[M].清华大学出版社，2013.
[4] 刘杰逾.基于IOS平台的一款游戏设计与实现[D]. 电子科技
大学，2012.5.
[5] 林冀，范俊等.Objective-C程序设计（第四版）[M].电子工业
出版社，2012.
[6] 万仓一黍博客园.算法实践——舞蹈链（Dancing Links）算法
求解数独[EB/OL].http：//www.cnblogs.com/grenet/p/3163550.html，2013.7.
