数独的起源编辑本段回目录
数独（日语：数独、 s ū doku ）是一种源自 18 世纪末的瑞士，后在美国发展、并在日本发扬光大的数学智力拼图游戏。拼图是九宫格（即 3 格宽× 3 格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上 1 至 9 的数字，让整个大九宫格每一列、每一行的数字都不重复。
数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。
如
今数独的雏型首先于 1970 年代由美国的一家数学逻辑游戏杂志发表，当时名为 Number Place 。现今流行的数独于 1984 年由日本游戏杂志Nikoli 《パズル通信ニコリ》发表并得了现时的名称。数独本是「独立的数字」的省略，因为每一个方格都填上一个个位数。
中国玩家可以访问数独游戏网：http://www.sudokus.cn/
数独的历史编辑本段回目录
■你知道是最先发明数独的吗？
1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。
■你知道是哪一本杂志最先推广数独的吗？
19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》 （Dell Puzzle Mαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”，在这个时候，9×9的81格数字游戏才开始成型。
■你知道“数独”这个游戏名称是怎么来的吗？
1984年4月，在日本游戏杂志《字谜通讯Nikoil》上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（SO DOKU），从此，这个游戏开始风靡全球。
解法举例编辑本段回目录
先注意其中一个方格，限定该方格内可以填写的数字。
注意其中一列（或者其中一个小九宫格），寻找填写某数字的方格。
学过“资料结构”的人，可以尝试用Backtrack试试。
数独的通解方法及步骤：
根据以下方法可以确保最终得到数独的解，而且通过手工运算的时间基本可以控制在1.5个小时，不论难易程度，所以此方法可以作为取得数独答案的一般解法。
1、根据横列、竖列和方格的限制条件排除各个点不可能的数字，并从1－9将各个可能的数字用小字体逐个写进每个空白的格子。（该步骤大约需要15－20分钟，这是求解的初始，务必确保没有遗漏）。
2、审视第一步骤的结果，如果发现某个空格只有一个数字，即确定该空格为这个数字。并根据该数字审视其相关的横列、竖列和方格，并划除相同的数字。（该情况出现的可能往往不多，除了较简单的数独题，但这是一个必要的过程，而且在随后的过程中要反复使用此方法。）
3、审视各个横列、竖列和方格中罗列出的可能的数字结果，若发现某一个数字在各个横列、竖列或方格中出现的次数仅一次，则可以确定该空格的解为此数字。并根据第二条的方法排除与此空格相关列或方格中相同的数字。
4、审视各个横列、竖列和方格中罗列的各个可能的结果，找出相对称的两个数组合的空格（或3个、4个组合），并确定这两个空格（或3个、4个）的数字只可能为这两个数字，即两个数字在这两个空格的位置可以交换，但不可能到该行、该列或该方格的其他位置。根据此结果可以排除相关列或方格罗列出相关数字的可能，并缩小范围。（该步骤处理的难度相对复杂，需要在积累一定经验的基础上进行，也是最终求解的关键）
5、反复使用2、3、4提到的步骤，逐步得到一个一个空格的解，并将先前罗列的各种可能的结果一个一个排除，使可能的范围越来越小，直至得到最后结果。
另外一种方法解初级的题目比较简单，就是：
1、把每一个横行里缺少的数字写到这一行的最右边。
2、把每一个竖列里缺少的数字写到这一列的最下边。
3、在刚才写的备选数字中，肯定有一个是行和列都缺的，这个数就可以填到里面去了。
4、如此反复第3步即可。
在线玩数独游戏地址：http://www.yx007.com/sdir/slist793c24.htm
经典益智游戏---数独
数独的历史
20世纪70年代，数独作为一种称为“数字拼图”的游戏开始出现在《Dell puzzle》书中。它实际上改编自“拉丁方”的数学概念，此概念可以追溯到中世纪，但18世纪的瑞士数学家莱昂哈德·欧拉最早对其进行了记录。“数字拼图”在美国并不是十分流行。但在1984年，数独落地日本并立即引起轰动。日本益智游戏出版商Nikoli的编辑Nobuhiko Kanamoto称其为“数字必须是单个”。后来简称为“数独”，意思是“单个数字”。
1997年，新西兰人韦恩·古尔德于日本旅行时发现了数独，并试图将其带到美国。他花了数年的时间编写计算机程序来生成迷题。古尔德将此益智游戏推介给《今日美国》，但遭到拒绝；但2005年4月被《纽约邮报》刊登。现在，数独已经出现在全球140种报纸上，移动电话用户甚至可以将数独益智游戏下载到其电话上。
数独的基础知识
数独是一种数字游戏，具体地说是数字 、1至9，但它真的跟数学关系不大。它与逻辑有关。除了数字1至9，您也可以使用字母表中的前9个字母或者包含9个符号的集合，它们都可以用来做同一个游戏。
数独的基础是一个九行九列的网格。您需要考虑三个部分：行、列和方框。
数独的要求是使用数字1至9填写每个包含9个方格的行、每个包含9个方格的列及每个包含9个方格的方框，且每个数字在每个部分只能使用一次。根据行、列和方框的交叉位置可判断出将填写数字的位置。因此，假设从一个空白的网格开始，需要根据数独规则在第1行、第2列及第4个方框中填入数字，则其大概情形如下：
第1行中每个数字仅出现一次，第2列和第4个方框与第1行的情况相同，尽管这些部分相互重叠。
当然，从一个空白的网格开始也不会增加多少难度。不过，对于已经填写了一些数字的数独益智游戏，您所要做的就是确定其他数字的填写位置。下面是一个真正的数独益智游戏的例子。
这是一个已填写了一些“线索”难度定级为
简易的数独益智游戏。
数独有多个难度级别，从容易到非常难，具体取决于用几个数字开始以及这些数字所在的位置。Michael Mepham作为伦敦《每日电讯报》的益智游戏创作人，将他的益智游戏（迷题）划分为以下等级：简易、中等、较难和最难。简单的迷题会在足够多的关键位置上放置足够多的数字，这样只需运用简单的逻辑就可以找到答案。每个迷题只有一个答案。
了解数独魅力的最好方法就是自己解答一个迷题。现在让我们解答一下上面的简单迷题，体会一下解答迷题的感觉。如果简单的迷题可以解答，那么复杂的也可以，只不过是更费时一些。
解答数独迷题
数独迷题并没有一个正确的开始位置。您可以闭上眼睛，将手指放在迷题上的任意位置从该处开始，就可以说这就是一个正确的位置。但是，从逻辑上看，最合理的开始位置是其中已填写了很多数字的某一行、列或方框。让我们看一下上页中的迷题：
第4列和第6列已经各填入了6个数字。让我们从第4列开始此迷题，此列已填好数字1、3、4、5、8和9。
因为1至9中的每个数字只能使用一次，所以我们只能在第4列中填入2、6和7。但是我们又不能将这些数字房子任意位置，因为在迷题的答案中，每一个数字都有一个特定的位置。该将各个数字填在哪里呢？为了找到答案，我们需要看一下与第4列交叉的行和方框。看一下位于第3行第4列（3,4）的空方格，以及与其交叉的行和方框：
为了填写位于第3行第4列的空方格，我们需要看一下第4列、第3行及第2个方框。
数独的简单的逻辑方法仅仅需要进行视觉分析，类似于：数字2能不能放在空方格中？不能，因为第2个方框已经有一个2了，而每个数字在每个方框中只能填一次。那么7能不能放在这里？第3行已经有一个7了，因此我们也不能将7放在这里。那么就剩下6了。第3行和第2个方框都没有6，所以我们知道，将6放在此单元格是正确的。我们已经填入了第一个数字！
将6放在此单元格是正确的。我们已经填入了第一个数字！
现在，我们看看如何填写第4列的其余位置，第4列还需要2和7。位于（5,4）的空方格与第5行和第5个方框交叉，而位于（7,4）的空方格与第7行和第8个方框交叉。
由于第5个方框中已经有一个7了，因此不能将7填入（5,4）方格中。这样，我们知道必须将2填入（5,4）方格，而将7填入（7,4）方格：
这样，我们就完成了第4列的全部数字，并且只用了简单的逻辑便完成了。由于这是一个简单的迷题，因此用这种方法可以填入大部分方格。但有时候迷题并非这样清楚。在答案不是很明显时，我们可以运用一些策略，而这些策略的根本，就是用铅笔做一些标记。
可能的数字
当数独迷题变得越来越难时，在一些空方格中用铅笔填入一些可能的数字变得很重要。但用铅笔标记的时候，并不是在猜数字。只是列举可能的答案。在玩数独时您不应该猜，否则，由于一切都是相互关联的，到最后您可能将整个迷题混成一团，这样您将不得不重新开始游戏。
为特定行、列或者方框中的每个方格用铅笔标记下所有可能的数字，我们就可以使用特定的策略将数字填入相应区域。现在我们看看第7行，它有四个空方格，需要填入数字4、5、6和9。
我们将用铅笔分别填入每个空方格的所有可能数字。那么，在数字4、5、6和9 中，哪一个可能适合（7,2）空方格？数字4不行，因为第2列已经有一个4了。5是可能的，因为第2行和第7个方框都还没有5。数字6也要排除，因为第7个方框已经有一个6了。但是9可以填在这里，因为第2行和第7个方框都没有9。因此我们用铅笔将“5 9”填入此方格：
按照同样的过程填写（7,5）方格，我们可以排除4和9（第8个方框中已经有这两个数字了），用铅笔填入5和6。至于（7,6）方格，我们也用铅笔填入5和6。剩下（7,8）方格，可以填入任何数字：
现在再看看您已经用铅笔填入的数字，您将注意到两件事情：首先，有两个方格中有相同的一对数字（并且仅有这两个数字）；其次，4只出现了一次。我们现在从只出现在（7,8）方格中的4开始。使用我们将称为“出现一次”的策略，我们知道，如果4只能填入（7,8）方格，那么我们已经填好此方格，因为第7行需要一个4。第7行如下所示：
现在，我们看看重复的那一对：5和6（且仅限5和6）均能填入方格（7,5）和（7,6）。此时我们得到的是一组配对。5必须填入这两个方格中的一个，而6也必须填入这两个方格中的一个。使用配对策略，现在我们可以将5从方格（7,2）排除，因为我们知道5是不能填在那里的。这样，我们又填好了一个方格：
与此类似，“配对”排除策略也可以作为“匹配三元组”使用，也就是说您有三个方格具有同一组（三个一组）数字，并且每个方格中，只有这一组（三个一组）数字。
从我们已经用铅笔填入的数字来看，我们仍然不知道5应在哪个方格，6应在哪个方格，因此我们将用铅笔填入更多的数字。现在我们看看如何处理第8个方框，这个方框中有四个空方格，需要填入数字1、2、5和6。
其中已经有两个方格用铅笔填入了配对数字5和6，因此我们知道，在其他方格中，就可以将5和6从其他方框的可能答案中排除。这样就剩下1和2。这两个数字中任一个都可以填入方格（8,5），因为第8行和第5列中都没有1或2。但是第9行有一个2，因此我们不能将2填入方格（9,5）。看一下我们已经填入的部分：
注意到什么了吗？方格（9,5）中只有一个数字。使用Mepham所谓的孤数策略（可能是数独中最简单的策略了），我们知道1是方格（9,5）的答案。因为第8个方框中的1已经在（9,5）中，所以我们从方格（8,5）排除已填入的1，这样就只剩下一个2了——又解答了一个方格。
但是我们仍然不知道数字5和6的正确位置。解答第6列就会知道方格（7,6）中应填入的数字。第6列有三个空方格，其中有一个方格已经填入了所有可能的答案：
第6列需要填入数字1、5和6。对于方格（3,6），1和5是可能的答案（第3行已经有一个6了）。对于方格（5,6），唯一可能的答案是6，因为第5个方框已经有1和5了。
现在我们知道，方格（7,6）中只能填入5，方格（3,6）中只能填入1，而方格（7,5）中只能填入6。
由于行、列和方框之间的交叉是数独的关键所在，因此解答一个方格便可立即得出其他五个答案。到现在为止，我们已经运用了简单的逻辑，并且为给定的方格找到了一些可能的数字。在下一部分，我们将使用另外一种方法：为给定数字找到可能的方格。
生成数独：涉及数学
数独迷题是计算机生成的。在生成的过程中涉及到不少数学知识。
数独网格是一种拉丁方，即由按方格形状排列的数字（符号或字母）模式组成的数学对象，在整个方格中，每一个数字在每一行和每一列中仅出现一次。对于由9个数字组成的拉丁方，共可以生成 5,524,751,496,156,892,842,531,225,600个数字网格。但是由于数独除了体现拉丁方的9个数字以外，还增加了3x3的方框，因此仅可以生成6,670,903,752,021,072,936,960个数独网格。计算机程序会分析种种可能性，并以决定迷题难度的预设算法为基础，使用已有的某些数字和缺少的其他数字建立数独网格。
正确的方格和最难的迷题
这一次，我们不是为某一个方格寻找正确的数字，而是为某一个数字找到正确的方格。要实现此目的，我们需要画一些线。看一下第6个方框：
第6个方框需要一个4。现在让我们通过排除其不能出现的方框，找到它应该出现的位置。第5行中有一个4，因此我们将在这一行画一条线。同时第6行和第7及8列中都有一个4。我们也要分别在这些行和列中画线。
现在第6个方框中只有一个空方格，即方格（4,9），我们已经知道了4应填入的方格。
现在，我们通过画更多的线来找到数字6的填入位置。我们在第5行、第6行和第9列各画一条线，这样就只剩一个空方格了。可以将6填入方格（4,8）中。
现在您已经了解了自己解答迷题所需要的全部知识。
使用我们刚才讨论的简单逻辑和基本策略，还有数独爱好者开发的成千上万种其他策略，您将能够解决任何数独迷题。随着难度的增加，您需要的只是花费更长的时间，来求得每个方格的答案，因为有些方格只有在您求得其他特定方格的答案后才能确定其答案，有时候甚至要等你填完所有其他方格后才能确定。随着您玩的迷题越来越多，您将会得出自己的一套方法和策略。归根结底就是发现和培养你自己的数独逻辑感觉。
虽然数独是一种逻辑游戏，但是有些迷题却与逻辑思维背道而驰，而需要猜测，这对那些数独纯化论者而言，简直就是一件恐怖的事情。
最难的数独
现在，伦敦《每日电讯报》上Michael Mepham定级为最难级别的一些数独，仅运用逻辑思维已不能解答。从某种程度上看，这确实需要猜测，而这些在纯化论者眼里，是完全不可取的。鉴于收到的大量抗议和恶意中伤的信件，Mepham已经停止发布那些需要猜测才能完成的迷题。只要解答迷题还是这样的过程——在您开始猜测过程之前，必须获得足够的了解以便绝对确信再也没有线索了，那么解答这些迷题的过程仍然是有趣的。Mepham称此策略为阿里阿德涅之线（见注解），这种方法需要为某一给定方格选择两个可能的答案之一，然后一直往下解答，直到您找到真正的答案或者陷入僵局。如果您陷入僵局，则折回到这个猜测点并选择其他的数字。
在Michael Mepham的《Book of Sudoku 3》中，其中有一个很难的数独是这样开始的：
运用逻辑思维，您能得到下图所示的答案：
至此，实在没有更多的逻辑线索了，就此卡壳。现在我们唯一的选择就是猜测，并忽略我们用铅笔标记的数字，这样在证明猜测错误时，可以沿着这条“阿里阿德涅之线”重新回到我们的开始点。在只有两个选择的情况下选择某个方格，此时选对正确数字的几率是50%。现在我们回到第2行第1列并选择4。假设4是方格（2,1）的答案，那么我们通过扩展就可以得出很多其他方格的答案，但是我们最后会碰到一个问题。
如果方格（1,7）的答案是4，那么方格（6,7）的正确数字就应该是5。但是第6行已经有一个5。因此需要擦去刚才猜得的答案，回到方格（2,1）。这一次我们将选择5。
5确实是方格（2,1）的答案，它能帮助我们解答整个迷题。
虽然Mepham已经停止在其专栏中发布那些需要猜测才能完成的数独迷题，但是你仍然可以从Mepham的数独网站sudoku.org.uk访问这类迷题。
随着数独风日渐兴盛，已经涌现了很多不同的版本，用以制造难度更大的迷题。有一种“极限数独”是三维数独。只需将九个完整的数独网格排成一个三维立方体，就出现了一个三维数独迷题，这个三维立方体要求在三个互连的轴上有完整的行、列和方框。所有的规则都适用，但是你现在需要在多个平面上填入数字。为了将数字填入这个立方体，你需要分别为这9个网格找到答案。但是如果你下载了一个三维数独计算机程序（有十几个这样的程序），您就可以在完整的三维美景中完成这个迷题。
注：阿里阿德涅之线
在希腊神话中，克里特国王米诺斯要求人们为他养在迷宫中的怪物充当祭品。而年轻的骑士特修斯决定毁灭这个怪物，巧的是国王的女儿阿里阿德涅爱上了特修斯。她为特修斯设计了一条最安全的路线，这样一旦他将这个怪物杀死后，就可以沿着这条路回去：特修斯在去迷宫的路上边走边放线。这样，当他进入死胡同时，将根据手中的线返回原来的位置并选择另一条线路。当他到达怪物所在地时，这根线就标记了完整的踪迹，从而可以直接引导他走出迷宫。
