数独人造解法的一些技巧及其python实现

数独人工解法的一些技巧及其python实现
这段日子实现了十几种数独的解题技巧，说实话，花费的时间比我想象的要长得多。本来说了要看论文的，结果心里痒痒，看着论文，心里想着实现这些解法的基础数据结构等等，于是忍不住小试了一下，一发不可收拾，就这样做了两个星期。中间生了一场病，在宿舍里躺了几天，顺便看了几本书，从《万寿寺》到《红拂夜奔》到《寻找无双》，也不知道是感冒药吃多了比较敏感，还是真的感触太大，有一天晚上看完《红拂夜奔》后，竟失声痛哭起来。我体会着那种无尽的绝望，甚至已经无力悲愤了。昨夜又看了《三十而立》，逻辑上的“人人都要死，皇帝是人，所以皇帝必死”与为生存目的而喊出的“皇上万岁万岁万万岁”相对立，可是人都能接受，人是多么复杂的生物啊。嗯哼，我跑题了。
总共有十几种解题技巧，其中最直接的是显式唯一数法和隐式唯一数法。所谓显式唯一数法，是指某个格只有一个候选数可选，这个格自然就只能填这个候选数了。而隐式唯一数法的意思则是，某一行、列或宫只有一个位置可以填某个候选数，当然，这个位置肯定就填这个候选数了。这两个技巧其实根本也算不上技巧了，除了这两个条件，我们还能怎样确定某个格该填哪个数，或者哪个数该填在哪个格呢？剩下的解题技巧，都是在努力删除格子里的候选数，从而使局面浮现出一个显式唯一数，或一个隐式唯一数。除了显/隐式唯一数法，还有显/隐式数对法，显/隐式三数集法以及显/隐式四数集法。在我看来，显式与隐式，一个以位置为中心，一个以候选数为中心，前面提到，显示唯一数法是指某个位置只有一个候选数可选，而显式数对法则是，在一个行/列/宫（以后统称为房）里，有两个位置只有两个相同的候选数可选，那么在这个房的其他位置，可以删除这两个候选数；同理，显式三数集、显式四数集法是指在一个房里，有三个/四个位置只有三/四个相同的候选数可选，那么在这个房的其他位置，可以删除这几个候选数。面隐式数对法则是说，有两个候选数只有两个相同的可选位置，那么这两个位置中的其他候选数均可以删除；同理，隐式三/四数集法是说，有三/四个候选数只有三/四个相同的可选位置，那么在这些位置中，其他的候选数都可以删除。除了以上8种技巧，还有区块删除法，XY形态匹配法（XY-Wing），XYZ形态匹配法（XYZ-Wing），矩形对角法（X-Wing），三链数删减法（SwordFish），四链数删减法（JellyFish）以及唯一矩形法（Unique Rectangle）。除此之外，还有X-Chain单数链法，XY-Chain双数链法以及Forcing Chain，不过我至今没有找到比较好的实现方法，所以算未完成。关于这些技巧的详细介绍，推荐大家看附件的那份手册，其实我所做的事情他全都做了，而且做得非常完整仔细，真是相当的佩服。
既然我已经认定了技巧分两种，一种以位置为中心，一种以候选数为中心，所以我就使用了两个dict来辅助这两种思路，一种就是以位置(r,c)为键，以候选数集为值，即valid_set[(r,c)]=set([a,b,c...])；另一个则以候选数为键，以其可选位置为值，即candi_pos[i]=set([(r1,c1),...,(rn,cn)])。这样，显式唯一数法和隐式唯一数法分别利用这两个dict就可以很容易地完成了：

