看到你昏昏欲睡的数独技巧 - 静盟论坛--一场风花雪月的事

数偶等价论
<H1 style="MARGIN: 17pt 0cm 16.5pt">基本定义</H1>
一般来说，我们解数独都是一步步排除或者确定数字的过程。每一步，我们实际上都是在对类似这样的逻辑命题进行判断：第3行第8列是数字5。当我们从第三行第8列排除数字5，我们实际上宣称这个命题不成立；反之，当我们确定该格子的数是5的时候，我们实际上是宣告这个命题成立。这样的命题，我们称之为候选数命题，或者简称“候选数”:
定义 1【候选数】数独中确定某格内是某数字的一个命题称为候选数。
候选数因此包含如下属性：行号(R), 列号(C), 九宫号(N), 以及数字(D)。根据数独规则，数字相同的两个候选数，其行号，列号，或者九宫号相同的，不能同时成立。另外，如果行号和列号相同的(数字不同)的两个候选数也不能同时成立。根据数独规则，我们有互斥组的定义：
定义 2【互斥组】一组候选数形成一个互斥组，如果这些候选数里有且只有一个成立。
互斥组实际上满足两个条件：1). 一个互斥组里至少有一个候选数成立；2). 一个互斥组最多有一个候选数成立。数独里属于一行，一列或者一个九宫的数字相同的候选数，或者属于同一个格子的候选数，天然地形成一个互斥组。这些天然的互斥组，我们称为元组。一般来说，当互斥组里有一个候选数确定为真时，其他候选数立即为假；但是如果一个候选数为假，却不一定能判断其他候选数的真假。当互斥组里候选数的个数下降到两个时，有趣的情况出现了：对于只有两个候选数的互斥组，其中一个为真，就意味着另一个为假；反之，其中一个为假，就意味着另外一个为真。它们好像硬币的两面，一面朝上，另一面就朝下。
定义 3【数偶】只有两个候选数的互斥组称为一对数偶。形成数偶对的候选数之间称为共轭关系。
候选数a和b形成一对数偶，我们也说a和b共轭。
<H1 style="MARGIN: 17pt 0cm 16.5pt">数偶和等价类</H1>
如果候选数a和b组成一对数偶，候选数b和c组成一对数偶，则a为真意味着c为真，a为假也意味着c为假，我们称a和c等价。
定义 4【等价】两个候选数等价，如果一个候选数的真假就意味着另外一个候选数的真假。
很明显，等价关系是自反的：如果a和b等价，则b也和a等价。等价关系是传递的，如果a等价于b，b又等价于c，则a等价于c。因此我们可以定义等价类：
定义 5【等价类】一组互相之间等价的候选数构成一个等价类。
引入等价类的直接好处是扩展了候选数的接触范围。当一个候选数局部的条件不足以判断其真伪时，使用等价类可以利用更大范围的条件。考虑一个常用的直观法：当某数字在某九宫中全在一行上时，则该行上其他位置不能出现该数。它可以基于如下逻辑：如果一个候选数和某个其他元组的所有的候选数在一个互斥组里，则该候选数为假。在只有一个候选数的情况下，该法则应用范围有限。现在使用基于等价类的判断法则：如果某元组的所有候选数分别和同一个等价类的候选数互斥，则该等价类不成立。这实际上是一种相当高级的判断法则。另外一种新的情况是，虽然单个候选数不能和自己争位子，单个等价类却可以。我们多出来一个新的准则：如果处于同一个互斥组的两个候选数等价，则该等价类不成立。所以我们一下就有了两个基于等价类的判定法则：
法则 1【等价互斥原理】处于同一个互斥组的两个等价候选数不能成立。
<A name=_Ref164016801>法则 </A>2【互斥—不等价原理】和一个互斥组所有候选数都互斥的等价类不能成立。
注意到候选数之间的共轭关系可以直接推广到等价类上：
定义 6两个等价类互相共轭，如果存在分别属于这两个等价类的共轭候选数(数偶)。互相共轭的等价类称为等价类偶。
然后由【互斥—不等价原理】可得：
法则 3【共轭—不等价原理】和一对等价类偶同时互斥的等价类不能成立。
这是显然的，因为共轭等价类的存在意味着共轭候选数的存在，共轭候选数组成一个完整的互斥组，所以和共轭等价类同时互斥，就意味着和这个互斥组的所有候选数互斥。
<H1 style="MARGIN: 17pt 0cm 16.5pt">类偶链和类偶环</H1>
假设等价类偶A的一对共轭等价类表为A+和A-。如果有两对等价类偶A和B，如果它们满足如下条件，它们可以融合成为一对新的等价类偶：
法则 4【类偶合并法则1】对于等价类偶A和B，如果A+和B-互斥，A-和B+互斥，则A+和B+等价，A-和B-等价。它们形成一对新的等价类偶C：C+={A+, B+}, C-={A-, B-}。
证明是容易的，只需证明A+和B+等价即可。如果A+成立，由于互斥关系，B-不成立，故由数偶关系B+成立。如果A+不成立，由数偶关系A-成立，由互斥关系，B+不成立。根据等价关系的定义，A+和B+等价。命题得证。
如果分属两对等价类偶的共轭等价类之间只存在一组互斥关系，也就是说它们不满足【共轭—不等价原理】和【类偶合并法则】的条件，我们就得到一个等价类偶节：
定义 7【等价类偶节】如果等价类偶A和B的等价类之间仅存在一组互斥关系，比方说A-和B+，则A和B之间形成一个等价类偶节，组成互斥关系的两个等价类(A-和B+)称为这个等价类偶节的关节，另外两个自由的等价类称为首尾。
注意，组成关节的两个等价类是互斥关系，也就是说它们不能同时为真；因此由各自的共轭关系，得到组成首尾的两个类之间不能同时为假。这样的关系我们称为准真。
定义 8【准真】两个(或者两个以上)等价类之间构成一组准真关系，如果它们之间至少有一个为真。
互斥组就是一组既互斥又准真的候选数。因此【互斥—不等价原理】可以推广为：
法则 5【准真—不等价原理】和一个准真组所有候选数或者等价类都互斥的候选数或者等价类不能成立。
这个原理的直接推论就是类偶节的首尾绞杀法则。
法则 6【首尾绞杀法则1】和等价类偶节首尾等价类同时互斥的候选数或者等价类不能成立。
等价类偶节的概念可以推广到类偶链：
定义 9【等价类偶链】设有一组等价类偶A1, A2, … An, 顺序满足A1-和A2+互斥，A2-和A3+互斥，如此直到An-1-和An+, 则它们构成一组等价类偶链。等价类A1+和An-称为该等价类偶链的首尾。
注意在等价类偶链中，如果i < j，Ai+和Aj-总是形成一对准真组，它们是从i到j的等价类偶链的首尾。等价类偶链是等价类偶节的自然延伸。因此我们有
法则 7【首尾绞杀法则2】和等价类偶链首尾等价类同时互斥的候选数或者等价类不能成立。
如果一个等价类偶链的首尾等价类存在互斥关系，我们就找到一个等价类偶环：
定义 10【等价类偶环】等价类偶环是首尾互斥的等价类偶链。
等价类偶环实际上是一对隐藏的等价类偶，因此环上的等价类偶可以合并：
法则 8【类偶合并法则2】如果等价类偶环A1，A2，…，An满足A1-和A2+互斥，A2-和A3+互斥，如此直到An-和A1+互斥，则它们可以合并成一对等价类偶A，其中A+={A1+，A2+，…，An+}，A-={A1-，A2-，…，An-}。
这实际上是【类偶合并法则1】的自然延伸和推广。所以证明也类似。类偶合并的结果是扩大了等价类的接触面积，从而可以增加使用【互斥—不等价原理】和【共轭—不等价原理】的机会。
<H1 style="MARGIN: 17pt 0cm 16.5pt">候选数关系</H1>
这一章研究候选数之间可能的关系。在数独中，最常见的关系是候选数之间的互斥关系，比如在同一个互斥组中的两个候选数a和b，a成立就意味着b不成立，b成立就意味着a不成立。在一般情况下的两个候选数，则很可能只出现一种情况，比如说a成立则b不成立，反之则不一定成立。这样的关系我们称为排斥：
定义 11【排斥】如果候选数a成立，则候选数b不成立，我们就称为a排斥b。在这种情况下，我们称b是a的牺牲。
类似地，我们可以定义其他三种情况：
定义 12【激励】如果候选数a成立，则候选数b也成立，我们就称为a激励b，称b是a的响应。
定义 13【释放】如果候选数a不成立，则候选数b成立，我们就称a释放b，称b是a的反调。
定义 14【抑制】如果候选数a不成立，则候选数b也不成立，我们就称a抑制b，称b是a的陪殉。
由逻辑的逆反命题原理可知，如果a排斥b，则b也排斥a。排斥的确是一个相互关系。类似地，如果a释放b，则b也释放a，互相释放的候选数之间其实是一组准真关系。但是，如果a激励b，则b抑制a。激励和抑制之间是一种反噬作用。
共轭关系和等价关系可以建立在这些定义的基础上。共轭等于互斥加准真。等价等于激励且抑制。
上面这些候选数间的关系显然可以自然地推广到等价类上。只需把每个定义中的候选数换成等价类即可。下面两个原理来自于数独的基本规则：
法则 9【互斥原理】如果一个等价类存在互斥的响应(反调)，则该等价类不成立(成立)。
法则 10【牺牲原理】如果存在整个准真组都是某个等价类的牺牲(陪殉)，则该等价类不成立(成立)。
【互斥原理】是说，如果候选数b和c都是a的响应，而且b和c互斥，那么a不成立。【牺牲原理】说的是，如果b和c都是a的牺牲，而且b和c构成一组准真关系，那么a不成立。这两个原理实际上是【等价互斥原理】和【准真—不等价原理】的推广。
由于等价类扩大了候选数的接触范围，所以扩张等价类是有益的。下面三个原理阐明了等价扩张的法则：
法则 11【牺牲提升原理1】如果候选数a既是等价类A的响应，又是A的共轭的牺牲，则a和A等价。
法则 12【牺牲提升原理2】如果候选数a是等价类A共轭的牺牲，a所在的某个准真组其他候选数都是等价类A的牺牲，则a和A等价。
法则 13【响应提升原理】如果一对互斥的候选数a+和a-分别是一对等价类偶A+和A‑的响应，则a+和A+等价，a‑和A-等价。