春招面试之N皇后问题
春招面试之N皇后问题
手撕算法系列之N皇后问题
0.题目
关于N皇后总共有两道题：
第一道题：求出所有皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
第二道题：求出所有满足皇后的解法个数
1.深度优先搜索
【思想】
使用一个数组queencol表示某一行已经被皇后占据的列，从上往下依次试探每行皇后可以放在哪些行。每次试探都与前面所有放好的皇后检查是否有冲突。
假设当前试探的位置为 (col,row)，而第 i 行已经有一个皇后放置在 (queencol[i],i)。这两个皇后有三种冲突的可能：
- 同一列：
col == queencol[i]
- 撇：
col-queencol[i] == i-row
- 捺：
col-queencol[i] == row-i
同一列好说，那撇捺怎么是上述式子呢？
建立如图所示的坐标系，设第2行(index从0开始)皇后坐标为(col,row)。那么撇就是蓝色线。捺就是橙色线。
上面已经假设，第 i 行已经有一个皇后放置在 (queencol[i],i)，那么由数学基础知识，线性斜率知道斜率如何求，而如上图可知道，斜率分别为1(捺)与-1(撇)。
上述问题就转化为：两点坐标求斜率，点A(col,row)，点B(queencol[i],i)。
那么对于撇：
(i-row)/(queencol[i]-col)=-1 ，也就是i-row = col-queencol[i]，两边变形得到：col-queencol[i] == i-row
对于捺：
(i-row)/(queencol[i]-col)=1，也就是i-row = queencol[i]-col，两边变形得到：col-queencol[i] == row-i
下面就来实现一下。
【实现】
def DFS(n,row,cur_res):
global count
# 递归终止条件
if row>n-1:
print(cur_res)
count+=1
res.append(cur_res)
print(res)
for col in range(n):
# 检测当前列冲突
ok = True
for i in range(row):
# 列冲突与撇、捺冲突queencol
if col == queencol[i] or col-queencol[i] == row-i or col-queencol[i] == i-row:
ok = False
break
# 判断当前列是否冲突
if not ok:
continue
# 当前列无冲突,皇后占据当前位置
queencol[row]=col
# 递归下一行
DFS(n,row+1,cur_res+[col])
n = 4 # 棋盘大小
queencol = [0]*n # 某一行已经被皇后占据的列
count = 0
res = []
DFS(n,0,[])
print("总共有"+str(count)+"种解决方案")
2.空间换时间
【思想】
注意到皇后位置的限制条件的本质，其实就是说每一竖、每一撇、每一捺上只能有一个皇后。
当试探一个位置时，如果能够立即知道它所在的竖、撇、捺是否已被占用，就可以在 O(1) 的时间内检查冲突了。
为此，将刚刚放置的皇后所在的竖、撇、捺标记为已占用，并在调用返回之后清除标记。
对于撇捺上述我们知道它们的规律，上述的规律，同时还可以得到撇捺的另一个规律：
撇：行+列=一个常数
捺：行-列=一个常数
在对冲突存储的时候，可以采用布尔来判断，也可以用set集合判断，下面给出两种解决方案！
【集合空间换时间】
def DFS(n,row,queencol):
global count
# 递归终止条件
if row>n-1:
print(queencol)
res.append(queencol)
count+=1
for col in range(n):
# 碰撞判断
if col in shu or (row+col) in pie or (row-col) in na:
continue
shu.add(col)
pie.add(row+col)
na.add(row-col)
DFS(n,row+1,queencol+[col])
# 递归回去清理空间
shu.remove(col)
pie.remove(row+col)
na.remove(row-col)
n = 4
shu = set()
pie = set()
na = set()
count = 0
res = []
DFS(n,0,[])
print("总共有"+str(count)+"种解决方案")
print(res)
print(len(res))
【布尔空间换时间】
这个方法申请撇捺空间大小的时候，可以推一下，都为2*n-1。
def DFS(n,row,queencol):
global count
# 递归终止条件
if row>n-1:
print(queencol)
res.append(queencol)
count+=1
for col in range(n):
j = row+col
k = col-row
if shu[col] or pie[j] or na[k]:
continue
shu[col]=pie[j]=na[k]=True
DFS(n,row+1,queencol+[col])
shu[col]=pie[j]=na[k]=False
n = 4
shu = [False]*n
pie = [False]*(2*n-1)
na = [False]*(2*n-1)
count = 0
res = []
DFS(n,0,[])
print("总共有"+str(count)+"种解决方案")
print(res)
print(len(res))
3.位运算必杀技
为了更好的减少空间内存，最后采用位运算来实现N皇后！
如果我们已经知道每一行的空位，也就是皇后可取位置，那么时间复杂度则会大大降低，基于这个思想，通过位运算获取每一行的空位，来优化算法。
位运算常用：
X&1==1 or ==0
x = x & (x-1) => 清零最低位的1 例如： x=110 x-1=101 x&x-1=100
x & -x => 得到最低位的1
x & ~x => 0
【代码实现】
位运算常用：
X&1==1 or ==0
x = x & (x-1) => 清零最低位的1 例如： x=110 x-1=101 x&x-1=100
x & -x => 得到最低位的1
x & ~x => 0
注意一点，在需要通过math函数来求当前p为2的多少次方，而这个多少次方就是我们每次皇后存放的真实列。
import math
def DFS(n,row,col,pie,na,queencol):
global count
# 递归终止条件
if row>n-1:
print(queencol)
res.append(queencol)
count+=1
bits = (~(col|pie|na)) & ((1<<n)-1) # 得到当前行的空位
while bits:
p = bits&-bits # 取最低位1
DFS(n,row+1,col|p,(pie|p)<<1,(na|p)>>1,queencol+[int(math.log(p,2))])
bits = bits&(bits-1)
n = 4
count = 0
res = []
DFS(n,0,0,0,0,[])
print("总共有"+str(count)+"种解决方案")
print(res)
print(len(res))