[页数] 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..... |
"数独"谜题生成器(Sudoku Designer)-2008年美国数学建模竞赛MCM一等奖论文中文版
查看评论
已有0位网友发表了看法