皇后问题"/>
代码随想录Day25 回溯算法 LeetCode T51 N皇后问题
目录
前言
LeetCode T51 N皇后问题
题目思路:
回溯三部曲:
2.终止条件
3.一次搜索逻辑
4.isValid合法性判断
5.Array2List
题目代码:
总结:
前言
又来到了我们的周末,今天我们挑战一道困难题:N皇后问题,相信大家都玩过一个经典的小游戏:8皇后
游戏规则是:在一个n*n的棋盘上,放置nge 皇后,要求每个皇后所在的一排一列并且对角线都不能存在皇后,放满n个皇后即为胜利.
LeetCode T51 N皇后问题
游戏链接:八皇后游戏 (gitee.io)
题目链接:51. N 皇后 - 力扣(LeetCode)
题目思路:
这题我们仍然使用回溯算法解决问题
首先我们画出树状图,我们以三皇后举例(无解)
回溯三部曲:
1.回溯函数参数
参数我们取一个二维数组(来记录棋盘的情况),一个n来控制我们树的宽度,也就是棋盘的宽度和高度,一个r变量来记录我们此刻位于哪一行
public void backtracking(char[][] chessboard,int n,int r)
2.终止条件
我们发现这道题的取值结果仍然是在叶子结点,所以我们的终止条件就是遍历到最后一行就开始收割结果
if(r == n){res.add(Array2List(chessboard));return;}
3.一次搜索逻辑
for循环,从0开始遍历到n即可,如果判断合法,就填入'Q',再实现回溯即可
这里不用进行去重操作,因为每一排只取一个值
for(int i = 0;i<n;i++){if(isVaild(r,i,n,chessboard)){chessboard[r][i] = 'Q';backtracking(chessboard,n,r+1);chessboard[r][i] = '.';}}
4.isValid合法性判断
这里我们需要判断棋盘皇后的落点是否合法
public boolean isVaild(int row,int col,int n,char[][] chessboard ){//竖着for(int i =0;i<row;i++){if(chessboard[i][col] == 'Q'){return false;}}for(int i=row-1,j =col-1;i>=0&&j>=0;i--,j--){if(chessboard[i][j] == 'Q'){return false;}}for(int i=row-1, j=col+1;i>=0&&j<=n-1;i--,j++){if(chessboard[i][j] == 'Q'){return false;}}return true;}
5.Array2List
这里细心地小伙伴就会发现我创建的Array2List是自己创建的,因为这里需要进行一次chessboard和list的一次转换,这里我们需要实现list下的这个自定义方法
public List Array2List(char[][] chessboard) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}
题目代码:
class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char chessboard[][] = new char[n][n];for(char[] c :chessboard){Arrays.fill(c,'.');}backtracking(chessboard,n,0);return res;}public void backtracking(char[][] chessboard,int n,int r){if(r == n){res.add(Array2List(chessboard));return;}for(int i = 0;i<n;i++){if(isVaild(r,i,n,chessboard)){chessboard[r][i] = 'Q';backtracking(chessboard,n,r+1);chessboard[r][i] = '.';}}}//定义接口public List Array2List(char[][] chessboard) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}//检查合法性public boolean isVaild(int row,int col,int n,char[][] chessboard ){//竖着for(int i =0;i<row;i++){if(chessboard[i][col] == 'Q'){return false;}}for(int i=row-1,j =col-1;i>=0&&j>=0;i--,j--){if(chessboard[i][j] == 'Q'){return false;}}for(int i=row-1, j=col+1;i>=0&&j<=n-1;i--,j++){if(chessboard[i][j] == 'Q'){return false;}}return true;}
}
总结:
本题是我们解决棋盘问题的第一道题目。
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手,可能知道要用回溯法,但也不知道该怎么去搜。
这里我明确给出了棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,这样就可以套进回溯法的模板里了。
大家可以在仔细体会体会!
更多推荐
代码随想录Day25 回溯算法 LeetCode T51 N皇后问题
发布评论