九宫格数独，是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。这种游戏全面考验做题者观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独是训练头脑的绝佳方式。

数独的历史(元素构成 规则)

基本解法举例(基础摒除法 唯一解法 唯余解法 区块摒除法 余数测试法 唯一候选数法 隐性唯一候选数法 候选数区块删减法 候选数对删减法 隐性候选数对删减法 三数集删减法 三链数删减法 隐性三链数删减法 矩形顶点删减法 三链列删减法 关键数删减法)

变形数独概述

靶形数独(Noip2009赛题 问题描述 输入数据 输出数据 样例输入 样例输出 数据规模 解题报告 代码清单（pascal实现）)

数独的近亲

给出最少数字且有唯一解的数独

求解数独的程序代码

数独的段位以及评选方法

数独单元格的叫法

玩数独的好处

数独的历史

数独是一种源自18世纪末的瑞士（具体在1886年），后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。

数独的基础是数字魔方，它的解也一定是数字魔方。制作一个数独，便是使用一个一般的数字魔方，盖住部分数字，成为一个拥有唯一解的数独。数独是现在最流行，最时尚的游戏。流行度甚至超过了俄罗斯方块。

数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。中国古籍《易经》中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。 现在已有多种手机装有数独游戏。

1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”（Latin Square）的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。

19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（Dell Puzzle Mαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”（Number Place），在这个时候，9×9的81格数字游戏才开始成型。1984年4月，在日本游戏杂志《字谜通讯Nikoil》（《パズル通信ニコリ》）上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是唯一的”，并将这个游戏命名为“数独”（sudoku）。

一位前任香港高等法院的新西兰籍法官高乐德（Wayne Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。从此，这个游戏开始风靡全球。后来更因数独的流行衍生了许多类似的数学智力拼图游戏，例如：数和、杀手数独。

中国大陆是在2007年2月28日正式引入数独. 2007年2月28日，北京晚报智力休闲数独俱乐部(数独联盟sudokufederation前身)在新闻大厦举行加入世界谜题联合会的颁证仪式，会上谜题联合会秘书长皮特-里米斯特和俱乐部会长在证书上签字，这标志着北京晚报智力休闲俱乐部成为世界谜题联合会的39个成员之一，这也标志着俱乐部走向国际舞台，它将给数独爱好者带来更多与世界数独爱好者们交流的机会。数独书籍是现在非小说类畅销书榜首！

元素构成

单元格：数独中最小的单元，标准数独中共有81个

行：横向9个单元格的集合

列：纵向9个单元格的集合

宫：粗黑线划分的区域，标准数独中为3×3的9个单元格的集合

已知数：数独初始盘面给出的数字

候选数：每个空单元格中可以填入的数字。

规则

标准数独的规则为：数独每行、每列及每宫填入数字1-9且不能重复。

基本解法举例

数独解法全是由规则衍生出来的，基本解法分为两类思路，一类为直观法，一类为候选数法。更复杂的解法，最终也会归结到这两大类中。 下边以图示简单介绍几种解法，只要你花几分钟看一遍，马上就可以开始做数独了。

基础摒除法

基础摒除法就是利用1 ～ 9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。

实际寻找解的过程为：

寻找九宫格摒除解：找到了某数在某一个九宫格可填入的位置只余一个的情形；意即找到了 该数在该九宫格中的填入位置。

寻找列摒除解：找到了某数在某列可填入的位置只余一个的情形；意即找到了该数在该列中的填入位置。

寻找行摒除解：找到了某数在某行可填入的位置只余一个的情形；意即找到了该数在该行中的填入位置。

基础摒除法的提升方法是区块摒除法,是直观法中使用频率最高的方法之一。

基础摒除法是直观法中最常用的方法，也是在平常解决数独谜题时使用最频繁的方法。单元排除法使用得当的话，甚至可以单独处理中等难度的谜题。

使用单元排除法的目的就是要在某一单元（即行，列或区块）中找到能填入某一数字的唯一位置，换句话说，就是把单元中其他的空白位置都排除掉。

那么要如何排除其余的空格呢？当然还是不能忘了游戏规则，由于1-9的数字在每一行、每一列、每一个九宫格都要出现且只能出现一次，所以：

如果某行中已经有了某一数字，则该行中的其他位置不可能再出现这一数字

如果某列中已经有了某一数字，则该列中的其他位置不可能再出现这一数字

