代码随想录Day25 回溯算法 LeetCode T51 N皇后问题

编程入门行业动态更新时间:2024-10-26 10:33:30

代码随想录Day25 回溯算法 LeetCode T51 N<a href=https://www.elefans.com/category/jswz/34/1757954.html style= 皇后问题"/>

代码随想录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;}
}