数独人工解法的一些技巧及其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 = False
		for pos, validset in self._valid_set.items():
			if len(validset)<=0:
				self._invalid = False
			elif len(validset) == 1:
				num = validset.pop()
				validset.add(num)
				print 'pos', pos, 'has only one candidate: %d' %num
				self._changed = True
				return True
		return False

	def _hiddenSingleNumber( self ):
		self._changed = False
		for num, posset in self._candi_pos.items():
			#_groupByRow,_groupByCol,_groupByBlock is helper function
			rows = 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 = True
					return True
			cols = 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 = True
					return True
			blks = 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 = True
					return True
		return 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 index
			i = n-1
			if index[i]<m-n+i:
				index[i]+=1
			else:
				index[i-1]+=1
				while i>0 and index[i-1]>=m-n+i:
					i -= 1
					index[i-1]+=1
				for 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 set
	def _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 list
			for 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 position
			if 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,
						print
						self._removeCandidate(toRemove)
						self._changed = True
						return True
		return 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 = True
						print '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 True
		return False

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

	def _regionDeletion( self ):
		self._changed = False
		for 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/column
			for b, blk in blks.items():
				(r,c) = blk[1]
				sameRow = True
				sameCol = True
				for (ri,ci) in blk:
					if ri!=r:
						sameRow = False
					if ci!=c:
						sameCol = False
					if not (sameRow or sameCol):
						break
				if 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 = True
						print 'in block%d, num %d occurs at the same row %d' %(b, num, r)
						self._removeCandidate(toRemove)
						return True
				
				if 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 = True
						print '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 block
			rows = self._groupByRow( posset )
			for r, row in rows.items():
				(r,c) = row[1]
				b = (r//3)*3+c//3
				sameBlock = True
				for (ri, ci) in row:
					bi = (ri//3)*3+ci//3
					if b != bi:
						sameBlock = False
						break
				if 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 = True
					self._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 block
			cols = self._groupByCol( posset )
			for c, col in cols.items():
				(r,c) = col[1]
				b = (r//3)*3+c//3
				sameBlock = True
				for (ri, ci) in col:
					bi = (ri//3)*3 + ci//3
					if b!=bi:
						sameBlock = False
						break
				if 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=True
					self._removeCandidate(toRemove)
					return True
		return 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 = False
		for 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=None
				YZ=None
				for i in range(1,10):
					#XZ and YZ should not be at the same row or column
					if 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 = pos2
								seeA = 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 = True
						print 'XYWing,', pos, 'as XY', 'and', XZ, 'and', YZ, 'as XZ and YZ respectively'
						self._removeCandidate(toRemove)
						return True
		return 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 XYZ
				cand_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 row
				row = 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 = True
								print '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 col
				col = 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 = True
								print 'XYZWing,', pos, 'as XYZ and', i, 'and', j, 'as XY and YZ respectively'
								self._removeCandidate(toRemove)
								return True
		return 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 they
			keys = 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 = True
						if 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,
						print
						self._removeCandidate(toRemove)
						return True
			cols = 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:
				continue
			keys = 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 = True
						if 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,
						print
						self._removeCandidate(toRemove)
						return True
		return 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)%3
				r2 = (pos[0]//3)*3+(pos[0]+1)%3
				c1 = (pos[1]//3)*3+(pos[1]+3-1)%3
				c2 = (pos[1]//3)*3+(pos[1]+1)%3
				candi = [ (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 = False
		rec_gen = self._helper_get_rectangle()
		rec = rec_gen.next()
		rec_type = 0
		while 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]
				#uniqueRectangle1
				if len(extra[exnum]) == 1:
					rec_type = 1
					toRemove.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]==3
				else:
					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 = 2
						elif t == 3:
							rec_type = 5
			elif 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 = True
						toRemove.append( (pos1[0],pos1[1], canlist[0]) )
						toRemove.append( (pos1[0], pos1[1], canlist[2]) )
						self._removeCandidate(toRemove)
						return True
					def _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:
									#uniqueRectangle3
									if 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 = 3
										print 'in rectangle',
										#for rect in rec:
										#	print rect,
										print 'in', pos1, pos2, "'s common house'",
										print 'naked tripple set is used'
										return rec_type
						count1 = 0
						count2 = 0
						for i in scan:
							if canlist[0] in self._valid_set[i]:
								count1 += 1
							if canlist[1] in self._valid_set[i]:
								count2 += 1
						#uniqueRectangle4
						if 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,
							#print
							return rec_type
					#at the same row
					if 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 column
					if 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 block
					if 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 )

					#uniqueRectangle6
					if 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 = 6
							print '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 column
				D = 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 = 0
				countBr = 0
				countAc = 0
				countBc = 0
				for i in row:
					if canlist[0] in self._valid_set[i]:
						countAr += 1
					if canlist[1] in self._valid_set[i]:
						countBr += 1
				for i in col:
					if canlist[0] in self._valid_set[i]:
						countAc += 1
					if canlist[1] in self._valid_set[i]:
						countBc += 1
				if (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= 7
			
			if toRemove:
				self._changed = True
				print 'uniqueRectangle%d' %rec_type,
				for i in rec:
					print i,
				print 
				self._removeCandidate( toRemove )
				return True
			rec = rec_gen.next()
		return False

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

评论

8 楼 master11 2017-10-13  

你好，博主
看完你的解释，好厉害啊！！佩服。
如果想运行看一下效果，请问从哪个函数开始调用啊？

7 楼 evasiu 2016-10-12  

chenxun1012033254 写道

lz这么辛苦我也是醉了
作为一名oier
我说有一个算法叫做dancing links,解决这一类匹配问题十分的高效。
十分的高效...lz感兴趣自己去百度啊

dancing link是机器解法，其实我前面的文章也有实现。这个人工解法主要原因是1）量化一个数独的“难度”，这样才能制造不同等级的数独题；2）做出合理的提示。

6 楼 chenxun1012033254 2016-08-13  

lz这么辛苦我也是醉了
作为一名oier
我说有一个算法叫做dancing links,解决这一类匹配问题十分的高效。
十分的高效...lz感兴趣自己去百度啊

5 楼 Boyer 2012-06-14  

evasiu 写道

呵呵，谢谢Boyer的赞赏。事实上我一直在做毕业倒计时，现在是离毕业还有365天，哈哈。不过我是喜爱学习的，只是觉得读研这两年很不自由，恨不得早早毕业，可以自己做主。

"赞赏"这俩字真是太抬举我了，我09年本科毕业的，我们应该年龄差不多。我倒是很羡慕在学校的生活啊，莫非学校是座围城，城外的想进去，城内的想出来。你平时聊QQ吗，或者其他通讯方式，我们多交流交流？

4 楼 evasiu 2012-06-14  

呵呵，谢谢Boyer的赞赏。事实上我一直在做毕业倒计时，现在是离毕业还有365天，哈哈。不过我是喜爱学习的，只是觉得读研这两年很不自由，恨不得早早毕业，可以自己做主。

3 楼 Boyer 2012-06-14  

很偶然的来到你的博客，之后又看了些其他的文章，感觉颇有收获。总是被各种浮躁的信息包围，楼主的文章给了我耳目一新的感觉。我也是向往自由的人，喜欢读书听音乐。只是现在已经是个社会人了，被一些压力和责任感束缚着，人也渐渐变得俗起来了，哈哈哈。
另外，后来发现楼主是个女孩子哦，不简单，对您的敬仰又高了一分。

2 楼 evasiu 2012-06-13  

Boyer 写道

作者很喜欢王小波啊！python没学过，算法很少看，我是看文章里面小说的标题才进来的。哈哈
楼主研究算法，好厉害啊，我同学还有我身边的人群里都找不到这样的人了。楼主加油，祝福你

确实是很喜欢王小波啊，呵呵。记得有一回我同学来我宿舍，看到我书架上一排王小波和张爱玲的书，说了一句，“哇，自由人来着”。我觉得这句话大概说出了我的本质吧。一直在追求自由，因而会很喜欢追求独立自由的作者，呵呵。至于算法，我这个大概就算是个新手吧，呵呵。

1 楼 Boyer 2012-06-13  

作者很喜欢王小波啊！python没学过，算法很少看，我是看文章里面小说的标题才进来的。哈哈
楼主研究算法，好厉害啊，我同学还有我身边的人群里都找不到这样的人了。楼主加油，祝福你