如果某区块中已经有了某一数字，则该区块中的其他位置不可能再出现这一数字。

唯一解法

如果某行已填数字的单元格达到8个,那么该行剩余单元格能填的数字就只剩下那个还没出现过的数字；同理，如果某列已填数字的单元格达到8个，那么该列剩余单元格能填的数字就只剩下那个还没出现过的数字；如果某九宫格已填数字的单元格达到8个,那么该九宫格剩余单元格能填的数字就只剩下那个还没出现过的数字。

这应该算是直观法中最简单的方法了。基本上只需要看谜题，推理分析一概都用不上，这是因为要使用它所需满足的条件十分明显。同样，也正是因为它简单，所以只能处理很简单的谜题，或是在处理较复杂谜题的后期才用得上。

唯余解法

唯余解法就是某宫格可以添入的数已经排除了8个，那么这个宫格的数字就只能添入那个没有出现的数字.

唯余解法是直观法中较不常用的方法。虽然它很容易被理解，然而在实践中，却不易看出能够使用这个方法的条件是否得以满足，从而使这个方法的应用受到限制。

与唯一解法相比，唯余解法是确定某个单元格能填什么数的方法，而唯一解法是确定某个数能填在哪个单元格的方法。另外，应用唯一解法的条件十分简单，几乎一目了然。

区块摒除法

区块摒除法是基础摒除法的提升方法,是直观法中使用频率最高的方法之一. 区块摒除法是直观法中进阶的技法。虽然它的应用范围不如基础摒除法那样广泛，但用它可能找到用基础摒除法无法找到的解。有时在遇到困难无法继续时，只要用一次区块摒除法，接下去解题就会势如破竹了。

当某数字在某个九宫格中可填入的位置正好都在同一行上，因为该九宫格中必须要有该数字，所以这一行中不在该九宫格内的单元格上将不能再出现该数字。

当某数字在某个九宫格中可填入的位置正好都在同一列上，因为该九宫格中必须要有该数字，所以这一列中不在该九宫格内的单元格上将不能再出现该数字。

当某数字在某行中可填入的位置正好都在同一九宫格上，因为该行中必须要有该数字，所以该九宫格中不在该行内的单元格上将不能再出现该数字。

当某数字在某列中可填入的位置正好都在同一九宫格上，因为该列中必须要有该数字，所以该九宫格中不在该列内的单元格上将不能再出现该数字。

区块摒除法实际上是利用区块与行或列之间的关系来实现的，这一点与基础摒除法颇为相似。然而，它实际上是一种模糊排除法，也就是说，它并不象基础摒除法那样利用谜题中现有的确定数字对行，列或九宫格进行排除，而是在不确定数字的具体位置的情况下进行排除的。

余数测试法

所谓余数测试法就是在某行或列，九宫格所填数字比较多,剩余2个或3个时，在剩余宫格添入值进行测试的解题方法.

唯一候选数法

唯一候选数法是候选数删减法中最简单的一种方法，就是通览所有单元格的候选数列表，如果哪个单元格中只剩下一个候选数，就可应用唯一候选数法，在该单元格中填入这个数字，并在相应行，列和九宫格的其它单元格候选数列表中删除该数字。

隐性唯一候选数法

顾名思义，隐式唯一候选数法也是唯一候选数法的一种，但它不如显式唯一候选数法那样显而易见。

当某个数字在某一列各宫格的候选数中只出现一次时，那么这个数字就是这一列的唯一候选数了．这个宫格的值就可以确定为该数字． 这是因为，按照数独游戏的规则要求每一列都应该包含数字1～9，而其它宫格的候选数都不含有该数，则该数不可能出现在其它的宫格，那么就只能出现在这个宫格了． 对于唯一候选数出现行,九宫格的情况，处理方法完全相同。

由于1-9这9个数字要在每行、每列和每个九宫格内至少出现一次，所以如果某个数字在某行、某列或是某个九宫格内所有单元格的候选数列表中只出现一次，那么这个数字就应该填入它出现的那个单元格内，并且从该格所在行、所在列和所在九宫格内其它单元格的候选数列表中删除该数字。

候选数区块删减法

候选数区块删减法也是比较常用的方法，它的目的是尽量删减候选数，而不一定要生成某一单元格的唯一解（当然，产生唯一解更好）。候选数区块删减法是利用九宫格中的候选数和行或列上的候选数之间的交互影响而实现的一种删减方法。

