前言
又来到了我们的周末,今天我们挑战一道困难题:N皇后问题,相信大家都玩过一个经典的小游戏:8皇后
游戏规则是:在一个n*n的棋盘上,放置nge 皇后,要求每个皇后所在的一排一列并且对角线都不能存在皇后,放满n个皇后即为胜利.
LeetCode T51 N皇后问题
游戏链接:八皇后游戏 (gitee.io)
题目思路:
这题我们仍然使用回溯算法解决问题
首先我们画出树状图,我们以三皇后举例(无解)
回溯三部曲:
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合法性判断
这里我们需要判断棋盘皇后的落点是否合法,我们只需要比较竖着,和两个对角线是否存在即可,竖着从0遍历到该节点即可,两个对角线别忘记给定边界限制.
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循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。
大家可以在仔细体会体会！