def _nakedSingleNumber( self ):self._changed = Falsefor pos, validset in self._valid_set.items():if len(validset)<=0:self._invalid = Falseelif len(validset) == 1:num = validset.pop()validset.add(num)print 'pos', pos, 'has only one candidate: %d' %numself._changed = Truereturn Truereturn Falsedef _hiddenSingleNumber( self ):self._changed = Falsefor num, posset in self._candi_pos.items():#_groupByRow,_groupByCol,_groupByBlock is helper functionrows = self._groupByRow(posset)for r, row in rows.items():if len(row)==1:print 'row%d has only one position for num %d' %(r, num), row[0]self._changed = Truereturn Truecols = self._groupByCol(posset)for c, col in cols.items():if len(col)==1:print 'col%d has only one position for num %d' %(c, num), col[0]self._changed = Truereturn Trueblks = self._groupByBlock(posset)for b, blk in blks.items():if len(blk)==1:print 'blk%d has only one position for num %d' %(b, num), blk[0]self._changed = Truereturn Truereturn False

从我们对显式数对/三数集/四数集法的描述，可以看出，它们其实很相似，只不过涉及到的候选数的个数不相同罢了。显式数对法中，要求两个位置有且只有两个相同的候选数，显式三数集法中，要求有三个位置，他们可以有两个或三个候选数，但是他们涉及到的候选数合起来正好是三个；同理，显式四数集法中要求有四个位置，他们可以有两个、三个或四个候选数，但是他们涉及到的候选数合起来正好是四个。注意到的是这些个位置指的都是同一个房内的。因此我的思路是这样的：分别对行/列/宫进行分析，num表示数集的个数（num=2：数对，num=3：三数集，num=4：四数集），如果该位置的候选数个数小于num，说明这个位置是可选的，将它加入candidate list中。从candidate list中任选num个（当然前提是candidate list中至少有num个元素），求这些位置的候选数的并集，如果正好等于num，则说明他们形成了显式数集。这其中涉及到一个辅助函数，_get_n_from_m(n,m)，即从m中任选n个元素而不导致重复，也就是我们的Cm取n，实现如下：

def _get_n_from_m( self, n, m ):index = range(n)while index[0]<=m-n:yield indexi = n-1if index[i]<m-n+i:index[i]+=1else:index[i-1]+=1while i>0 and index[i-1]>=m-n+i:i -= 1index[i-1]+=1for j in range(i,n):index[j]=index[j-1]+1

这个函数很有用，在后面将多次使用到。有了这个函数，接下来实现我们的思路就不难了：

#nakedNumberSet occurs in a [house], [name] it 'row/column/block'#num=2: pair#num=3: tripple set#num=4: quad setdef _helper_nakedNumberSet( self, house, name, num ):for i, item in house.items():candidate = []#if a position has less than or equal to [num] candidates#add it to the candidate position listfor pos in item:if len(self._valid_set[pos])<=num:candidate.append(pos)#if candidate list has at least [num] elements#get any [num] of positions #and have union of candidate numbers of these position#if this union has exactly [num] candidate numbers#we can delete these candidate numbers from cells other than these positionif len(candidate)>=num:for indices in self._get_n_from_m( num, len(candidate)):uSet = set()subset = []toRemove = []for index in indices:uSet = uSet.union(self._valid_set[candidate[index]])if len(uSet)==num:subset = [ candidate[j] for j in indices ]for j in subset:item.remove(j)for pos in item:for n in uSet:if n in self._valid_set[pos]:toRemove.append( ( pos[0], pos[1], n ))if toRemove:print 'in %s%d,' %(name,i),for (r,c) in subset:print '(%d, %d)' %(r,c),print 'have only candidates',for n in uSet:print '%d' %n,printself._removeCandidate(toRemove)self._changed = Truereturn Truereturn False

同样的，隐式数对/三数集/四数集法也是相通的，只由一个num来区别。而且它的实现思路与显式数集法相仿，只不过由以位置由中心变成了以候选数为中心而已。首先是以房为单位，把那些只有少于num个候选位置的候选数给选出来，然后利用_get_n_from_m从中任选num个，看他们的并集是否正好是num个位置。