在某一九宫格中，当所有可能出现某个数字的单元格都位于同一行时，就可以把这个数字从该行的其他单元格的候选数中删除。

在某一九宫格中，当所有可能出现某个数字的单元格都位于同一列时，就可以把这个数字从该列的其他单元格的候选数中删除。

在某一行（列）中，当所有可能出现某个数字的单元格都位于同一九宫格中时，就可以把这个数字从该九宫格的其他单元格的候选数中删除。

候选数对删减法

选数对删减法依据的原理是数字1-9在同一行、同一列和同一九宫格内不能出现2次或2次以上。这样，如果在同一行、同一列和同一九宫格内两个单元格的候选数列表都是{a,b}，那么如果其中一个单元格填入的数字为a，另一个单元格填入的数字就应该是b；反之，如果其中一个单元格填入的数字为b，另一个单元格填入的数字就应该是a。也就是说，a,b两个数字就应该分别填入这两个单元格，所以该行、该列或是该九宫格内其它单元格就不应该再填入数字a和b。

所以候选数对删减法就是：在一个行、列或九宫格中，如果有两个单元格都包含且只包含相同的两个候选数，则这两个候选数字应该从该行、该列列或该九宫格的其他单元格的候选数列表中删去。

隐性候选数对删减法

隐性候选数对删减法依据的原理是数字1-9在同一行、同一列和同一九宫格内至少要出现一次。这样，如果某两个数字a和b在同一行、同一列和同一九宫格内只在两个单元格的候选数列表中出现，那么该行、该列或是该九宫格内其它单元格就不应该再填入数字a和b，所以a和b只能在这两个单元格中出现，所以这两个单元格的候选数列表就都应该是{a,b}，可以将其他的数字从这两个单元格的候选数列表中删去。

所以隐性候选数对删减法就是：在同一行，列或区块中，如果一个数对（两个数字）正好只出现且都出现在两个单元格中，则这两个单元格的候选数中的其他数字可以被删除。

三数集删减法

三数集删减法的原理类似于候选数对删减法。候选数对删减法要求同样的2个数字都出现在某行、列或九宫格的2个单元格中，且这2个单元格的候选数不能包含其他的数字。同样，三数集删减法要求的是3个数字要出现在3个位于同一行、列或九宫格的单元格中，且这3个单元格的候选数中不能包含其他数字。但不同的是，三数集删减法不要求每个单元格中都要包含这3个数字。例如，对于数字集{2,4,5}，如果在某行，列或区块中有3个单元格的候选数分别为下面几种情况时，都可应用三数集删减法：

{2, 4, 5}、{2, 4, 5}、{2, 4, 5}

{2, 4}、{4, 5}、{2, 5}

{2, 4, 5}、{2, 5}、{4, 5}

{2, 4, 5}、{4, 5}、{2, 4, 5}

……

也就是说，要形成三数集，则必须要有3个在同一行、列或九宫格中的单元格，每个单元格中至少要有2个候选数，且它们的所有候选数字也正好都是一个三数集的子集。这个三数集中的3个数字只能填入这3个单元格中，所以该行、列或九宫格中其他的单元格中不可能再填入这3个数字。

但要注意的是，{2, 4, 5}、{2, 4}、{2, 4}这种情况不是三数集。其中{2, 4}和{2, 4}可应用候选数对删减法，所以第一个候选数列表{2, 4, 5}将只能剩下候选数5，这时就可应用唯一候选数法了。

三链数删减法

找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形， 进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。

隐性三链数删减法

在某行，存在三个数字出现在相同的宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数．那么这三个宫格的候选数中的其它数字都可以排除．

当隐形三链数出现在列，九宫格，处理方法是完全相同的．

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

修改为：在某行，存在三个候选数字分别出现在三个宫格内，

在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数．那么这三个宫格的其它候选数都可以排除．

当隐形三链数出现在列，九宫格，处理方法是完全相同的

或者： 利用“找出某3个数字仅出现在某行、某列或某一个九宫格的某三个宫格候选数中的情形，进而将这三个宫格的候选数删减成该3个数字”的方法就叫做隐性三链数删减法(Hidden Triples)。

矩形顶点删减法

矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶点删减法在识别时比较不容易找到，所以最好先使用其它的方法。

三链列删减法

