换一批

数独

数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。

经验文章 概述

  组成元素

  方格

  水平方向有九横行,垂直方向有九纵列的矩形,画分八十一个小正方形,称为九宫格(Grid),是数独(Sudoku)的作用范围。

  数独元素 - 九宫格

  行

  水平方向的每一横行有九格,每一横行称为行(Row)。

  数独元素 - 单元

  列

  垂直方向的每一纵列有九格,每一纵列称为列(Column)。

  数独元素 - 列

  宫

  三行与三列相交之处有九格,每一单元称为小九宫(Box、Block),简称宫,如图四所示(在杀手数独中,宫往往用单词Nonet表示)。

  数独元素 - 宫

  单元

  上述行、列、宫统称为单元(Unit)。

  区块

  由三个连续宫组成大区块(Chute),分大行区块(Floor)及大列区块(Tower)。

  第一大行区块:由第一宫、第二宫、第三宫组成。第二大行区块:由第四宫、第五宫、第六宫组成。第三大行区块:由第七宫、第八宫、第九宫组成。第一大列区块:由第一宫、第四宫、第七宫组成。第二大列区块:由第二宫、第五宫、第八宫组成。第三大列区块:由第三宫、第六宫、第九宫组成。

  格位编号

  格位按所处的行列单元赋予坐标值。

  数独元素 - 格位

  坐标有多种标示法,有横行 A~I,纵列 1~9(如中国),也有横行 1~9,纵列 A~I(如日本),这两种标示容易混淆,故最被广泛使用的是横行R1~R9,纵列C1~C9的标示法。

  提示数

  在九宫格的格位填上一些数字,做为填数判断的线索(Hint),称为提示数(Clue)。

  数独元素 - 提示数

  基本解题方法

  解题的本质有二:隐性唯一解(Hidden Single)及显性唯一解(Naked Single),他们的名称是在候选数法的基础上命名的。

  解题必须以逻辑为依归,猜测的方法被称为“暴力型”解法(Brute Force),这不是提倡数独的本意。

  根据解题本质发展出来的基本解题方法有二种:

  摒除法

  摒除法:用数字去找单元内唯一可填空格,称为摒除法,数字可填唯一空格称为摒余解(隐性唯一解)。根据不同的作用范围,摒余解可分为下述三种:数字可填唯一空格在「宫」单元称为宫摒余解(Hidden Single in Box),这种解法称宫摒除法。数字可填唯一空格在「行」单元称为行摒余解(Hidden Single in Row),这种解法称行摒除法。数字可填唯一空格在「列」单元称为列摒余解(Hidden Single in Column),这种解法称列摒除法。行摒余解和列摒余解合称行列摒余解(Hidden Single in Line)。得到行列摒余解的方法称为行列摒除法。

  余数法

  Peer等位群格位余数法:用格位去找唯一可填数字,称为余数法,格位唯一可填数字称为唯余解(Naked Single)。余数法是删减等位群格位(Peer)已出现的数字的方法,每一格位的等位群格位有 20 个,如图七所示。依解题填制的过程可区分为直观法与候选数法:

  直观法

  直观法就是不做任何记号,直接从数独的盘势观察线索,推论答案的方法。

  候选数法

  候选数法就是删减等位群格位已出现的数字,将剩余可填数字填入空格做为解题线索的参考,可填数字称为候选数(Candidates,或称备选数)。

  直观法和候选数法只是填制时候是否有注记的区别,依照个人习惯而定,并非鉴定题目难度或技巧难度的标准,无论是难题或是简单题都可上述方法填制,一般程序解题以候选数法较多。

  进阶解题方法

  上述方法称为基础解法(Basic Techniques),其他所有的解法称为进阶解法(Advanced Techniques),是在补基本解法之不足,所以又称辅助解法。

  进阶解法包括:区块摒除法(Locked Candidates)、数组法(Subset)、四角对角线(X-Wing)、唯一矩形(Unique Rectangle)、全双值坟墓(Bivalue Universal Grave)、单数链(X-Chain)、异数链(XY-Chain)及其他数链的高级技巧等等。已发展出来的方法有近百种之多。

  其中前两种加上基础解法为一般数独书中介绍并使用的方法,同时也是大部分人可以理解并掌握的数独解题技法。通过基础解法出数只需一种解法,摒除法或唯余法,超出此范围而需要施加进阶解法时,解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数,该解题点的解法需要多个步骤协力完成,因此称做组合解法。

  相对概率

  相对概率不是真实的概率,而是用于同一格中的几个数字之间相互比较出现的可能。

  相对概率 = 九宫格出现的概率 × 行出现的概率 × 列出现的概率

  九宫格出现的概率:如果九宫格中有2个格可能出现1,目标格可能的数字为1、2、3,另一个格可能出现的数字为1、4,那么:目标格中的1在九宫格出现的概率 = 目标格中出现1的概率 × (1 - 另一个格中出现1的概率),得1/3 × (1-1/2) = 1/6。

  注意:1-1/2表示另一个格不出现1的概率,1/3 × (1-1/2) 的意思就是在另一个格不出现1的情况下,目标格出现1的概率。

  如果九宫格中有三个格可能出现1,目标格可能的数字为1、5、6,另一个格可能出现的数字为1、7,还有一个格可能出现的数字为1、8、9,得1/3 × (1-1/2) × (1-1/3) = 1/9。依此类推。

  行出现的概率和列出现的概率与九宫格出现的概率的算法原理相同。最后,把三个概率相乘,得到相对概率,把目标格中3个数字的相对概率进行对比,相对概率越大,出现的可能性越大。

  区块摒除法

  区块摒除法包括宫区块摒除法(Pointing)与行列区块摒除法(Claiming)。在基础题里,利用区块摒除可以替代一些基础解法的观察,或辅助基础解法寻找焦点。在非基础题里,区块可以隐藏任何其他结构,简单的可以把基础解法隐藏起来,难的可以隐藏数对等等其他进阶技巧。

  区块摒除法

  首先数字6对第五宫摒除,得到第五宫的6在R4C5或者R6C5。

  不论是在R4C5或者R6C5,C5的其他格都不能再有数字6。(R4C5与R6C5就是数字6的区块,这也是区块摒除作用的观点)

  数字6对第二宫摒除,得解R1C4=6。

  难度划分

  影响数独难度的因素很多,就题目本身而言,包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言,了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐,在书籍、报纸、杂志中所列的难度或者大众解题时间纯属参考,常有难度错置的情况出现,所以不必特别在意。网络上有很多数独难度的分析软件,比较著名的是 Nicolas Juillerat 开发的 Sudoku Explainer 和 Bernhard Hobiger 开发的 Hodoku,它们都是免费的软件。因为每种软件的都有不同的解题策略,所以也只能作为难度的大致界定,无法真正的解析出难度的内涵。

  如果一道题目的提示数少,那么题目就会相对难,提示数多则会简单,这是一般人判断难易的思维模式,但数独谜题提示数的多寡与难易并无绝对关系,多提示数比少提示数难的情况屡见不鲜,同时也存在增加提示数之后题目反而变难的情形,即使是相同提示数(甚或相同谜题图形)也可以变化出各式各样的难度。提示数少对于出题的困难度则有比较直接的关系,以20-35提示数而言,每少一个提示数,其出题难度会增加数倍,在制作谜题时,提示数在22以下就非常困难,所以常见的数独题其提示数在23~30之间,其原因在于制作比较不困难,可以设计出比较漂亮的图形(Pattern),另外这个提示数范围的谜题变化多端是一个重要因素。

  终盘数量

  数独中的数字排列千变万化,那么究竟有多少种终盘的数字组合呢?

  6,670,903,752,021,072,936,960(约为6.67×10的21次方)种组合,2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字,并将计算方法发布在他们网站上,如果将等价终盘(如旋转、翻转、行行对换,数字对换等变形)不计算,则有5,472,730,538个组合。数独终盘的组合数量都如此惊人,那么数独题目数量就更加不计其数了,因为每个数独终盘又可以制作出无数道合格的数独题目。

  标准数独

  目前(截止2011年)发现的最少提示数9×9标准数独为17个提示,截止2011年11月24日16:14,共发现了非等价17提示数谜题49151题,此数量仍在缓慢上升中,如果你先发现了17提示数的题目,可以上传至“17格数独验证”网站,当然你也可以在这里下载这49151题。

  关于是否有16提示数的合格题目,网络上也争论很久,有发现16提示数双解的,但是仍未发现唯一解。国外有网友给出了关于为什么至少需要17提示的证明,受到了大家的质疑,比如9×9对角线数独(在标准数独规则基础上,两条大对角线的数字不重复)的最小提示数为12,按照他的理论则需要更多的提示数。

  另外在2006年Gary McGuire撰写了程式,试图通过暴力法来证明16提示数的数独是否存在,方法很简单,既然Bertram Felgenhauer和Frazer Jarvis已经计算出不等价的终盘总数为5,472,730,538个,那么将每个终盘是16提示的情况都跑一遍,如果没有找到16提示的数独,那么就可以证明最少提示数为17个。但因为是暴力方法,对于一台单核的电脑来说需要跑30万年才能跑出结果。台湾的吴毅成教授和他的团队将Gary McGuire的程式加以改进,使得效率大幅提升,大约2417年即可完成演算。并放在BOINC(伯克利开放式网络计算平台)上让世界加入BOINC的电脑一同演算,令人欣喜的是,截至编辑2012年4月18日已经完成了51.73%。

  Gary McGuire的团队在2009年设计了新的算法,利用Deadly Pattern的思路,花费710万小时CPU时间后,于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明,继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。

相关文章

手机页面
收藏网站 回到头部