KenKen问题生成算法探究

《KenKen问题生成算法探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、KenKen问题生成算法探究摘要：KenKen是一种类似于数独的数字游戏，是数独游戏与数学运算规则的巧妙结合。它既能像数独游戏那样锻炼人的逻辑思维能力，又能同时训练人的数学运算能力。该文针对KenKen问题提出了一种髙效、可行的生成算法，该算法包括三个部分的内容：基于矩阵的初等变换生成满足KenKen规则的解矩阵、运用改进的合并算法生成"盒子”和随机生成“提示"。可基于该算法开发成型的软件产品，用于启蒙、教学、娱乐。关键词：KenKen；游戏；算法中图分类号：TP391文献标识码：A文章编号：1009-3044(2013)04-0811-04StudyontheGenerationAlgori

2、thmofKenKenProblemTUYang-yang(WuhanUniversityofScienceandTechnologyCityCollege,Wuhan430083,China)Abstract:KenKen,adigitalgamesimilartoSudoku,istheingeniouscombinationbetweenSudokugameandmathrules・Itnotonlycantrainaperson，slogicalthinkingabilitylikeSudokugames,butalsocantraintheirmathematicalability.

3、Inthispaper,anefficientandfeasiblegenerationalgorithmofKenKenproblemhasbeenputforward.Thisalgorithmconsistsofthreeparts:generatesolutionmatrixabidebyKenKenrulesbasedonelementarytransformationofmatrix,generate“Box"byimprovedmergingalgorithmandgenerate"Prompt”randomly.Softwareproductscanbedevelopedbas

4、edonthisalgorithmforenlighten,teachingandentertainment.Keywords：KenKen；game；algorithmKenKen（又名聪明方格、算独、Kendoku）,一种类似于数独的数字益智游戏，由日本东京一位名叫宫本哲也的老师为帮助儿童学习算数而发明［1］。它的规则是：给出NXN的方格，用1到N这些数字填入其中，每一行每一列都不能有重复的数字。方格中的黑色粗线框出若干个限定框，称为“盒子”，每个盒子中数字的和、差、积或商会标注在盒子的左上角，称为“提示”［2］。例如提示是“6X”，则说明该盒子中的数字之积为6；提示是“2三”，则说明该盒

5、子中的大数除以小数的商为2；提示是“1”，则说明该盒子中的数为1,如图1所示。本文试图对KenKen问题进行分析，设计算法，达到实现利用计算机程序自动生成KenKen问题的目的。1算法整体分析通过观察不难发现，KenKen问题，是由若干个盒子和与之对应的提示两个大的部分所构成的。同时，提示又是根据其所在盒子内的数字的计算结果而确定的，也就是说先得有数据，才能根据数据计算出提示。由此可以得出结论，要生成一个KenKen问题，算法必须要完成以下三个步骤的内容:1）生成一个满足KenKen规则的解矩阵，作为提示的数据来源。矩阵为N阶方阵，且每一行每一列均为1到N,N个互不相同的数字。2）生成盒子。即

6、对矩阵进行划分，将矩阵随机划分为若干个连续的小区域。3）生成提示。根据每个盒子内数字的数量与内容，随机产生运算符号并计算运算结果，从而得到提示的内容。2算法详细设计2.1生成满足KenKen规则的解矩阵生成一个满足KenKen规则的解矩阵，即对N阶方阵赋值，使其每一行每一列均为1到N,N个互不相同的数。一个可行的办法是使用拉斯维加斯算法［3］,即在N阶方阵中随机填入1到N,N个数，然后不断地基于KenKen规则对其进行求解，直到解出为止。其中，求解过程又可使用多种算法，例如比较排除法［4］、图搜索策略法［5］、回溯法［6］、遗传算法［7］等。上述算法虽然可行，但多存在效率问题。KenKen问题

7、虽与数独问题类似，但是在规则上有所不同。不同之处在于：数独问题不仅要求每行每列上的数字不能重复，还要求在每个小的3X3的宫格内不能重复［8］；而KenKen问题只要求每行每列的数字不能重复。可以此为突破口，寻求更简单、更高效的算法来生成满足KenKen规则的解矩阵。通过观察,发现进行矩阵的初等变换，即任意交换KenKen解矩阵的两行或者两列后［9］,得到的新矩阵依然满足KenKen规则。如图2所示