三链列删减法是矩形顶点删减法的扩展，如果不清楚矩形顶点删减法，可以参考矩形顶点删减法，以便于更容易理解本节内容。 利用“找出某个数字在某三列仅出现在相同三行的情形，进而将该数字自这三行其他宫格候选数中删减掉”； 或“找出某个数字在某三行仅出现在相同三列的情形，进而将该数字自这三列其他宫格候选数中删减掉”的方法 就叫做三链列删减法。

关键数删减法

在进入到解题后期，利用前面讲到的唯一候选数法、隐性唯一候选数法、 区块删减法、数对删减法、隐性数对删减法、 三链数删减法、隐性三链数删减法、矩形顶点删减法、 三链列删减法都无法有进展的时候，可以考虑使用关键数删减法。关键数删减法就是在后期找到一个数，这个数在行（或列，九宫格）仅出现两次的数字。我们假定这个数在其中一个宫格类，继续求解，如果发生错误，则确定我们的假设错误。如果继续求解仍然出现困难，不妨假设这个数在另外一个宫格，看能不能得到错误。这就是关键数删减法.

全删掉 不要本段

变形数独概述

数独发展到今天，类型已经多种多样，如果按不同条件细分绝不下百种，而且数量还在增加中。大家平时可以常见的变形数独，如：对角线数独、锯齿数独、杀手数独等等。所谓变形数独，即改变一些标准数独的条件或规则，形成的新型数独题目，有的变形数独也会同时具备多种变形条件，变形条件如下：

1.使用数字的数量不同可以有4字数独、6字数独、16字数独、25字数独等等

2.增加限制区域的类别可以有对角线数独、额外区域数独、彩虹数独等等

3.宫形发生变化有锯齿数独；多个数独叠加起来有连体数独、武士数独、超级数独等等

4.用其它元素代替已知数字有字母数独、骰子数独（6字）、数码数独等等

5.利用单元格内数字之和或乘积等关系有杀手数独、边框数独、魔方数独、算式数独等等

6.利用相邻单元格内数字的关系有连续数独、不等号数独、堡垒数独、XV数独、黑白点数独等等

7.单元格限制数字属性有奇偶数独、大中小数独等等

8.利用数独外提示数字有边缘观测数独、摩天楼数独等等

9.按禁止同一数字位置有无缘数独、无马数独等等

10.非方形数独有圆环数独、立方体数独、六角数独、蜂窝数独等等

11.需要多个数独条件配合才能解题的有三合一数独、双胞数独等等。

以上11种分类并非全部变化条件，只是常见的大类，还有不少变形数独未举例，其实变形的条件不会有极限的，只要你有想象力，可以创造出属于你自己的新型变形数独。虽然数独条件变换多端，但有一条始终不变的 绝对条件——同一限制区域内不能出现重复数字。只要符合这个条件，就没有脱离“数独”的范畴。

靶形数独

Noip2009赛题

Noip2009提高组复赛最后一题：靶形数独。

靶形数独

(sudoku.pas/dpr/c/cpp)

考察搜索顺序优化，预处理出所有结点的决策，卡时搜索方法。

问题描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z博士请教，Z 博士拿出了他最近发明的“靶形数独” ，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的） 。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。

上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。

比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法） ，而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

输入数据

一共 9 行。每行 9 个整数（每个数都在 0—9 的范围内） ，表示一个尚未填满的数独方格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。

输出数据

输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

样例输入

7 0 0 9 0 0 0 0 1

1 0 0 0 0 5 9 0 0

0 0 0 2 0 0 0 8 0

0 0 5 0 2 0 0 0 3

0 0 0 0 0 0 6 4 8

4 1 3 0 0 0 0 0 0

0 0 7 0 0 2 0 9 0

2 0 1 0 6 0 8 0 4

0 8 0 5 0 4 0 1 2

样例输出

2829

数据规模

40%的数据，数独中非0数的个数不少于 30。

80%的数据，数独中非 0数的个数不少于 26。

100%的数据，数独中非 0 数的个数不少于 24。

解题报告

首先进行最原始的数独搜索，我们可以开3个标记数组

heng,shu,box:array[0..9,0..9] of boolean;

我们每次就填入数字可以进行如下判断

if (heng[x,i]=false) and (shu[y,i]=false) and (box[((x-1) div 3)*3+((y-1) div 3)+1,i]=false) then

这次的数据我们倒的搜索要比正的搜索效率高

对于完全不加优化的程序期望分值为70分

