51. N 皇后（困难）
题目描述：
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击，即使其中任意两个皇后都不同列、同行和在一条斜线上。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
文章图片
文章图片
【leetcode|LeetCode—51. N 皇后（困难）】考察重点：需要找出所有情况，应立刻想到DFS，同时为了方便查找，使用二维数组代替链表进行遍历。使用isLegal()函数判断斜边，列是否存在Queen；DFS按行进行递归，每次在当前行，寻找合法的列插入Queen，并进入下一行。最终当递归到最后一行+1时，说明当前分布满足条件，加入结果链表list。
List>list;
public boolean isLegal(char map[][], int x, int y){
for(int i = 0;
i < map.length;
i ++){
if(map[i][y] != '.')
return false;
}
for(int i = 1;
i < map.length;
i ++){
if(x+i < map.length && y+i = 0 && y-i >= 0 && map[x - i][y - i] != '.')
return false;
if(x+i < map.length && y-i >= 0 && map[x + i][y - i] != '.')
return false;
if(x-i >= 0 && y+i < map.length && map[x - i][y + i] != '.')
return false;
}
return true;
}
public int dfs(char[][] map, int x){
if(!(x < map.length)){
List single = new ArrayList<>();
for(int i = 0;
i < map.length;
i ++)
single.add(String.valueOf(map[i]));
list.add(single);
return 0;
}
for(int y = 0;
y < map.length;
y ++){
if(isLegal(map, x, y)) {
map[x][y] = 'Q';
dfs(map, x + 1);
map[x][y] = '.';
}
}
return 0;
}
public List> solveNQueens(int n) {
list = new ArrayList<>();
char[][] map = new char[n][n];
for(int i = 0;
i < n;
i ++)
for(int j = 0;
j < n;
j ++)
map[i][j] = '.';
dfs(map, 0);
return list;
}
推荐阅读
- LeetCode--689_Maximum_Sum_of_3_NonOverlapping_Subarrays
- 如何为回归问题选择ML算法（）
- LeetCode|117. Populating Next Right Pointers in Each Node II刷题笔记
- R教程中的算法交易
- #Leetcode# 448. Find All Numbers Disappeared in an Array
- 主动学习（好奇的AI算法）
- 算法|一文详解三维重建中的立体匹配
- 算法|三维重建——相机几何参数标定
- 蓝桥杯|第十二届蓝桥杯python