N皇后问题----回溯法

版权声明：本文为博主原创文章，未经博主允许不得转载。https://blog.****.net/qq_38148754
本人水平有限，同在学习，如若发现问题还请及时批评指正。

问题描述：

将n个皇后放置在n * n的棋盘上，使得任意两个皇后不能相互攻击。即任意两个皇后都不在同一行，同一列，和同一条斜角线上。

问题分析：

1. 回溯法

回溯法的思想和基本概念在这里就不再详细阐述，想要深入了解的朋友可以自行查找相关资料，在这里我只简单说明一下：
在求解满足某些约束条件最优解的问题中，通过一个规范函数来测试正在构造的一个可能的解序列，若确定该解不可能构成一个可行解则跳过接下来的构造过程，舍弃该解，回溯到上一步，进行下一个构造过程。
拿n皇后问题举例来说，例如一个4*4的棋盘，在构造解的过程中，若第一个皇后放在一行一列，第二个放在二行二列，此时检测到两个皇后已经在同一条斜角线上，则可停止该构造，因为已经能够确定该序列不可能构成有效解。则回溯到上一步，即决定第二个皇后该放置在哪个位置。这样就免去了做构造第三、第四个皇后的无用功。
这个过程说的通俗一点就是你可以无限悔棋。例如在走迷宫时，在每个路口你都从中选择一条路，当你走到一半时发现这是一条错误的道路，便退回到上一个路口重新选择另一条路，直到找出最后的出口。

2. 规范函数

n皇后问题的规范函数在于使得任意两个皇后不能相互攻击，同行同列的验证比较简单。对于不在同一条斜角线上的约束，可以发现，对于在棋盘同一条左上到右下的斜角线上所有元素都有相同的行减列值，而左下到右上斜角线上的元素都有相同的行加列值。
假设有两个皇后被放置在（i，j）和（k，l）上，则当
i - j = k - l 或 i+j = k+l
时吗他们在同一条斜角线上。将两个等式分别变换为
j - l = i - k 和 j - l = k - i
则有 | j - l | = | i - k | 时两个皇后在同一条斜角线上。
故可以写规范函数place（K,col）用来测定将皇后放置在某一行是否合法，及满足不能相互攻击的条件，相应的代码示例和相应的注解如下方所示

参考代码：

规范函数place（k， col）
其中列表 col（k） 保存第k个皇后放置在第 col（k） 列。
该函数测试第k个皇后 放在第col（k）列是够满足条件，若满足则返回真，否则返回假。

	def place(self, k, col) :
		i = 0
		while i < k :
			if (col[i] == col[k]) or(abs(col[i]-col[k]) == abs(i - k)) :
				return False
			i = i+1
		return True

回溯法解决N皇后问题

	def solveNQueens(self, n):
		#最终结果用字符串表示，其中
		# ‘.’表示空，‘Q’表示放置皇后
		answer = []		  #保存最终的所有解
		ori = '.' * n     #初始化每行都为空
		result = []  	  #存放每次构造的可行解
		col = [0]*n       #所有列初始化为0
		col[0] = -1
		k = 0
		while k >= 0 :
			col[k] = col[k] +1
			while col[k] < n and not self.place(k, col) :  #寻找一个可行的列
				col[k] = col[k] +1
			if col[k] < n:    #找到一个合法的列
				if k == n-1:  		#如果此时已经处理到最后一行，表示已经产生一组可行解，加入到最终的解列表中
					#该代码块 (接下来的5行） 可理解为打印输出结果
					for i in range(n):
						index = col[i]
						result.append(ori[:index]+'Q'+ori[index+1:])
					answer.append(result)
					result = []     #清空result，以便下一次使用
				else:         		#该行不是最后一行，则行数加一，接着处理
					k = k + 1
					col[k] = -1
			else:             #没有找到合法的列，则回溯到上一步
				k = k-1
		return answer

结果示例：
以下是n=5时的结果