如果加上卡时间的操作，期望得分95分

如果随机化搜索顺序，期望得分100分

如果加入启发函数信息，期望得分100分

代码清单（pascal实现）

program sudoku;

const value:array[1..9,1..9] of integer=((6,6,6,6,6,6,6,6,6),

(6,7,7,7,7,7,7,7,6),

(6,7,8,8,8,8,8,7,6),

(6,7,8,9,9,9,8,7,6),

(6,7,8,9,10,9,8,7,6),

(6,7,8,9,9,9,8,7,6),

(6,7,8,8,8,8,8,7,6),

(6,7,7,7,7,7,7,7,6),

(6,6,6,6,6,6,6,6,6));

type node=record

juece:array[0..9] of integer;

square,lie,hang:integer;

end;

var way:array[1..81] of node;

temp:node;

find:boolean;

i,j,k,w,point,bestpoint:integer;

square,lie,hang:array[1..9,1..9] of boolean;

map:array[1..9,1..9] of integer;

function fs(i,j:integer):integer;

begin

if (i<=3) and (j<=3) then fs:=1;

if (i<=3) and (j>=4) and (j<=6) then fs:=2;

if (i<=3) and (j>=7) then fs:=3;

if (i>=4) and (i<=6) and (j<=3) then fs:=4;

if (i>=4) and (i<=6) and (j>=4) and (j<=6) then fs:=5;

if (i>=4) and (i<=6) and (j>=7) then fs:=6;

if (i>=7) and (j<=3) then fs:=7;

if (i>=7) and (j>=4) and (j<=6) then fs:=8;

if (i>=7) and (j>=7) then fs:=9;

end;

procedure search(i:integer);

var k:integer;

begin

if i=82 then

begin

if point>bestpoint then bestpoint:=point;

find:=true;

exit;

end;

if way[i].juece[0]=0 then search(i+1);

for k:=1 to way[i].juece[0] do

if not hang[way[i].hang,way[i].juece[k]] and not lie[way[i].lie,way[i].juece[k]] and not square[way[i].square,way[i].juece[k]] then

begin

hang[way[i].hang,way[i].juece[k]]:=true;

lie[way[i].lie,way[i].juece[k]]:=true;

square[way[i].square,way[i].juece[k]]:=true;

point:=point+way[i].juece[k]*value[way[i].hang,way[i].lie];

search(i+1);

hang[way[i].hang,way[i].juece[k]]:=false;

lie[way[i].lie,way[i].juece[k]]:=false;

square[way[i].square,way[i].juece[k]]:=false;

point:=point-way[i].juece[k]*value[way[i].hang,way[i].lie];

end;

end;

begin

point:=0;

bestpoint:=0;

find:=false;

assign(input,'data\\sudoku\\sudoku1 in');

reset(input);

for i:=1 to 9 do

begin

for j:=1 to 9 do

begin

read(map[i,j]);

if map[i,j]>0 then

begin

point:=point+map[i,j]*value[i,j];

hang[i,map[i,j]]:=true;

lie[j,map[i,j]]:=true;

square[fs(i,j),map[i,j]]:=true;

end;

end;

readln;

end;

close(input);

for i:=1 to 9 do

for j:=1 to 9 do

begin

way[(i-1)*9+j].hang:=i;

way[(i-1)*9+j].lie:=j;

way[(i-1)*9+j].square:=fs(i,j);

w:=0;

way[(i-1)*9+j].juece[0]:=w;

if map[i,j]=0 then

begin

for k:=1 to 9 do

if not hang[i,k] and not lie[j,k] and not square[fs(i,j),k] then

begin

inc(w);

way[(i-1)*9+j].juece[0]:=w;

way[(i-1)*9+j].juece[w]:=k;

end;

end;

end;

for i:=1 to 80 do

for j:=1 to 81-i do

if way[j].juece[0]>way[j+1].juece[0] then

begin

temp:=way[j+1];

way[j+1]:=way[j];

way[j]:=temp;

end;

search(1);

assign(output,'dataout\\sudoku.out');

rewrite(output);

if not find then writeln('-1')

else writeln(bestpoint);

close(output);

end.

数独的近亲

谜题（Pazzle）：排除文化差异对做题者的影响，只用数字和图形表示的逻辑推理游戏。

数独是谜题（Pazzle）中的一个分支，由于其规则简单、种类众多从而从众多谜题脱颖而出，成为大众熟知的数字谜题。

