春招面试之N皇后问题
- 2019 年 10 月 6 日
- 笔记
手撕算法系列之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))