def _helper_hiddenNumberSet( self, housename, num ):con = list()for i in range(9):con.append(dict())groupBy = getattr( self, '_groupBy%s' %housename )for n, posset in self._candi_pos.items():house = groupBy( posset )for i, items in house.items():if len(items)<=num:con[i][n]=set(items)for i in range(9):if len(con[i])>=num:for indices in self._get_n_from_m( num, len(con[i])):ks = con[i].keys()nSet = [] uSet = set()toRemove = []for index in indices:nSet.append(ks[index])uSet = uSet.union(con[i][ks[index]])if len(uSet)==num:for pos in uSet:for j in self._valid_set[pos]:if j not in nSet:toRemove.append( (pos[0], pos[1], j) )if toRemove:self._changed = Trueprint 'in %s%d,' %(housename, i),for n in nSet:print '%d,' %n,print 'have only candidate postion',for n in uSet:print n,print self._removeCandidate(toRemove)return Truereturn False

区块删减法基本可以用下面两点来概括：
1. 在某一区块即宫中，如果某个候选数只出现在一行（或者一列中），那么可以将该候选数从该行（或者该列）的其他单元格中删除，因为我们知道，每一个行/列/宫都有且只有一个候选数i，如果该候选数i在某个块中只出现在同一行，那么该行便已经确定在这个块中会有这个候选数了，所以该行的其他单元格就不能再有这个候选数了。
2. 在某一行/列中，如果某个候选数只出现在同个块中，那么可以将该候选数从该块中的其他单元格中删除。

def _regionDeletion( self ):self._changed = Falsefor num, posset in self._candi_pos.items():blks = self._groupByBlock(posset)#1. if in a blk, a candidate number occurs at the same row or same column#delete the candidate number from other cells of this row/columnfor b, blk in blks.items():(r,c) = blk[1]sameRow = TruesameCol = Truefor (ri,ci) in blk:if ri!=r:sameRow = Falseif ci!=c:sameCol = Falseif not (sameRow or sameCol):breakif sameRow:toRemove = []for i in range(0,c//3*3)+range((c//3+1)*3, 9):if (r,i) in self._valid_set and num in self._valid_set[(r,i)]:toRemove.append((r,i,num))if toRemove:self._changed = Trueprint 'in block%d, num %d occurs at the same row %d' %(b, num, r)self._removeCandidate(toRemove)return Trueif sameCol:toRemove = []for i in range(0, r//3*3)+range((r//3+1)*3, 9):if (i, c) in self._valid_set and num in self._valid_set[(i,c)]:toRemove.append((i,c,num))if toRemove:self._changed = Trueprint 'in block%d, num %d occurs at the same col %d' %(b, num, c)self._removeCandidate(toRemove)return True#2.1 if in a row, a candidate number occurs at the same block,#delete the candidate number from other cells of this blockrows = self._groupByRow( posset )for r, row in rows.items():(r,c) = row[1]b = (r//3)*3+c//3sameBlock = Truefor (ri, ci) in row:bi = (ri//3)*3+ci//3if b != bi:sameBlock = Falsebreakif sameBlock:toRemove = []for i in range(r//3*3,r)+range(r+1, (r//3+1)*3):for j in range(c//3*3, (c//3+1)*3):if (i, j) in self._valid_set and num in self._valid_set[(i,j)]:toRemove.append((i,j,num))if toRemove:print 'in row%d, num %d occurs at the same block %d' %(r, num, b)self._changed = Trueself._removeCandidate(toRemove)return True#2.2 if in a column, a candidate number occurs at the same block,#delete the candidate number from other cells of this blockcols = self._groupByCol( posset )for c, col in cols.items():(r,c) = col[1]b = (r//3)*3+c//3sameBlock = Truefor (ri, ci) in col:bi = (ri//3)*3 + ci//3if b!=bi:sameBlock = Falsebreakif sameBlock:toRemove = []for i in range(r//3*3, (r//3+1)*3):for j in range(c//3*3, c)+range(c+1, (c//3+1)*3):if (i,j) in self._valid_set and num in self._valid_set[(i,j)]:toRemove.append((i,j,num))if toRemove:print 'in col%d, num %d occurs at the same block %d' %(c, num, b)self._changed=Trueself._removeCandidate(toRemove)return Truereturn False

