学文网摘要：KenKen是一种类似于数独的数字游戏，是数独游戏与数学运算规则的巧妙结合。它既能像数独游戏那样锻炼人的逻辑思维能力，又能同时训练人的数学运算能力。该文针对KenKen问题提出了一种高效、可行的生成算法，该算法包括三个部分的内容：基于矩阵的初等变换生成满足KenKen规则的解矩阵、运用改进的合并算法生成“盒子”和随机生成“提示”。可基于该算法开发成型的软件产品，用于启蒙、教学、娱乐。
关键词：KenKen；游戏；算法
中***分类号：TP391 文献标识码：A 文章编号：1009-3044（2013）04-0811-04
Study on the Generation Algorithm of KenKen Problem
TU Yang-yang
（Wuhan University of Science and Technology City College，Wuhan 430083，China）
Abstract： KenKen， a digital game similar to Sudoku， is the ingenious combination between Sudoku game and math rules. It not only can train a person's logical thinking ability like Sudoku games， but also can train their mathematical ability. In this paper， an efficient and feasible generation algorithm of KenKen problem has been put forward. This algorithm consists of three parts： generate solution matrix abide by KenKen rules based on elementary transformation of matrix， generate “Box” by improved merging algorithm and generate “Prompt” randomly. Software products can be developed based on this algorithm for enlighten， teaching and entertainment.
Key words： KenKen； game； algorithm
KenKen（又名聪明方格、算独、Kendoku），一种类似于数独的数字益智游戏，由日本东京一位名叫宫本哲也的老师为帮助儿童学习算数而发明[1]。它的规则是：给出N×N的方格，用1到N这些数字填入其中，每一行每一列都不能有重复的数字。方格中的黑色粗线框出若干个限定框，称为“盒子”，每个盒子中数字的和、差、积或商会标注在盒子的左上角，称为“提示”[2]。例如提示是“6×”，则说明该盒子中的数字之积为6；提示是“2÷”，则说明该盒子中的大数除以小数的商为2；提示是“1”，则说明该盒子中的数为1，如***1所示。
本文试***对KenKen问题进行分析，设计算法，达到实现利用计算机程序自动生成KenKen问题的目的。
1 算法整体分析
通过观察不难发现，KenKen问题，是由若干个盒子和与之对应的提示两个大的部分所构成的。同时，提示又是根据其所在盒子内的数字的计算结果而确定的，也就是说先得有数据，才能根据数据计算出提示。由此可以得出结论，要生成一个KenKen问题，算法必须要完成以下三个步骤的内容：
1）生成一个满足KenKen规则的解矩阵，作为提示的数据来源。矩阵为N阶方阵，且每一行每一列均为1到N，N个互不相同的数字。
2）生成盒子。即对矩阵进行划分，将矩阵随机划分为若干个连续的小区域。
3）生成提示。根据每个盒子内数字的数量与内容，随机产生运算符号并计算运算结果，从而得到提示的内容。
2 算法详细设计
2.1生成满足KenKen规则的解矩阵
生成一个满足KenKen规则的解矩阵，即对N阶方阵赋值，使其每一行每一列均为1到N，N个互不相同的数。一个可行的办法是使用拉斯维加斯算法[3]，即在N阶方阵中随机填入1到N，N个数，然后不断地基于KenKen规则对其进行求解，直到解出为止。其中，求解过程又可使用多种算法，例如比较排除法[4]、***搜索策略法[5]、回溯法[6]、遗传算法[7]等。
上述算法虽然可行，但多存在效率问题。KenKen问题虽与数独问题类似，但是在规则上有所不同。不同之处在于：数独问题不仅要求每行每列上的数字不能重复，还要求在每个小的3×3的宫格内不能重复[8]；而KenKen问题只要求每行每列的数字不能重复。可以此为突破口，寻求更简单、更高效的算法来生成满足KenKen规则的解矩阵。通过观察，发现进行矩阵的初等变换，即任意交换KenKen解矩阵的两行或者两列后[9]，得到的新矩阵依然满足KenKen规则。如***2所示为一个满足KenKen规则的4阶解矩阵，矩阵每行每列无重复数字。交换***2的第一行和第三行得到***3，交换***3的第二列和第四列得到***4。经过交换后的***3和***4所示的矩阵依然为满足KenKen规则的解矩阵。
由此得出结论，可以使用基于矩阵初等变换的算法来生成满足KenKen规则的解矩阵，即可行，又具有较高的效率。具体做法是：首先生成一个固定的有规律的初始解矩阵（如***5所示），然后对其进行一定次数的随机行变换和列变换，从而得到最终结果。例如对***5所示的初始解矩阵进行五次初等变换：依次交换第三、四列，第二、四行，第二、三列，第一、二行和第一、三行后，得到一个满足KenKen规则的解矩阵（如***6所示）。
此算法在实际操作的过程中存在一个可商榷的问题，即随机初等变换的次数应该如何确定。可想而知，如果初等变换次数过少，那么初始的解矩阵会产生打乱不充分的现象；如果初等变换次数过多，则会影响效率且不能确保打乱效果。在此，提出两点建议：1）通过对初等变换次数进行大量的尝试和调整，发现当变换次数大于10次时，有着较好的打乱效果；2）如果想确保打乱效果，可以考虑在初等变换的过程中设置一个打乱效果评价指标，直到满足该指标时停止变换。
2.2 生成盒子
随机生成盒子，即将N阶方阵为随即划分为若干个连续的区域，每个区域包含一定数量的方格。首先考虑到一个可行的算法：生成一个划分方案，例如{4，3，3，2，2，1，1}，表示拟将方阵划分为7个盒子，每个盒子包含的方格数量分别为4，3，3，2，2，1，1。然后按照此方案，随机在方阵中依次划分出这7个盒子，若碰到无法划分下去的情况则回溯。这种算法对盒子数量和其包含的方格数量要求非常严格，由于回溯机制，使得算法存在效率上面的问题，并且划分方案的生成也需要专门的算法设计。另外一个可行的算法是采取合并法，即从第一个方格1开始向下或向右试探其相邻的方格2，若方格2不在盒子中就和方格1合并生成新的盒子，反之将方格1合并到方格2所在的盒子中[10]。这种算法不存在回溯，执行效率较高，但是也存在一些问题。可想而知，划分结束后，方阵内的盒子包含的方格数量只可能为3，2或者1，不可能出现包含方格数量为3以上的盒子。同时只包含一个方格的盒子只可能在方阵底端出现且机率偏小。这样一来会使KenKen问题显得过分单调。
综合分析，考虑将合并算法进行改进，采取改进的合并算法对方阵进行划分，随机生成盒子。为方便表述，用1到16依次对方阵逐行逐列进行编号（如***7）。下面以4阶方阵为例说明算法思路：
1）给出两个限定条件：1）生成的所有盒子中，包含方格数量的最大值不能超过P。2）生成的所有盒子中有且只有Q个只包含一个方格的盒子。这两个条件的作用是为了规避合并算法的缺陷，为后期调整盒子提供依据。P值和Q值的确定是一个需要注意的问题：P值如果设置得过大，会使KenKen问题的难度过大，以致失去游戏性；而Q值设置得过大，会导致KenKen问题的难度过小，亦会影响到游戏性。对于四阶的KenKen问题，我们不妨将P设为4，将Q设为2。
2）利用合并算法对方阵进行初步划分，过程如表1所示，划分结果如***8所示。
3）结合给出的两个限定条件，对初步划分结果进行调整。调整的算法为首先检测两个限定条件是否成立，如果成立则退出调整；如果不成立分三种情况处理：1）只有P不成立，将不成立的盒子划出一部分与相邻盒子合并，使得剩下的盒子满足P；2）只有Q不成立，随机寻找一个包含方格最少的盒子，保留一个方格单独成为一个盒子，将其余部分与相邻盒子进行合并；3）P和Q同时不成立，调整办法与2相同。为提高效率，可在调整的时候做一个预判，检测此次调整是否会将不满足一个限定条件的情况变为两个条件都不满足的情况。针对***8所示的初步划分结果，通过调整算法，将方格15并入了方格14所在的盒子，将方格12并入了方格8所在的盒子。去掉方格编号后，结果如***9所示。
2.3 生成提示
生成提示需要算法做的事情，就是为方阵中的每个盒子随机生成一个四则运算符号，并利用运算符号对盒子中的数字进行运算，进而根据运算符号和运算结果生成该盒子的相应提示。具体到为某一个特定的盒子生成提示的时候，算法需要分三种情况来处理：
1）如果某一个盒子包含的方格数量大于2，则只能在“+”和“×”两种运算符号中随机生成一种。然后对盒子中的数字进行连加或连乘的运算，并根据运算结果生成该盒子的提示。
2）如果某一个盒子包含的方格数量为2，则可在“+”、“-”、“×”和“÷”四种运算符号中随机生成一种。并对盒子中的数字进行运算，进而生成该盒子的提示。这里注意两个问题：1）在进行减法和除法运算的时候需要将较大的那一个数调整到运算符号的左边，避免在运算结果中出现负数或零的情况。2）如果存在大数除以小数不能整除的情况，则只能考虑在“+”、“-”和“×”三种运算符号中随机生成一种进行运算。
3）如果某一个盒子仅包含一个方格，则不用生成运算符号，直接将方格中的数字作为提示生成。
将***6中满足KenKen规则的解矩阵填入***9的盒子中，对其按照算法生成提示（如***10所示），再将盒子中的数字去掉，便生成了一个KenKen问题（如***11所示）。
3 结束语
KenKen是数独游戏与数学运算规则的巧妙结合，不仅更加有趣好玩，同时也能寓教于乐。该文通过三个部分：基于矩阵的初等变换生成满足KenKen规则的解矩阵、运用改进的合并算法生成盒子和随机生成提示，提出了KenKen问题的高效、可行的生成算法。在经济文化日益发展的今天，人们的生活水平得到了很大的提高。生活在钢筋混凝土大都市里的人群，每天都要面对各种各样的生活压力[11]。基于本算法开发出成型的软件产品，可以缓解人们的压力，放松大脑，提供最好的思维锻炼。同时可用于启蒙、教学，对孩子熟悉四则运算，提高逻辑推理能力，激发对数学的热爱起到潜移默化的积极推动作用。
参考文献：
[1] 覃琛琛. KenKen：A New Sudoku Puzzle新数独游戏[J].数学教学通讯：数学金刊，2009（6）.
[2] 王瑞霖，张惠英.用KenKen游戏提高学生逻辑运算能力与逻辑思维能力[J].教育实践与研究：中学版（B），2012（4）.
[3] 薛源海，蒋彪彬，李永卓.基于“挖洞”思想的数独游戏生成算法[J].数学的实践与认识，2009（21）.
[4] 易珺，朱静文，曹东.数独求解算法的设计与实现[J].科学技术与工程，2010（27）.
[5] 李昊.基于***搜索策略的数独问题算法与实现[J]. 通化师范学院学报，2009（10）.
[6] 李盘荣.数独游戏的算法研究与实现[J].电脑知识与技术，2008（26）.
[7] 黎永达，邓秀勤.基于改进的遗传算法的数独谜题求解[J].计算机应用与软件，2011（3）.
[8] 刘晓宝.数独游戏的解题算法[J].电脑编程技巧与维护，2007（5）.
[9] 陈祥云.矩阵的初等变换及其应用[J].高等函授学报：自然科学版，2012（2）.
[10] 金伟，谭劲.一种数字迷宫游戏程序设计[J].计算机时代，2012（7）.
[11] 郭东恩，吴刚.基于Android平台的数独游戏设计与实现[J].计算机与数字工程，2012（3）.
转载请注明出处学文网 » KenKen问题的生成算法研究