大作业1——数独解算器实现

《大作业1——数独解算器实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大作业1——数独解算器的实现问题描述“数独sudoku”来自日文，但概念源自“拉丁方块”，是十八世纪瑞士数学家欧拉发明的。游戏规则很简单：在九个九宫格里，填入1到9的数字，让每个数字在每个行、列及九宫格里都只出现一次。谜题中会预先填入若干数字，其它宫位则留白，玩家得依谜题中的数字分布状况，逻辑推敲出剩下的空格里是什么数字。这种风靡日本及欧美的“数独sudoku”，据说原创者是18世纪的瑞士人，但没有得到应有的注目，直到20多年前，美国人重新挖掘它的魅力，接着日本杂志出版商在八○年代末期在一本美国杂志上看到这个游戏，带

2、回日本后，增加它的游戏难度，并命名为“数独sudoku”，“数独”谜戏就此诞生，并逐渐受到日本人的注意、沉迷，日本坊间书局还出版了许多“数独”的书。纽西兰裔英籍退休法官韦恩．古德（WayneGould）一九九七年旅游日本时，买了一本数独游戏书，进而开始供稿给全球十几家报社，立即受到读者的热烈回响，邀他供稿的媒体还正不断增加中；据说，“数独”还成为英国报纸销售量的法宝，连美国纽约时报也无法阻挡它的魅力，开始定期登载。94年5月30日起，台湾的中国时报也取得古德的授权，每天都刊出一则数独谜题，让这个新玩意第一次出现在台湾

3、的大众媒体上，也是全球第一家引入数独游戏的中文报纸。填制规则数独的游戏规则很简单：在九个九宫格里，填入１到９的数字，让每个数字在每个行、列及九宫格里都只出现一次就可以过关了！ 谜题中会预先填入若干数字，其它宫位则留白，玩家得依谜题中的数字分布状况，逻辑推敲出剩下的空格里是什么数字。下图就是一个简易级的数独谜题与它的唯一解：我们的题目是：设计一个程序，尽量快地找到数独的解。程序说明：要求编写一个可执行程序Work1.exe：能够从文本文件中读入数独数据，求解后输出到文本文件中。典型的程序调用方式如下：HomeWork1

4、.exee:input.txte:output.txtHomeWork1.exe是用同学们的程序在VC6下编译后得到的可执行程序名称。而后面的e:input.exe与e:output.exe是为这个程序执行所提供的参数。在控制台下键入上述命令后，你的程序要首先从e:input.txt中读入数据（输入数据文件的格式见下面），处理后将数据输出到e:output.txt中（输出数据文件的格式见下面）。而我们的评判将基于输出文件进行。调用与程序内部的参数传递方式见附录一。重点强调的是，不能将程序中写死“从e:i

5、nput.txt中输入，e:output.txt中输出”。否则在评判程序时为了方便我们要修改输入输出的文件名与命令行的调用方式，如果写死将出现程序执行错误！！！输入文件:通过文件读入输入的数据。输入文件中包含了一个9*9的矩阵，如下图所示：210630890040007005000900007002000040400102006060000100700003000800700060035094021其中包含了0~9一共10种数——0代表空格处需要进行填写。这里可以被确保的是，输入的数据中至少有一位是0。即不会出现不

6、需要填写数据的情况。输出文件：输出文件格式如下图所示：12217635894948217635356948217172356948489172356563489172721563489894721563635894721……其中，第一行包含了一个数字，代表一共找到的解的个数。接下来的10排中前9排为一个解答，第10排为一个空行。第11~19排为第二个解答，20排为另一个空行……依此类推（注意输出文件的最后一行为空行！）如果题目没有解，则输出的文本中只包含一行，内容为0。要求：1.能够处理有解，无解，有多种解的情况从背

7、景资料中不难发现，一个数独题目可能有唯一解，可能有多种解，也可能没有解答。要求编写的程序能处理上述情况。2.处理时间尽量短一个题目最多有多少种解答？根据题目的难度不同，解答的数目也不同。而不同的解答意味着不同的处理时间。在本次作业中，我们给大家的题目不会太复杂，同时要求处理的时间不能太长——一道题目的求解不超过2分钟（我们在运行大家的程序时会进行计时）。不会出过于复杂以致正常算法下2分钟无法完成的题目。示例测试数据随作业要求提供了两个测试用例：sudoku_easy.txt与sudoku_hard.txt。对应的输出

8、结果为：res_easy.txt与res_hard.txt。FormatCheckFormatCheck程序供大家来检查自己的程序输出是否符合要求。可以使用如下命令：FormatCheckInputFile来自我检测一下输出结果的正确性。其中，inputFile是经过大家的程序运行后得到的结果文件。比如编写程序后使用：HomeWork1.exe