XY-Wing描述起来似乎有些麻烦，事实上它应该是三数集的一种变种。假设有一个数格，该格（我们且称它为A格）有且只有候选数X,Y,在该格所在的house里，也就是它能影响到的行/列/宫里，存在另外两个位置（我们且称它为B格和C格），它们分别有且只有候选数XZ和YZ（注意XZ和YZ如果在同一个房里，就变成显式三数集了，因此该技巧在三数集后用较有成效），如果A格为X，那么B格必然为Z；如果A格为X，那么C格必然为Z，也就是说，在BC两格能共同看到的格子不应该有候选数Z，也就是说可以将Z从BC两格可以看到共同看到的格子中删去。因此，实现的时候，首先是找到XY，即从一个只有两个候选数的格子出发，找出该格子所在的行/列/宫所有只有两个候选数，且这两个候选数中有且只有一个与该格相同的候选数的格，并从这些格中任取两个，如果这两个格的候选数能构成XZ和YZ，即，两个格的候选数的并集减去XY得到一个Z，我们即可将Z从这两个格共同的影响的格中删去。

def _XYWing( self ):self._changed = Falsefor pos, vset in self._valid_set.items():if len(vset)==2:candidate = dict()for i in range(1,10):candidate[i]=[]row = get_conflict_list( pos[0]*9+pos[1] )plist = [divmod(i,9) for i in row]for i in plist:if i in self._valid_set:if len(self._valid_set[i])==2 and \len(vset.intersection(self._valid_set[i]))==1:z = self._valid_set[i].difference(vset).pop()candidate[z].append(i)toRemove = []XZ=NoneYZ=Nonefor i in range(1,10):#XZ and YZ should not be at the same row or columnif len(candidate[i])>=2 :for indices in self._get_n_from_m( 2, len(candidate[i]) ):pos1 = candidate[i][indices[0]]pos2 = candidate[i][indices[1]]uset = self._valid_set[pos1].union(self._valid_set[pos2])uset.remove(i)if uset==vset:XZ = pos1 YZ = pos2seeA = get_conflict_list(pos1[0]*9+pos1[1])seeB = get_conflict_list(pos2[0]*9+pos2[1])seeBoth = set(seeA).intersection(set(seeB))seelist = [divmod(j,9) for j in seeBoth]seelist.remove(pos)for item in seelist:if item in self._valid_set and i in self._valid_set[item]:toRemove.append((item[0], item[1], i))if toRemove:self._changed = Trueprint 'XYWing,', pos, 'as XY', 'and', XZ, 'and', YZ, 'as XZ and YZ respectively'self._removeCandidate(toRemove)return Truereturn False

XYZ-Wing是XY-Wing的一种扩展，A格由XY扩展到XYZ，B格和C格分别为XZ跟YZ，同时，B格和C格中有一个跟A格在同一个宫里。假设B格跟A格在同一个宫里，C或者跟A同行，或者跟它同列（如果同宫的话就是显式三数集了），如果C跟A同行，则在AB所在的宫AC所在的行的交集，除A以外的另外两个格不应该有候选数Z，因为（1）C如果为Z，这一行自然不会再有其他为Z；（2）如果C不为Z，那么C为Y，A跟B的候选数为XZ，即显式数对，AB所在的宫的其他格都应该删除候选数Z。对于C与A同列也是同样的情况。实现的时候，先找出一个有三个候选数的格，并找出其所在的宫的所有可能的XZ，然后再找出其所在的行/列可能的YZ，综合得ABC格。

