代码随想录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
        {
            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
        {
            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 list = new ArrayList<>();
 
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

题目代码:

class Solution {
    List> res = new ArrayList<>();
    public List> 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
        {
            if(isVaild(r,i,n,chessboard))
            {
                chessboard[r][i] = 'Q';
                backtracking(chessboard,n,r+1);
                chessboard[r][i] = '.';
            }
        }
       
    }
    //定义接口
      public List Array2List(char[][] chessboard) {
        List 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
        {
            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循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

大家可以在仔细体会体会！