数独游戏的实现与算法优化

论文总字数：26011字

摘 要

数独是一种源自18世纪末的瑞士，后在美国发展，并在日本得以发扬光的数字谜题。数独盘面是个九宫，每一宫又分为九个小格,在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字，使1-9每个数字在每一行、每一列和每一宫中都只出现一次。数独游戏可以训练人们的逻辑思维，增进大脑的推理能力，帮助人们建立排列组合的概念，养成自主动脑的习惯。九宫数独可以锻炼大脑的思维灵活度同时增强人全面看问题的能力。现如今，计算机的快速发展带动了数独设计以及计算的多元化，数独进入了高速发展期。

本文主要阐述了以Java为开发语言，以Android studio为开发工具，基于Android系统开发的一款数独游戏，实现相应的难度选择、继续游戏、答案提示等功能，以sublime text为开发工具，对数独游戏进行算法优化和调整，实现计时、生成游戏、显示答案等功能。

关键词： 数独；Android；Java；html

Abstract：Sudoku is a digital puzzle that originated in Switzerland at the end of the 18th century, developed in the United States and flourished in Japan. Sudoku Disk is a Nine Palace, each palace is divided into nine small squares. In the eighty-one lattices, given some known numbers and solution conditions, using logic and reasoning, fill in the other blanks with 1-9 numbers. Make 1-9 each number appear only once in every row, column and palace. It can train logical thinking and improve the brain"s reasoning ability. Help to establish the concept of permutation and combination, develop the habit of autonomous brain. Sudoku in the Ninth Palace can exercise the brain"s flexibility of thinking and enhance people"s ability to see problems in an all-round way, and Sudoku has entered a period of rapid development.

This paper mainly elaborates a Sudoku game based on Android system with Java as the development language and Android studio as the development tool. It realizes the functions of difficulty selection, continue the game、follow the answer, With sublimetext as the development tool, it optimizes and adjusts the arithmetic of the degree game, realizes the functions of timing, generating games and displaying answers.

Keywords： Sudoku; Android；Java；html；

目 录

1. 绪论 3

1.1 项目背景 3

1.2 游戏介绍 3

1.3 国内外研究现状 3

1.4 项目目的 3

2. 开发环境与技术介绍 4

2.1 开发环境 4

2.2 技术介绍 5

3. Android端数独游戏设计 5

3.1 Android数独功能需求分析 5

3.2 Android开发环境配置 6

3.3 Android 图形编程 7

4. 网页端数独游戏设计 19

4.1 网页版数独功能需求分析 19

4.2 数独算法设计 20

5. 系统测试 26

5.1 测试目的 26

5.2 测试方法 26

5.3 系统测试 26

5.4 游戏运行效果 28

结 论 34

参 考 文 献 35

1. 绪论

1.1 项目背景

2019年2月28日，中国互联网络中心（CNNIC）在京发布第四十三次《中国互联网络发展状况统计报告》《报告》从互联网应用发展、产业与技术等多个方面，展现我国互联网发展状况。《报告》显示，截至2018年12月，我国国民规模为9.29忆，全年新增网民5653万，互联网普及率达59.6%，较2017年底提升3.9%，我国手机网民规模达8.17亿，今年新增手机网民6433万，随着中国互联网的愈加普及，中国上网比例在逐步提升。在当前的中国市场中，电脑端以及手机端的娱乐方式已成为当前用户娱乐的主流项目。数独游戏起源于18世纪由瑞士数学家欧拉等人研究的拉丁方正，并于1997年后开始广为传播，风靡全球。现如今，相对于纸质的数独游戏，网络版数独游戏应运而生。

1.2 游戏介绍

数独由一个九行九列的宫格组成，从第一个空格开始，每三行散列是一个数独块，共有9个数独块，81个九宫格。用户在空格中填写的数字范围为1~9，当用户在某一个空格中填写数字时，其所填写的数字不能与其所在行、列以及数独块中的数字相等。当用户填完最后一个数字时，其九宫格所对应的所有行、所有列以及所处的数独块中的数字都是1~9。

1.3 国内外研究现状

随着数独游戏的发展，数独的基础解法被人们分析并罗列了出来。大致分为相斥法、唯一法和排除法三个方法，首先通过相斥法和唯一法判断，数独中的数字不能出现重复，若出现无法判断的情况，通过排除法排除不符合规则的数字，填入数字后，不断地通过其中的方法顺序进行解题，直到完成数独游戏。杨晓华教授用c语言模拟数独的人工解题思路，介绍了唯一法、排除法和回溯法三种解题方法^[1]。本文将参考回溯法生成数独并对回溯法进行改进。

1.4 项目目的