def _XYZWing( self ):for pos, vset in self._valid_set.items():if len(vset)==3:index = pos[0]*9+pos[1]blk = get_block(index)plist = [divmod(i,9) for i in blk]#vset is XYZcand_XY = []for i in plist:if i in self._valid_set and len(self._valid_set[i])==2 and \self._valid_set[i].issubset(vset):cand_XY.append(i)if not cand_XY:continue#looking for YZ#first in rowrow = get_row(index)for i in set(row).intersection(set(blk)):row.remove(i)plist = [divmod(i,9) for i in row]cand_YZ = []for i in plist:if i in self._valid_set and len(self._valid_set[i])==2 and \self._valid_set[i].issubset(vset):cand_YZ.append(i)toRemove=[]for i in cand_XY:for j in cand_YZ:if self._valid_set[i].union(self._valid_set[j]) == vset:Y = self._valid_set[i].intersection(self._valid_set[j]).pop()for k in [ (pos[0], (pos[1]//3)*3+(pos[1]+3-1)%3), (pos[0], (pos[1]//3)*3+(pos[1]+1)%3) ]:if k!=i and k!=j and k in self._valid_set:if Y in self._valid_set[k]:toRemove.append((k[0],k[1],Y))if toRemove:self._changed = Trueprint 'XYZWing,', pos, 'as XYZ', 'and', i, 'and', j, 'as XY and YZ respectively'self._removeCandidate(toRemove)return True#found not YZ in row, turn to colcol = get_column(index)for i in set(col).intersection(set(blk)):col.remove(i)plist = [divmod(i,9) for i in col]cand_YZ=[]for i in plist:if i in self._valid_set and len(self._valid_set[i])==2 and \self._valid_set[i].issubset(vset):cand_YZ.append(i)toRemove = []for i in cand_XY:for j in cand_YZ:if self._valid_set[i].union(self._valid_set[j]) == vset:Y = self._valid_set[i].intersection(self._valid_set[j]).pop()for k in [( (pos[0]//3)*3+(pos[0]+3-1)%3, pos[1]), ((pos[0]//3)*3+(pos[0]+1)%3, pos[1]) ]:if k!=i and k!=j and k in self._valid_set:if Y in self._valid_set[k]:toRemove.append((k[0],k[1],Y))if toRemove:self._changed = Trueprint 'XYZWing,', pos, 'as XYZ and', i, 'and', j, 'as XY and YZ respectively'self._removeCandidate(toRemove)return Truereturn False

接下来的X-Wing，SwordFish和JellyFish跟显/隐式数对、三数集、四数集之间的关系是相似的。X-Wing说的是如果一个数字正好出现且只出现在某两行（列）的相同的两列（行）上，则这个数字就可以从这两列（行）上其他的单元格的候选数中删除。而SwordFish将这种考虑扩展到三行三列上， 而JellyFish则将其扩展到四行四列上。首先它是以候选数为中心的，并且只考虑行、列。我们可以将候选数一个一个_groupByRow，然后挑出所有在行上只有等于或少于[num]个候选位置的行，任取[num]行并对其所在列做并集，如果正好为[num]列，那么根据这个[num]的不同可以找到X-Wing，SwordFish，JellyFish。同样的情况可以发生在列上。

