1. 暴力破解法与精确覆盖法

暴力破解法

　没有写暴力破解的代码。这一块的大概思路是：

  1. 确定过滤规则，确定可能性设定规则(如图中假定过滤后H3与H7分别能够填入1,2与1,3,5。那么1填入H3的可能性>1填入H7的可能性)
  2. 根据规则填入可能性最大的数字并将操作入栈
  3. 重复2步骤，若最终填满81个单元则成功，若出现无解状态则出栈返回2填入下一可能的数字。
    　从网上各路神仙的分析结果来看，对于低中层次的数独题目，用这种方法是最高效的，算法足够合理的话基本能够在一秒钟之内完成。

精确覆盖法

　首先放精确覆盖问题的百科，以及它的简单应用
　简单来说，精确覆盖法就是将原本逻辑难以理解的问题转化为人类大脑更容理解的问题。例如数独问题，精确覆盖法将原本复杂的行列宫判断过滤流程简化为在二维矩阵中选取互不冲突的81行。这篇博客将数独问题转化为精确覆盖问题解释的比较精确。
　为了便于理解，下面将详述数独算法如何转化为精确覆盖法。

2. 数独问题转化为精确覆盖问题

确定数独(9*9)规则

  1. 每个格子只能填一个数字
  2. 每行每个数字只能填一遍
  3. 每列每个数字只能填一遍
  4. 每宫每个数字只能填一遍

将规则转述为精确覆盖法的条件

  1. 每个格子只能填一个数字，共有81种情况
  2. 每行1-9共九个数字都需要填一遍，共有81种情况
  3. 每列1-9共九个数字都需要填一遍，共有81种情况
  4. 每宫1-9共九个数字都需要填一遍，共有81种情况

根据条件确定精确覆盖阵填写规则

  1. 1-81列为条件1的数学模型，例如，在(3,2)中填入数字，则将2*9+2=29列置为1，其余80列为0
  2. 82-162列为条件2的数学模型，例如，在第2行中填入数字9，则将81+(1*9+9)列置为1，其余80列为0
  3. 163-243列为条件3的数学模型，例如，在第3行中填入数字7，则将162+(2*9+7)列置为1，其余80列为0
  4. 244-324列为条件4的数学模型，例如，在第5宫中填入数字1，则将243+(4*9+1)列置为1，其余80列为0

根据如上规则，总结如下

  • 在(5,7)中填入数字3，根据规则1，将43列置为1。根据规则2，将120列置为1。根据规则3，将219列置为1。根据规则4，将291列置为1。
  • 对于9*9数独阵来说，填写一个数字，共有729种情况，转化为精确覆盖问题，既精确覆盖阵共有729行，324列。
  • 找出其中的81行，保证其每一列有且只有一个1，则最终的数独矩阵有解。

3. 思考、改进与代码

　一种网红算法叫做dance link，它应该是精确覆盖问题的最高效解决方案。但归根到底，精确覆盖问题是一个npc问题，虽然根据现有数独阵求解唯一答案可以在多项式时间内完成，但是对于生成所有数独阵这样的问题就无法在O(n^k)内解决。如果要将代码写的完美，填写单一数字的方法应该在求解单一数独阵与生成所有数独阵中通用，并且能够避免迭代回溯。

精确覆盖阵的变形与去重

　1. 为方便在python中编写，我们将324列的01矩阵变形为4列1-81矩阵，对于给定简单数独阵，我们先将其转换为精确覆盖阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#已知数独阵转为精确覆盖阵,0为空单元格
def sodukuToRect(soduku):
	position = 0
	rect = []
	for num in soduku:
		if num == 0:
			position = position + 1
			continue
		pRow = int(position / 9)
		pCol = position % 9
		row = pRow*9 + num
		col = pCol*9 +num
		pGon = ((pRow % 3 * 3) + (int(pCol/3) % 3) + 1)*9+num
		res = (position+1,row,col,pGon)
		rect.append(res)
		position = position+1
	return rect

　2. 对结果矩阵进行去重，首先需要初始化数独精确覆盖阵所有解，再跟据结果过滤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#初始化全精确覆盖阵
def coverArray():
	rect = []
	for position in range(81):
		pRow = int(position / 9)
		pCol = position % 9
		for num in range(9):
			num = num + 1
			row = pRow*9 + num
			col = pCol*9 +num
			pGon = ((pRow % 3 * 3) + (int(pCol/3) % 3))*9+num
			res = (position+1,row,col,pGon)
			rect.append(res)
	return rect
    
    
#去重算法，非迭代回溯O(n^2),testRect为已知阵，rect为全阵
def removeImpossible(testRect, rect):
	newRect = [i for i in rect]
	for line in rect:
		remove = 0
		for testLine in testRect:
			if testLine[0] == line[0] or testLine[1] == line[1] or testLine[2] == line[2] or testLine[3] == line[3]:
				newRect.remove(line)
				break
	noConflictNumList = [i for i in newRect]
	for i in range(len(newRect)):
		for j in range(i+1,len(newRect)):
			iline = newRect[i]
			jline = newRect[j]
			if iline[0] == jline[0] or iline[1] == jline[1] or iline[2] == jline[2] or iline[3] == jline[3]:
				if iline in noConflictNumList:
					noConflictNumList.remove(iline)
				if jline in noConflictNumList:
					noConflictNumList.remove(jline)
				break
	newTestRect = [i for i in testRect] + noConflictNumList
	for i in noConflictNumList:
		newRect.remove(i)
	return(newTestRect, newRect)

　3. 进行到这一步，可以得出新的精确覆盖阵，显而易见的错误都已经被过滤掉。之后再进行暴力破解或舞蹈链算法求解。虽然优化后的代码比直接迭代回溯的方式运算量小了很多，但还是无法避免最终迭代回溯计算这一逻辑，也就是说对于高难度数独阵，去重算法并不能过滤绝大部门错误行，优化效果不明显。

关于求解数独阵的思考

　我们可以根据一下逻辑进行分析：

  1. 数独阵求解或生成是一个不确定问题，既可能是p,或np问题。
  2. 精确覆盖问题已经被定义为npc问题。
  3. 由1.2可知，将数独问题转化为精确覆盖问题相当于将一个np及以下时间复杂度的问题转化为np时间复杂度的问题。

    本质上讲，将数独阵转为精确覆盖阵是一种非理性的转化方式，虽然便于人脑理解，但会加大计算的时间复杂度。

　解决数独问题的关键应该是寻找避免迭代回溯的方案。
　当然，生成所有数独阵，再对数独题目进行匹配的方式是最高效的。不包括矩阵变形的数独阵共有5472730538种，普通CPU用回溯法计算高难度数独阵的时间在800ms左右，假设生成一个数独阵所需的平均时间是8s，那么单台机器利用CPU生成所有数独阵大概需要1300年。幸运的是，这对于分布式计算大当其道的今天，已经不算什么问题了。 　

3. 题外话

　我们在求解数独问题时，在已知答案存在且唯一的情况下，却要通过复杂的计算过程才能找到答案，这是十分不合理的。所有问题的本质，都是映射。我们在求解问题时更多的是去寻找问题与答案间的映射关系，进而去求解答案。
　我更愿意相信，问题的答案是问题本身这一抽象概念。如果非要形容的话:

问题与答案是两个指向相同内存段的指针。

　因此无论是数独问题，np问题，还是更宽泛的任何已知与未知问题的答案，它们一直存在。而逻辑为我们提供了解题思路，却有可能屏蔽了我们直接获取答案的方法。

数据解法源码(未完成版)