题目链接： N皇后
题意：
- 给定一个 n*n 大小的棋盘，要求放入 n 个皇后，使得皇后之间不会相互攻击
- 皇后的攻击路线是：同行、同列、同对角线
思路：
- 深度优先搜索，DFS
- 用三个数组表示当前状态下，哪些列和对角线已经被占据了，如果被占据了，就不能放入新的皇后，如果没有被占据，就放入新的皇后，并进行下一步搜索
- 不需要对行的访问情况进行记录，因为搜索方向是向下搜索，一行只能有一只皇后
- 列对角线数组需要开到 2*n ，因为对角线数量比n大
代码（Golang）：
func solveNQueens(n int) [][]string { ans:=make([][]string,0) tmp:=make([][]byte,n) for i:=0;i<n;i++{ tmp[i]=make([]byte,n) for j:=0;j<n;j++{ tmp[i][j]='.' } } visc,vislr,visrl:=make([]bool,n),make([]bool,n*2),make([]bool,n*2) var dfs func(i int) dfs=func(i int){ if i==n{ temp:=make([]string,n) for k:=0;k<n;k++{ temp[k]=string(tmp[k]) } ans=append(ans,temp) return } for j:=0;j<n;j++{ if !visc[j] && !visrl[i+j] && !vislr[i-j+n]{ visc[j],visrl[i+j],vislr[i-j+n]=true,true,true tmp[i][j]='Q' dfs(i+1) tmp[i][j]='.' visc[j],visrl[i+j],vislr[i-j+n]=false,false,false } } }dfs(0) return ans}
局座张召忠