def _XWing( self, n ):for num, posset in self._candi_pos.items():rows = self._groupByRow(posset)pos = dict()for r, row in rows.items():if len(row)<=n:pos[r]=set()for (r,c) in row:pos[r].add(c)if len(pos)<n:continue#keys stores the rows that have less that n position for num#while pos.items() contains what column are theykeys = pos.keys()for indices in self._get_n_from_m( n, len(pos) ):uset = set()for index in indices:uset = uset.union(pos[keys[index]])#if their union have exactly n len#that mean they are candidates for X-wing(n=2), swordfish(n=3) or JellyFish(n=4)toRemove = []if len(uset)==n:removeR = range(9)for index in indices:removeR.remove(keys[index])removels = [(r,c) for (r,c) in product(removeR, list(uset)) ]for i in removels:if i in self._valid_set and num in self._valid_set[i]:toRemove.append( (i[0], i[1], num) )if toRemove:self._changed = Trueif n==2:print 'X-Wing:',elif n==3:print 'SwordFish:',elif n==4:print 'JellyFish:',print 'in row',for index in indices:print keys[index],print 'num %d occurs only on column' %num,for index in uset:print index,printself._removeCandidate(toRemove)return Truecols = self._groupByCol(posset)pos = dict()for c, col in cols.items():if len(col)<=n:pos[c]=set()for (r,c) in col:pos[c].add(r)if len(pos)<n:continuekeys = pos.keys()for indices in self._get_n_from_m( n, len(pos) ):uset = set()for index in indices:uset = uset.union(pos[keys[index]])if len(uset) == n:toRemove = []removeC = range(9)for index in indices:removeC.remove(keys[index])removels = [(r,c) for (r,c) in product(list(uset), removeC)]for i in removels:if i in self._valid_set and num in self._valid_set[i]:toRemove.append( (i[0], i[1], num) )if toRemove:self._changed = Trueif n==2:print 'X-Wing:',elif n==3:print 'SwordFish:',elif n==4:print 'JellyFish:',print 'in col',for index in indices:print keys[index],print 'num %d occurs only on row' %num,for index in uset:print index,printself._removeCandidate(toRemove)return Truereturn False

唯一矩形法利用数独的唯一性质。唯一矩形由两个候选数，四个数格组成。四个格中至少有一个有一个额外候选数，否则该数独将不唯一。唯一矩形有7种情况可供分析，通过对手册里七种情况的描述，我通过额外候选数的情况来实现这七种情况的分流。
首先是如何到一个矩形，首先我们要分析一个可能的矩形的特征：
（1）四个格分布在两个九宫格里。
（2）组成矩形的四个格中，至少有一个只有两个候选数
（3）另外三个格均包含这两个候选数。
利用这三个特征，我们可以这样找一个矩形：首先找到一个只有两个候选数的数格，在它所在的宫与行（或列）的交集中找另一个顶点，该顶点的特征是其候选数包含这两个候选数；沿着这两个顶点平行过去找另外两个顶点。