随着互联网的普及，越来越多的人们开始倾向于使用电子产品例如手机、电脑。而且当人们去体验纸质数独的时候，需要随身携带纸笔和一个待解的数独本。显然，在这个时候手机端和网页端的数独游戏往往更具有优势，它可以非常便利的节省用户的碎片时间，无论是上班等待地铁时还是当使用电脑工作休息时都可以随时打开数独游戏，并且随时关闭。不需要在填写数字错误的时候，用橡皮擦反复进行擦出；其次免去了找数独谜题，然后撰写谜题的步骤，在游戏中存储的数独谜题，可以让玩家能够随时随地选择不同的数独进行填写。

2. 开发环境与技术介绍

2.1 开发环境

2.1.1 Windows 10操作系统

本系统采用的操作系统为windows10，可以自由分发而且是免费使用的。他能够运行主要的工具软件、网络协议以及应用程序等，它既支持32位也支持64位硬件。Windows用户界面和开发环境都是面向对象的。用户采用“选择对象-操作对象”这种方式进行工作。这种操作方式模拟了现实世界的行为，易于理解、学习和使用。

2.1.2 Android Studio环境

Android studio是基于InteliJ IDEA的官方提供的专门针对android开发者的开发环境，对比eclipse，同样是java语言开发的集成环境，IntelliJ在业界被公认为最好的java开发工具之一，在启动速度、智能代码助手、代码自动提示、重构、J2EE支持、Ant、JUnit、CVS整合、代码审查、 创新的GUI设计等方面的功能都优于eclipse，它基于gradle的项目构建系统，这让我们在构建Android项目的时候更加灵活，并且可以通过变量配置来生成多个版本的apk文件，拥有大量的代码模板可以快速地帮用户构建Android项目，内置link tools代码优化工具，可以捕捉性能，可用性，版本兼容等问题。

2.1.3 Sublime text环境

Sublime text为最好的java开发工具之一，在启动速度、智能代码助手、代码自动提示、重构、J2EE支持、Ant、JUnit、CVS整合、代码审查、 创新的GUI设计等方面的功能都优于Sublime Text是一个代码编辑器，也是HTML和散文先进的文本编辑器。Sublime Text具有漂亮的用户界面和强大的功能，列入代码缩略图，Python的插件代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text的主要功能包括：拼写检查，书签Goto功能，及时项目切换，多选择，多窗口等等。他是一个跨平台的编辑器，同时支持Windows、Linux、Max OS等操作系统。

2.2 技术介绍

2.2.1 java语言技术

Java语言具有如：简单性、稳健性、可移植性等诸多特点。Java似乎设计得看起来很像C ，但是为了使语言简洁并且容易让人熟悉，设计人员剔除了C 语言中许多可用的特征，这些特征是程序员很少使用的。除此以外，Java还剔除了C 的操作符重载和多继承的特征，并且不使用主文件，从而消除了预处理程序。因为Java没有结构，所以数组和串都是对象，因此不需要指针。Java自动处理对象的引用以及间接引用，实现自动无用的单元收集，消除了程序员对存储管理问题的担忧^[2,3]。

2.2.2 Javascript语言技术

Javascript是一种解释性脚本语言，主要用来向HTML页面添加交互行为，可以直接嵌入HTML页面，但写成单独的js文件有利于结构和行为的分离，具有跨平台特性，在绝大多数浏览器的支持下，可以在多种平台下运行（如Windows、Linux、Mac、Android、IOS等），它已经被广泛用于Web应用开发，常用来向网页添加各式各样的动态功能，为用户提供更流畅美观的浏览效果^[4]。

2.2.3 算法技术

本文将采取两种不同的算法实现Web版数独游戏和Andoroid数独游戏，在Android端数独游戏中，通过定义字符串在game类中，存储数独初始谜题。但在web端数独游戏中，采取递归算法生成数独游戏。常规回朔法的最原始方法即从数独的左上角（0,0）处开始，生成随机数，然后依次按照从左往右、从上往下的顺序逐渐生成满足数独规则的最终数独。但在具体实现中，此类方法生成数独太过复杂。经过研究数独规则，在执行回溯算法之前优先循环遍历3、5、7相关小九宫格块并随机填写数字，大大节约生成数独的效率。对比Android数独，网页版数独游戏对游戏的题库选择实现了较大的扩增，将不必使用预先存储在数独游戏中的题库，每次游戏开始前，随机生成^[5,6]。

3. Android端数独游戏设计

3.1 Android数独功能需求分析

此数独游戏是基于Andorid平台进行实现，并且最终程序将在夜神模拟器中进行实现。该数独游戏面向Android端用户群体，提供给用户体验简洁、便利的操作模式，点击屏幕上的空白部分，便可以跳出备选框，选择想要填写的数字，进行数独的不断实现，此程序中存储了3种不同难度的数独游戏题目，可供用户选择^[7,8]。

1.继续功能

剩余内容已隐藏，请支付后下载全文，论文总字数：26011字