数据结构——DFS深度优先遍历之n皇后问题
n皇后是指将n个皇后放在n-n的国际象棋棋盘上，使皇后不能相互攻击到，即任意两个皇后不能再同一行、同一列或同一斜线上。
算法基本思路：
1.当N个皇后摆放好，依次输出
2.对每行U的0-N列遍历，比较第U个皇后是否会发生冲突（横、竖、对角线）
3.放置好后对该皇后、横、竖、斜对角线做标记，下一次放置 则不会出现在以上地方
需要变量：
q[n][n] 棋盘，不放置为‘.’,放置则为‘Q’
col[n] bool的列标记，标记为True则该列不能再放皇后
dg[n+u-i]、udg[u+i] 对角线、反对角线bool标记
n+u-i、u+i 数学推理过程：
1.对角线函数表示 y=x+b 则截距表达为b = y-x，为防止存在负数 则表示为 n+y-x 即 n+u-i
2. 反对角线函数表示为y=-x+b 则截距表达为 b = y+x 即u+i
def dfs(u): if u==n: print(q) return for i in range(0,n): if !col[i] and !dg[n+u-i] and !udg[u+i]: q[u][i] = 'Q' col[i] = dg[n+u-i] = udg[u+i] = True dfs(u+1) # 回溯 q[u][i] = '.' col[i] = dg[n+u-i] = udg[u+i] = False
查看21道真题和解析