不过除了数独以外，还有不少谜题也非常出色，也有众多的拥护者，而且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理游戏。下面简单介绍几类谜题：

数和（Kakuro）：与杀手数独很像的一类谜题，规则要求同行、同列（同一段）数字不能重复，且每段数字之和等于左边和上边的提示数字。

数图（Nonograms\\Griddlers)：根据盘面周围的数字提示，把盘中涂成符合条件的图案，很像“十字绣”。

数回（Slither Link）：游戏由0,1,2,3四个数字组成。每一个数字，代表四周划线的数目，并在最后成为一个不间断、不分岔的回路。

数墙（Nurikabe）：数墙的世界，是一个非黑即白的二元世界；在游戏中，你要决定的是，那些格子需要涂黑，那一些应该留白。

数连（Number Link）：与数独一样，数连是一个简单明快的游戏。你只需要把属于相同数字的同伴，以线连接起来。不过，这个游戏看起来非常简单，实际上是很有深度的。

图独（tudoku）：数独的一种扩展，将数字换成有趣的图形，看似一样，但换成图形后大大增强了数独趣味性，使游戏不会那么枯燥，很合适小孩子玩，即动脑又锻炼记忆力。

给出最少数字且有唯一解的数独

数独初盘最少可以有17个数。

与数独终盘相对应，一个数独游戏给出的初始条件称为初盘。由于规则所限，给出的初盘数字个数必须在32以下。

一般常见的初盘数字个数在22—28之间，而数独爱好者们常问的一个问题是：最少给出多少个数字，数独游戏才确保有唯一解？具体地说：最少需要在初盘中给出多少个数字，使得移除其中任何一个数字该数独游戏便没有唯一解。

事实上，这个问题是数独中最有数学趣味的问题之一，并且至今仍未得到解决。但数学家们估计，这个数字很可能是17.17个数字的最小唯一解初盘是由一名日本数独爱好者发现的。澳大利亚数学家GordonRoyle已经收集了36628个17个数字的唯一解初盘，而爱尔兰数学家Gary McGuire则致力于寻找16个数字的唯一解初盘，但至今仍无发现。部分数学家开始退而求其次，转而寻找只有两个解的17个数字初盘。

统计学家根据一个统计学原理曾随机地构造了大量17个数字的初盘，发现其中有唯一解的初盘只有数个未被GordonRoyle教授发现，这意味着，最小唯一解初盘问题的最终答案可能正是17：因为从理论上说，如果16个数字的唯一解终盘存在，那么每一个必将引起65个17个数字唯一解终盘的增加，而在研究中至今没有观察到这一效应。

求解数独的程序代码

求解数独所有解（适合所有数独）的PASCAL程序

var a:packed array[1..9,1..9] of longint;

i,j,k,p,l,m,n,ii,ans,mm,oo:longint;

s,s1:packed array[0..100,1..4] of longint;

x,y,xy:packed array[0..9,-1..9] of boolean; //横向，纵向，九宫的检验

t,tt,u:boolean;

opo:longint;

ll:packed array[0..9,0..9,-1..11] of longint; //存储每个空格可能出现的数字 提高程序效率

function max(a,b:longint):longint;

begin

if b>a then exit(b)

else exit(a);

end;

function choose2(x:longint):longint;

begin

case x of

0..3:exit(1);

4..6:exit(2);

7..9:exit(3);

end;

end;

function iff:boolean; //搜索结束条件

begin

if (k<1) then exit(false)

else exit(true);

end;

function pa(i,j:longint):longint; //得到九宫格编号

var o,kk,jj,ii:longint;

begin

o:=choose2(i);

kk:=choose2(j);

case o of

1:jj:=0;

2:jj:=3;

3:jj:=6;

end;

exit(jj+kk);

end;

begin

fillchar(x,sizeof(x),true);

fillchar(y,sizeof(y),true);

fillchar(xy,sizeof(xy),true);

for i:=1 to 9 do

for j:=1 to 9 do

begin

read(ii);

a[i,j]:=ii;

if ii=0 then begin

inc(n);

s1[n,1]:=j;

s1[n,2]:=i;

end

else begin

x[i,ii]:=false;

y[j,ii]:=false;

xy[pa(i,j),ii]:=false;

end;

end;

for i:=1 to 9 do

for j:=1 to 9 do

begin

for oo:=1 to 9 do

