您现在的位置:网站首页答辩论文论文专题

"数独"谜题生成器(Sudoku Designer)-2008年美国数学建模竞赛MCM一等奖论文中文版

  • 简介:“数独”谜题生成器邓璎函(西南大学数学与统计学院2006级, 重庆 400715)摘要:这篇论文主要是阐述了Sudoku(数独,一种益智游戏)的谜题自动生成(非人工录入等)的方法以及定义它们的难度等级方法。根据直接推断法,运用矩阵...
    • 请与管理员联系购买资料 QQ:5739126
  • 论文简介
  • 相关论文
  • 论文下载
[页数] 24    [字数] 8322

[目录]
1 引言 2
2 设计的准备 3
3 Algorithms about Making Template 5
4 算法的复杂度 14
5 确定谜题的难度水平 17
6 算法和难度水平的延展 21
参考文献 21

[原文]
1 引言
Sudoku,也就是数独,是一种益智填数游戏,风靡全球。完成Sudoku谜题,需要严密的逻辑推理。
1.1 Sudoku的概念
大多数的Sudoku谜题出现在这个9×9的大格子中,这9×9个格子又被区分为九个3×3的小格子(称之为“域”),如图1所示。    
图 1  数独格子及它的九宫格
它的目标是在一个九宫格中填上数字,使九宫格的每一行和每一列,以及九宫格中的九个3×3的域里都包含数字1到9。Sudoku谜题是一个已填充部分数字的九宫格。待填入的新数字应在每一个域,以及每一列和每一行中都是唯一的。
图 2  A Sudoku puzzle               图 3  Puzzle’s answer
日本引进了现代数字游戏。“数独”一词源于日语,意思是“数字只能出现一次”。2004年,英国的报纸刊登了数独游戏。目前它已风靡全球。
牛津大学和剑桥大学每年都会组织大学生参加一次“Sudoku大赛”。
除了通常的9×9格Sudoku,还有许多其他格数的Sudoku,比如:简单的拥有四个2×2格域的 4×4格Sudoku,适合儿童,也能方便的提供到手机上;还有5×5 格、6×6格以及7×7格的Sudoku;对于高级的游戏玩家,甚至还有16×16格和25×25格的Sudoku。
除了格子数目的变化外,Sudoku还有其他类型的变化,如用字母或者符号替换数字、改变域的形状等。
Sudoku的魅力在于,它的规则很简单,但是要解一个好的Sudoku谜题却是一个智力的挑战。而且,Sudoku也是一个老少皆宜的益智游戏,因为它可以由线索数量等决定出不同的难度水平,适合所有人。
1.2 Sudoku的一些性质
Sudoku谜题通过以下变化会发生转换:
? 数字的排列,比如把2替换为1,把4替换2,把1替换为4,等等。这样一共有9! = 362880。
? 交换同一个域中的行,比如,交换第一行和第二行,(注意不允许交换不同域中的行)。所以这里有 种。加上每三行之间的交换,最终可以得到  种。
? 列的交换同理于行,所以有 种。
? 移项(交换行和列),这样有两种可能性。
那么每个Sudoku谜题都有 种等价的谜题,对吗?当然不对,因为或许存在结果相同的交换......

[摘要]
这篇论文主要是阐述了Sudoku(数独,一种益智游戏)的谜题自动生成(非人工录入等)的方法以及定义它们的难度等级方法。根据直接推断法,运用矩阵工具,发展了4种生成Sudoku的算法。同时,根据试验-错误-矫正的方法,设计了另一个算法——预测-矫正算法。通过预测-矫正算法的运行,我们可以获得线索数量少于20个的Sudoku谜题。这5种算法都确保了谜题答案的唯一性。由上述5种算法推知,谜题的难度水平与其线索的数量相关。运用相对方差的理论,得到与谜题的难度水平相关的另一个关系,即在行、列、域中的分布情况。结合这两个与谜题难度水平相关关系,建立对谜题难度水平的评价标准。此外,分别举例说明了所划分的8个难度水平。值得说明的是运用我们的算法所得到的Sudoku谜题的难度水平范围是非常广的。另外,还分析了算法的复杂度以使得算法的复杂度尽可能的小。

[参考文献]
[1]Gary McGuire, "Sudoku Checker and the Minimum Number of Clues Problem",  http://www.math.ie/checker.html.
[2]Andrew C.Bartlett, Amy N.Langville,” An Integer Programming Model for the Sudoku Problem”, March, 18, 2006.
[3]Wei-Meng Lee, Programming Sudoku, P139, Apress.
[4]Wei Xiao, MATLAB program design and application, P95, the Public Tsinghua University, 2005, CHINA.
[5]Qiyuan Jiang, Mathematical Model, China Higher Education Press, 2006, CHINA.
[6]http://www.sd9981.com/sudoku-online.asp, Accessed, Feb, 15th, 2008.
[7]”SuDoku the Number-Placing Puzzle”, http://www.cleavebooks.co.uk/trol/trolxs.pdf
[8]TomDavis, ”The Mathematics of Sudoku”,
http://dit.unitn.it/-montreso/asd/progetti/2006-07/Esercitazione-2/sudoku-Davis.pdf.


[原文截取]
“数独”谜题生成器
邓璎函
(西南大学数学与统计学院2006级, 重庆 400715)
摘要:这篇论文主要是阐述了Sudoku(数独,一种益智游戏)的谜题自动生成(非人工录入等)的方法以及定义它们的难度等级方法。根据直接推断法,运用矩阵工具,发展了4种生成Sudoku的算法。同时,根据试验-错误-矫正的方法,设计了另一个算法——预测-矫正算法。通过预测-矫正算法的运行,我们可以获得线索数量少于20个的Sudoku谜题。这5种算法都确保了谜题答案的唯一性。由上述5种算法推知,谜题的难度水平与其线索的数量相关。运用相对方差的理论,得到与谜题的难度水平相关的另一个关系,即在行、列、域中的分布情况。结合这两个与谜题难度水平相关关系,建立对谜题难度水平的评价标准。此外,分别举例说明了所划分的8个难度水平。值得说明的是运用我们的算法所得到的Sudoku谜题的难度水平范围是非常广的。另外,还分析了算法的复杂度以使得算法的复杂度尽可能的小。
关键词:Sudoku谜题,预测-矫正算法,相对方差,难度水平,复杂度
Sudoku Designer
Deng Yinghan
(College of Mathe.....
查看评论 已有0位网友发表了看法
  • 验证码: