kakuro数独问题

《kakuro数独问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Kakuro数独问题092260周扬092312童思博问题描述：l在空格中填入数字1-9，数字0不能出现l带斜线的方格，斜线上方的数字等于该方格右面对应的一组水平空格里的数字之和；斜线下方的数字，等于该方格下面对应一组垂直空格里的数字之和l同一数字在每组水平（垂直）空格里只能出现一次(右图为一范例)针对Kakuro数独，完成以下问题：l讨论求解模型或方法,并给出算法复杂性讨论.l如何对Kakuro数独问题划分为不同级别，并给出一种划分方式，并给出实例.l如何产生不同级别的Kakuro数独，并保证产生的数独问题为唯一解。l假

2、定所有kakuro数独都以8x10为标准进行讨论.问题背景：数谜(Kakuro)　　  当大家还在钻研数独Sudoku，究竟填写1至9这几个数字的窍门时，另一个相类的游戏于最近迅速火爆，这就是Kakuro。Kakuro在英美等地人气急升，它的好玩之处在于既有Sudoku的逻辑推理，还多了加数运算。　　在空格内选添1-9中一个数字，最终目的使那些数字加起来之和与所给的数字相等。说起来简单，实际上想在游戏中过关可不是那么容易的。　　Kakuro相比Sudoku更难玩，除了涉及逻辑推理，更要大家计算加数。与Sudoku一样，是将

3、一串数字加到面板上，大前提是加入的数字是空格旁边数字的总和，还有该总和算式内的数字不能重复。　　玩Kakuro，会用到在小学时期的加数运算法，如要填入3个方格，单是总和9便已经有3个配搭，包括1+2+6、1+3+5、2+3+4；再者，数字的次序可以不同，这样便有18个组合，究竟哪个才是正确答案，这就是游戏的最困难地方。Kakuro是一款在游戏中需要增加运算(加法)的智力游戏，逻辑推理性很强。与数独玩法相近但趣味更丰富、挑战性更大。Kakuro的玩法与数独相似，有的是由3乘以3的9个方格组成，每个方格又分成3乘以3的9格，在

4、空格内选添1至9中的一个数字，最终目的是使那些数字加起来之和与所给出的数字相等。也有的是8乘10的方格组成，其他刚相同。游戏规则每一道谜题都是实体格和“线索”格的组合，再加上一个个自成一体的空格组。每个空格组，我们称之为一个“回”，游戏的目的就是在空格中填入1到9等数字，每一回里，相同的数字不能重复出现。每一行，列的“回”，会先从灰色的线索格开始，它就位在每一回的左边（就列而言），或上面（就行而言）。每一个回在遇到实体格或线索格就结束了。线索格通常以对角线分成两半，包含一到两个数字，一个数字就是一个“提示码”。斜线上方的提

5、示码代表该列数字的加总总和；相同的，斜线下方的提示码则表示在它以下的行回数字的加总总和。不论在行回或列回里，数字都不能重复。举例来说，4不能拆解成（2，2），只能拆解成（1，3）符号说明n数独中需要填入的空格总数Xi空格中填入的数（i=1,2,3，…，n）m数独中“回”的个数，即一行（列）空格组的组数Yj每一个“回”的和（j=1,2,3，…，m）SUMi用于判断其填入数的重复性，设定的初值为45MULi作用同上，设定的初值为9!=362880A一个二元一唯数组表，作用也是判断其重复性问题分析：a)若给出一存在可行解的数独，

6、最简单直接的办法就是将其每个空格设为一个未知元Xi（i=1,2,3……，n），利用LINGO的线性规划功能求解，同时需加上限制条件（同一数字在每组水平（垂直）空格里只能出现一次），但是这个算法的计算量（忽略数字重复的剪枝）高达9n，如范例给出的就为940≈1.47*1038，显然我们不能承受如此恐怖的计算量，但这是最为直接、最容易想到的方法。简化计算量势在必行。我们可以确定数独本就为一个搜索类型的题目，当搜索的次数达到一定量时（如9n）必然可以求出答案（若没有答案，则不存在可行解）！因此，我们需要更多的剪枝来优化搜索的次数

7、。1）技巧性的剪枝一：唯一分解方式数和中有些和值只有一种分解方式。2字组的优化：92→A223字组的优化：93→A33……依此类推：9n→Ann（n=1,2,3,……,9）简化效率非常的客观！2字组·3=1+2·4=1+3·16=7+9·17=8+93字组·6=1+2+3·7=1+2+4·23=6+8+9·24=7+8+94字组·10=1+2+3+4·11=1+2+3+5·29=5+7+8+9·30=6+7+8+95字组·15=1+2+3+4+5·16=1+2+3+4+6·34=4+6+7+8+9·35=5+6+7+8+9

8、6字组·21=1+2+3+4+5+6·22=1+2+3+4+5+7·38=3+5+6+7+8+9·39=4+5+6+7+8+97字组·28=1+2+3+4+5+6+7·29=1+2+3+4+5+6+8·41=2+4+5+6+7+8+9·42=3+4+5+6+7+8+98字组·36=1+2+3+4+5+6