if x[i,oo]and y[j,oo] and xy[pa(i,j),oo] then

begin

inc(ll[i,j,-1]);

ll[i,j,ll[i,j,-1]]:=oo;

end;

end;

for i:=1 to n do

s[i]:=s1[n-i+1];

k:=1; i:=0;

t:=true;tt:=false;

whileiff do

begin

if t then

begin

for i:=ll[s[k,2],s[k,1],-1] downto 0 do

if (x[s[k,2],ll[s[k,2],s[k,1],i]]and y[s[k,1],ll[s[k,2],s[k,1],i]]) and xy[pa(s[k,2],s[k,1]),ll[s[k,2],s[k,1],i]] then

begin

t:=true;

break;

end;

end

else begin i:=s[k,4]; tt:=false;

repeat

dec(i);

until ((x[s[k,2],ll[s[k,2],s[k,1],i]]and y[s[k,1],ll[s[k,2],s[k,1],i]]) and xy[pa(s[k,2],s[k,1]),ll[s[k,2],s[k,1],i]])or (i<1);

end;

if i<1 then begin s[k,3]:=0; a[s[k,2],s[k,1]]:=0;

dec(k); t:=false;i:=s[k,3]; x[s[k,2],i]:=true;y[s[k,1],i]:=true;//向上回溯

xy[pa(s[k,2],s[k,1]),i]:=true;

end

else t:=true;

if t then

begin

s[k,4]:=i;

s[k,3]:=ll[s[k,2],s[k,1],i];

a[s[k,2],s[k,1]]:=s[k,3];

x[s[k,2],s[k,3]]:=false;

y[s[k,1],s[k,3]]:=false;

xy[pa(s[k,2],s[k,1]),s[k,3]]:=false;

inc(k);

end;

tt:=false;

if k>n then

begin

inc(opo);

writeln(opo); // 计数器

for i:=1 to 9 do

begin

for j:=1 to 9 do

write(a[i,j],' ');

writeln;

end;

writeln;

mm:=0;

x[s[k-1,2],s[k-1,3]]:=true;

y[s[k-1,1],s[k-1,3]]:=true;

xy[pa(s[k-1,2],s[k-1,1]),s[k-1,3]]:=true;

dec(k);

t:=false;

end;

end;

writeln(opo);

end.

求解数独的简单C语言程序（适合仅有唯一解的数独）/*数独求解*/

#include <stdio.h>

void print(int a[9][9]) /*格式化输出数独*/

