数独

官窑高级中学严华坚【数独的概念】数独是一种源自18世纪末的瑞士、后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。【数独的历史】■你知道是谁最先发明数独的吗？1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。■你知道是哪一本杂志最先推广数独的吗？19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（DellPuzzleMαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”，在这个时候，9×9的81格数字游戏才开始成型。【数独的历史】■你知道“数独”这个游戏名称是怎么来的吗？1984年4月，在日本游戏杂志《字谜通讯Nikoil》上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（SUDOKU）。■你知道数独怎么席卷全球的吗？曾任香港高等法院法官的高乐德（WayneGould），2004年在日本旅行的时候，发现杂志的这款游戏，便带回伦敦向《泰晤士报》推介并获得接纳。英国《每日邮报》也于三日后开始连载，使数独在英国正式掀起热潮。其他国家和地区受其影响也开始连载数独。从此，这个游戏开始风靡全球。【数独快速入门】范例一：1123在左边第一个九宫格里，哪格可以放数字１？先看到再第一列和第二列里已经有了数字１所以，除了橙色格子之外，上面两列格子已经不能放１了112311231121【数独快速入门】范例二：在左边第一个九宫格里，哪格可以放数字１？112111211121【数独快速入门】范例二：在左边第一个九宫格里，哪格可以放数字１？1111111111111111【直观法】①单元唯一法(SolePositionTechnique)在左图中，观察行B，可以看到除了[B3]外，其他所有的单元格中都已有了数字，根据数独游戏的规则，即每行，列或区块中不能有重复的数字，则[B3]中能填入的数字只能是行B中所未出现过的，也就是数字3。所以可以毫不犹豫地在[B3]中填入3。【直观法】①单元唯一法(SolePositionTechnique)这里的单元(Unit,orgroup)，指的是行，列或区块。所以有三种情况：☆当某行有8个单元格中已有数字☆当某列有8个单元格中已有数字☆当某区块有8个单元格中已有数字【直观法】②单元排除法(BasicEliminationTechnique)使用单元排除法的目的就是要在某一单元（即行，列或区块）中找到能填入某一数字的唯一位置，换句话说，就是把单元中其他的空白位置都排除掉。它对应于候选数法中的隐式唯一法。那么要如何排除其余的空格呢？当然还是不能忘了游戏规则，即行，列或区块中不能有重复的数字。【直观法】②单元排除法(BasicEliminationTechnique)区块排除法是直观法中进阶的技法。虽然应用范围不如前2种方法广泛，但有时在遇到困难无法继续时，只要用一次区块排除法，接下去解题就会势如破竹了。区块排除法实际上是利用区块与行或列之间的关系来实现的，这一点与单元排除法颇为相似。然而，它实际上是一种模糊排除法，也就是说，它并不象单元排除法那样利用谜题中现有的确定数字对行，列或区块进行排除，而是在不确定数字的具体位置的情况下进行排除的。【直观法】③区块排除法(BlockEliminationTechnique)从填入数字最多的中下区块入手，该区只有1和2还未填入。观察全局，[D2]=2，则第2列上不再出现数字2，所以[H2]和[I2]将不能填入2，这使得左下区块中数字2可能出现的位置仅剩下[I1]和[I3]。虽然无法确定2在左下区块中的确定位置，但能填入2的位置都在行I上，也就是说，无论2在[I1]还是在[I3]，行I的其他单元格中将不可能再出现数字2，所以可以排除在[I5]填入2的可能性。这样，对于中下区块，能填入数字2的位置就只剩下[H6]了。所以[H6]=2。【直观法】③区块排除法(BlockEliminationTechnique)在右上区块中，未填入数字的空单元格多达4个，但我们还是可以轻松地确定数字5的位置。【直观法】③区块排除法(BlockEliminationTechnique)在行C上，数字3的位置可以用区块除法来确定在这个示例中，只是使用单元排除法和单元唯一法到这一步就继续不下去了。要想求得数字8在第6列的位置，就必须要借助区块排除法。【直观法】③区块排除法(BlockEliminationTechnique)你能确定数字3在左上区块中的位置吗？这个例子同时使用了多个辅助区块同时参与排除。在实际使用中虽然这种情况并不常见，但却也不少见。关键在于如何能正确识别并恰当应用区块排除法。相信通过大量的练习并勤于分析思考，这种方法就可以运用自如，得心应手。【直观法】③区块排除法(BlockEliminationTechnique)【直观法】③区块排除法【直观法】④唯一余数法(SoleNumberTechnique)唯一余数法是直观法中较不常用的方法。虽然它很容易被理解，然而在实践中，却不易看出能够使用这个方法的条件是否得以满足，从而使这个方法的应用受到限制。单元格[G9]应该填入什么数字？就是如果某一单元格所在的行，列及区块中共出现了8个不同的数字，那么该单元格可以确定地填入还未出现过的数字。【直观法】⑤组合排除法(CombinationEliminationTechnique)组合排除法，和区块排除法一样，都是直观法中进阶的技法，但它的应用范围要更小一点。组合排除法，顾名思义，要考虑到某种组合。这里的组合既包括区块与区块的组合，也包括单元格与单元格的组合，利用组合的关联与排斥的关系而进行某种排除。它也是一种模糊排除法，同样是在不确定数字的具体位置的情况下进行排除的。你能确定数字6在中下区块中的位置吗？组合排除法的要满足的条件如下：1.如果在横向并行的两个区块中，某个数字可能填入的位置正好都分别占据相同的两行，则这两行可以被用来对横向并行的另一区块做行排除。2.如果在纵向并行的两个区块中，某个数字可能填入的位置正好都分别占据相同的两列，则这两列可以被用来对纵向并行的另一区块做列排除。【直观法】⑤组合排除法(CombinationEliminationTechnique)能确定数字1在中中块区中的位置吗？【直观法】⑤组合排除法(CombinationEliminationTechnique)实践中，组合排除法的实际应用机会不如区块排除法多。但是，掌握这一技法无疑可以大大提高求解谜题的灵活性，从而增加解题的乐趣。【直观法】⑥矩形排除法(RectangleEliminationTechnique）使用矩形排除法的条件如下：如果一个数字在某两行中能填入的位置正好在同样的两列中，则这两列的其他的单元格中将不可能再出现这个数字；如果一个数字在某两列中能填入的位置正好在同样的两行中，则这两行的其他的单元格中将不可能再出现这个数字。矩形排除法虽然浅显易懂，但应用较少。因为即使谜题中存在满足使用这一方法的情况，也很难直接看出来。然而，相对组合排除法而言，在解题过程中倒是能有更多的机会用上矩形排除法。能确定数字8在左下区块中的位置吗？【直观法】⑥矩形排除法(RectangleEliminationTechnique）做到这一步时，不用矩形排除法的话恐怕是走投无路了。这次是要在左下区块中找到数字4的位置。【直观法】⑥矩形排除法矩形排除法可以说是直观法中最困难的技法，因为当前的谜题即使满足应用这一方法的条件，也实在太难发现了。一般情况下，尽量先使用其他相对简单的直观法。如连矩形排除法都用上还是无法解题，你可能需要尝试候选数删减法了。【候选数法】对于解决数独谜题，最常使用的方法就是直观法和候选数法。在谜题相对简单时，直观法可以取得相当好的效果。但是如果谜题比较复杂，直观法的效果就十分有限，而候选数法却可以很好地发挥作用。在对数独谜题求解的电脑程序的设计上，候选数法也因为高效易实现而被广泛应用。如果用候选数法来解题，必须首先准备一张候选数栅格表：在候选数删减法中，常用的算法包括：显式唯一法(NakedSingle)隐式唯一法(HiddenSingle)区块删减法(IntersectionRemoval)显式数对法(NakedPair)显式三数集法(NakedTriplet)显式四数集法(NakedQuad)隐式数对法(HiddenPair)隐式三数集法(HiddenTriplet)隐式四数集法(HiddenQuad)矩形对角线法(X-wing)XY形态匹配法（XY-wing）XYZ形态匹配法（XYZ-wing)三链数删减法(Swordfish)WXYZ形态匹配法（WXYZ-wing)【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】【数独游戏】我们只要有相对锐利的眼光和一定的逻辑分析能力，就可以充分利用数独游戏规则，准确地把空余的数字逐个填出来。直观法(DirectEliminationTechniques)具有以下的特点：①轻松上手。即便是数独新手，在拿到谜题的一刹那，就可以用直观法来解题了。②无需辅助。在纸上解题时一般只需要一支钢笔就可以。因为是通过推理和逻辑分析来确定哪个格填哪个数，或是哪个数填在哪个格里，所以基本不需要猜测。③容易掌握。对于直观法中应用的各种算法，可以很快掌握并应用于实际中。④相对简单。比起候选数法，它的算法相对比较简单，当然能解决的谜题的复杂度也相对要低。在直观法中，常用的算法包括：单元唯一法、单元排除法、区块排除法、唯一余数法、组合排除法、矩形排除法【直观法】①显式唯一法(NakedSingle)【候选数法】这是候选数删减法中最简单的一种方法，就是扫描候选数栅格表，如果哪个单元格中只剩下一个候选数，就可应用显式唯一法，在该单元格中填入这个数字，并在相应行，列和区块的候选数中删除该数字。单元格[I1]有唯一的候选数1，则毫无疑问地把数字1填入该单元格中，并扫描其所在行，列和区块的候选数中有无数字1：如果有，则把1从这些单元格的候选数中删除：显式唯一法虽然简单，但却是最有效的候选数删减法之一；尤其在谜题相对简单时，有时单单使用显式唯一法就可以解题。②隐式唯一法(HiddenSingle)【候选数法】见文知义，隐式唯一法也是唯一候选数法的一种，但它肯定不如显式唯一法那样显而易见。我们知道，如果某一个单元格中只有一个候选数字，这时可以毫不犹豫地填入它；但是有没有这种情况，即使某个单元格中有不止一个候选数字，我们也可以轻易地推断出这个单元格的正确解答呢？考虑下面的情况：在第7列中，单元格[B7]中虽然有多个候选数，但观察整列后我们发现，只有这个单元格中有数字6。根据数独游戏的规则，每一列中都必须要有从1到9的所有数字，而同时6却只能出现在这个单元格中，所以很显然[B7]=6。当然，别忘了把6从[B7]所在的行，列和区块中删除。同样，在下图中：观察行B后我们发现，只有单元格[B8]中含有数字7。同理，[B8]是该行中唯一可以填入数字7的单元格，所以[B8]=7。另外，我们还要扫描相应行，列和区块，删除其中的候选数7。当然，这种隐藏的唯一候选数也可能躲在区块中，看下图：对于起始于[A1]的区块而言，数字8只出现在单元格[A2]的候选数中，所以[A2]=8。从相应行，列和区块，删除其中的候选数8。隐式唯一法是显式唯一法的有力补充，很多稍复杂的题都可以在这两种方法的交替使用下得以解决。③区块删减法(IntersectionRemoval)【候选数法】数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法