def _helper_get_rectangle( self ):for pos, vset in self._valid_set.items():if len(vset) == 2:r1 = (pos[0]//3)*3+(pos[0]+3-1)%3r2 = (pos[0]//3)*3+(pos[0]+1)%3c1 = (pos[1]//3)*3+(pos[1]+3-1)%3c2 = (pos[1]//3)*3+(pos[1]+1)%3candi = [ (r1, pos[1]), (r2, pos[1]), (pos[0], c1), (pos[0], c2) ]candidate = []for i in candi:if i in self._valid_set and vset.issubset(self._valid_set[i]):candidate.append(i)for i in candidate:if i[0]==pos[0]:col1 = [divmod(j,9) for j in get_column(pos[0]*9+pos[1])]col = [ j for j in col1 if j in self._valid_set and vset.issubset(self._valid_set[j]) ]for j in col:r,c = j[0],i[1]if (r,c) in self._valid_set and vset.issubset(self._valid_set[(r,c)]):yield (pos, i, j, (r,c))if i[1]==pos[1]:row1 = [divmod(j,9) for j in get_row(pos[0]*9+pos[1])]row = [ j for j in row1 if j in self._valid_set and vset.issubset(self._valid_set[j]) ]for j in row:r,c = i[0],j[1]if (r,c) in self._valid_set and vset.issubset(self._valid_set[(r,c)]):yield (pos, i, j, (r,c))yield None

找到矩形后，将是对矩形进行分析，以额外候选数及其有多少个格有额外候选数，以及这些格的位置，来决定它是哪一种唯一矩形从而采取相应的战略。
1. 如果只有一个额外候选数：
1.1 矩形中只有一个格有该额外候选数，uniqueRectangle1，该格只能填这个额外候选数
1.2 矩形中有两个格有该额外候选数，uniqueRectangle2，这两个格中必然有一个要填这个候选数，因此将该候选数从这两个格共同能看到的格中删去
1.3 矩形中有三个格有该额外候选数，uniqueRectangle5，如1.2相似，只不过现在将该候选数从这三个格能共同看到的格中删去
2. 如果有两个额外候选数
2.1 如果两个额外候选数在同一个格中，该格只能填这两个额外候选数中的一个（这一点是我现在总结的时候突然想到的）
2.2 如果这两个额外候选数在两个格中，且这两个格在同一行或列或宫中（注意，也就是它们同边），可以考虑使用三数集法；如果这两个矩形候选数中有某个在所在的行/列只有这两个候选位置，那么另一个矩形候选数一定被删除。
2.3 如果这两个额外候选数在两个格中，且这两个格是对角，可以利用强链关系看是否可以删除某个矩形候选数（具体看手册）
3. 有多个额外候选数。由手册中的描述，A肯定是那个只有两个候选数的格，而D则是其对角，只需要检查是否满足手册所说的强链关系。

def _uniqueRectangle( self ):self._changed = Falserec_gen = self._helper_get_rectangle()rec = rec_gen.next()rec_type = 0while rec:rec_can = self._valid_set[rec[0]]canlist = list(rec_can)extra = dict()for i in rec:dset = self._valid_set[i].difference(rec_can)while dset:d = dset.pop()if d not in extra:extra[d] = []extra[d].append(i)toRemove = []if len(extra)==1:exnum = extra.keys()[0]#uniqueRectangle1if len(extra[exnum]) == 1:rec_type = 1toRemove.append( (extra[exnum][0][0], extra[exnum][0][1], canlist[0]) )toRemove.append( (extra[exnum][0][0], extra[exnum][0][1], canlist[1]) )#uniqueRectangle2 if extra[exnum]==2 and uniqueRectangle5 if extra[exnum]==3else:commonset = set()for cell in extra[exnum]:conflict = get_conflict_list(cell[0]*9+cell[1])if commonset:commonset = commonset.intersection(set(conflict))else:commonset = set(conflict)common = [divmod(i, 9) for i in commonset]for i in common:if i in self._valid_set and exnum in self._valid_set[i]:toRemove.append( (i[0], i[1], exnum) )if toRemove:t = len(extra[exnum])if t == 2:rec_type = 2elif t == 3:rec_type = 5elif len(extra) == 2:exnum = extra.keys()if len(extra[exnum[0]])==1 and len(extra[exnum[1]])==1:exset = set()exset.add(exnum[0])exset.add(exnum[1])pos1 = extra[exnum[0]][0]pos2 = extra[exnum[1]][0]index1 = pos1[0]*9+pos1[1]index2 = pos2[0]*9+pos2[1]if index2 == index1:self._changed = TruetoRemove.append( (pos1[0],pos1[1], canlist[0]) )toRemove.append( (pos1[0], pos1[1], canlist[2]) )self._removeCandidate(toRemove)return Truedef _helper_two_extra( scan ):for i in scan:if len(self._valid_set[i])==3 and exset.issubset(self._valid_set[i]):for j in scan:#uniqueRectangle3if len(self._valid_set[j])==2 and \self._valid_set[j].issubset(self._valid_set[i]):for k in scan:for t in self._valid_set[i]:if k!=i and k!=j and t in self._valid_set[k]:toRemove.append( (k[0], k[1], t) )if toRemove:rec_type = 3print 'in rectangle',#for rect in rec:#print rect,print 'in', pos1, pos2, "'s common house'",print 'naked tripple set is used'return rec_typecount1 = 0count2 = 0for i in scan:if canlist[0] in self._valid_set[i]:count1 += 1if canlist[1] in self._valid_set[i]:count2 += 1#uniqueRectangle4if count1 == 0:toRemove.append( (pos1[0], pos1[1], canlist[1]) )toRemove.append( (pos2[0], pos2[1], canlist[1]) )elif count2 == 0:toRemove.append( (pos1[0], pos1[1], canlist[0]) )toRemove.append( (pos2[0], pos2[1], canlist[0]) )if toRemove:rec_type = 4#print 'in rectangle',#for rect in rec:#print rect,#printreturn rec_type#at the same rowif pos1[0] == pos2[0]:row = get_row(index1)row.remove(index2)scanRow = [(r,c) for (r,c) in (divmod(i, 9) for i in row) if (r,c) in self._valid_set]rec_type = _helper_two_extra( scanRow )#at the same columnif pos1[1] == pos2[1]:col = get_column(index1)col.remove(index2)scanCol = [(r,c) for (r,c) in (divmod(i,9) for i in col) if (r,c) in self._valid_set]rec_type = _helper_two_extra( scanCol )#at the same blockif pos1[0]//3==pos2[0]//3 and pos1[1]//3==pos2[1]//3:blk = get_block( index1 )blk.remove(index2)scanBlk = [(r,c) for (r,c) in (divmod(i,9) for i in blk) if (r,c) in self._valid_set]rec_type = _helper_two_extra( scanBlk )#uniqueRectangle6if pos1[0]!=pos2[0] and pos1[1]!=pos2[1]:posset1 = self._candi_pos[canlist[0]]posset2 = self._candi_pos[canlist[1]]row1 = self._groupByRow(posset1)row2 = self._groupByRow(posset2)col1 = self._groupByCol(posset1)col2 = self._groupByCol(posset2)if (len(row1[pos1[0]])==2 or len(col1[pos1[1]])==2) and \(len(row1[pos2[0]])==2 or len(col1[pos2[1]])==2):toRemove.append( (pos1[0], pos1[1], canlist[0]) )toRemove.append( (pos2[0], pos2[1], canlist[0]) )elif (len(row2[pos1[0]])==2 or len(col2[pos1[1]])==2) and \(len(row2[pos2[0]])==2 or len(col2[pos2[1]])==2):toRemove.append( (pos1[0], pos1[1], canlist[1]) )toRemove.append( (pos2[0], pos2[1], canlist[1]) )if toRemove:rec_type = 6print 'uniqueRectangle6'if not toRemove:#see if it satisfies requirements of uniqueRectangle7#A is definitely rec[0] while D is definitely rec[3]#test whether a candidate occures both only twice on D's row and columnD = rec[3]Dindex = D[0]*9+D[1]Drow = [ divmod(i,9) for i in get_row(Dindex) ]Dcol = [ divmod(i,9) for i in get_column(Dindex) ]row = [ (r,c) for (r,c) in Drow if (r,c) in self._valid_set ]col = [ (r,c) for (r,c) in Dcol if (r,c) in self._valid_set ]countAr = 0countBr = 0countAc = 0countBc = 0for i in row:if canlist[0] in self._valid_set[i]:countAr += 1if canlist[1] in self._valid_set[i]:countBr += 1for i in col:if canlist[0] in self._valid_set[i]:countAc += 1if canlist[1] in self._valid_set[i]:countBc += 1if (countAr==1 and countAc==1):toRemove.append( (D[0],D[1], canlist[1]) )elif (countBr==1 and countBc==1):toRemove.append( (D[0], D[1], canlist[0]) )rec_type= 7if toRemove:self._changed = Trueprint 'uniqueRectangle%d' %rec_type,for i in rec:print i,print self._removeCandidate( toRemove )return Truerec = rec_gen.next()return False

至于X-Chain，XY-Chain和ForcingChain，我只能感觉到他们应该也是相通的，可是具体要实现起来，我还是觉得麻烦，不知道从何下手。这两天被这个东西搞到有些沮丧，为了换一下心境，我便决定先总结一下吧。好久没有写博客了，当是对我这段时间的一点总结。说实话，热情已经下跌了很多，这段时间很无聊，很无聊，还是换点别的事情做吧~！

查看更多 下一篇