{int i,j;

for(i=0;i<9;i++)

{for(j=0;j<9;j++)

printf("%d ",a[i][j]);

printf("\");

}

}

void ini_logo(int logo[10][9][9],int arr[9][9]) /*初始化标志数组*/

{int i,j,k,p,r,s,t;

for(i=0;i<9;++i)

for(j=0;j<9;++j)

if(arr[i][j]!=0)

for(k=1;k<=9;++k)logo[k][i][j]=1;

for(i=0;i<9;++i)

for(j=0;j<9;++j)

if(arr[i][j]!=0)

{p=arr[i][j];

for(r=0;r<9;++r)

{logo[p][i][r]=1;logo[p][r][j]=1;}

for(s=(i/3)*3;s<(i/3)*3+3;++s)

for(t=(j/3)*3;t<(j/3)*3+3;++t)

logo[p][s][t]=1;

}

}

int add(int arr[9][9],int logo[10][9][9],int m,int n,int k) /*arr[m][n]插入数字，修改arr,logo数组*/

{int i,s,p,t;

arr[m][n]=k;

for(p=1;p<=9;++p)

logo[p][m][n]=1;

for(i=0;i<9;++i)

{logo[k][m][i]=1;

logo[k][i][n]=1;

}

for(s=(m/3)*3;s<(m/3)*3+3;++s)

for(t=(n/3)*3;t<(n/3)*3+3;++t)

logo[k][s][t]=1;

}

int check(int logo[10][9][9],int arr[9][9]) /*检测行列和小九宫格*/

{int i,j,k,p,q,r,s,t,m,n,tag=0; /*tag标志本轮是否修改*/

for(k=1;k<=9;++k)

{for(i=0;i<9;++i)

{p=0;q=0;

for(j=0;j<9;++j)

{if(logo[k][i][j]==0){r=j;p++;} /*检测行*/

if(logo[k][j][i]==0){s=j;q++;} /*检测列*/

}

if(p==1){tag=1;add(arr,logo,i,r,k);}

if(q==1){tag=1;add(arr,logo,s,i,k);} /*满足一个添加的条件，修改arr,logo数组和标志tag*/

}

for(i=0;i<9;i=i+3) /*检测小九宫格*/

for(j=0;j<9;j=j+3)

{t=0;

for(m=i;m<i+3;++m)

for(n=j;n<j+3;++n)

if(logo[k][m][n]==0){q=m;s=n;t++;}

if(t==1){tag=1;add(arr,logo,q,s,k);}

}

}

return(tag);

}

main()

{

int arr[9][9]={

0,0,0,0,0,0,0,0,0, /*数独初始化，其中0表示数字未给出*/

0,2,3,0,0,0,7,8,0,

1,0,0,4,0,6,0,0,9,

4,0,0,0,5,0,0,0,1,

9,0,0,0,0,0,0,0,6,

0,6,0,0,0,0,0,9,0,

0,0,5,0,0,0,8,0,0,

0,0,0,3,0,1,0,0,0,

0,0,0,0,9,0,0,0,0

},

logo[10][9][9]={0},i,j;

ini_logo(logo,arr);

while(check(logo,arr)==1) /*当一轮没有检测出，即结束*/

{}

print(arr);

}

=================================================================================

Java解法(循环递归法):

private boolean counting(int row, int col){

// Fill the number as 1 to 9

for (int num = 1; num < 10; num++){

if (isLegal(row, col, num)){// Check whether the number is legal

matrix[row][col] = num;

int nextRow = (row + 1 > 8) ? 0 : (row + 1);

int nextCol = (col + 1 > 8) ? 0 : (col + 1);

if (nextCol != 0) {// Not last column

if (counting(row, nextCol))

return true;

} else if (nextRow != 0) {// Last column

if (counting(nextRow, nextCol))

return true;

} else {// Last cell

return true;

}

// Get false with the current selection, clear it and go on

matrix[row][col] = 0;

}

}

// From 1 to 9, no number is legal, return false

return false;

}

上面只列出了主函数，如果要调用,还需要初始化matrix二维数组，然后写以下语句：

if (counting(0, 0) == true)

//有解

else

//无解

数独的段位以及评选方法

一段掌握数独概念及其分类、数独元素和规则、数独符号；掌握单区唯一解法、简单排除法；45分钟内正确完成1星九字标准题3道。二段：掌握数独概念及其分类、数独元素和规则、数独符号；掌握单元排除法；了解对角线数独和不规则数独的解题规则；45分钟内正确完成2星九字标准题2道、对角线数独或不规则数独1道。三段：掌握数独概念及其分类、数独元素和规则、数独符号；掌握多区唯一解法、区块排除法、数组占位法；掌握杀手数独的解题规则；45分钟内正确完成3星九字标准题2道、杀手数独题1道。四段： 掌握候选数概念及候选数列表、链的概念及分类；掌握初级候选数删减法；熟练掌握对角线数独、不规则数独、杀手数独的解题技巧；45分钟内正确完成4星九字标准题1道、杀手数独1道、不规则数独或对角线数独1道。五段： 掌握候选数概念及候选数列表、链的概念及分类；熟练掌握初级候选数删减法；熟练掌握各类题型的解题技巧；对于新题型的反应能力比较快速，45分钟内正确完成4星九字标准题2道、新变形数独题2道。六段： 掌握候选数概念及候选数列表、链的概念及分类；熟练掌握高级候选数删减法；对于新题型的反应能力非常快速，45分钟内正确完成5星九字标准题2道、新变形数独2道。七段： 45分钟内正确完成5星九字标准题2道、新变形数独题3道。或是中国数独锦标赛冠军。八段： 世界数独锦标赛前八名。九段： 世界数独锦标赛前三名，同时提交一篇论文，经中国数独联盟理事会审核通过。（证书2年内有效，2年后须复核，如不过即降段，上交本人2寸照片）。

数独单元格的叫法

从第1行到第9行分别叫A、B、C、D、E、F、G、H、I行，从第1列到第9列分别叫1.2.3.4.5.6.7.8.9列。读单元格的名称时，字母放前，数字放后。比如说第3行第5列就叫C5，第9行第6列叫I6，以此类推。

玩数独的好处

数独

少儿玩了可以激活细胞

成人玩了可以思维宽阔

老人玩了可以延年益寿