51. N 皇后（回溯算法）

àì夳堔傛蜴生んèń 2023-10-05 19:46 34阅读 0赞

#### 51. N 皇后 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

我们先来简化一下题目：棋盘中皇后可以攻击同一行、同一列,或者左上、左下、右上、右下四个方向的任意单位。现在给你一个NxN的棋盘,让你放置N个皇后,使得它们不能互相攻击,返所有合法的结果。

这题只需要套回溯算法的模板即可。

## 代码 ##

class Solution {
        
        //保存结果
        List<List<String>> res = new ArrayList<>();
    
        public List<List<String>> solveNQueens(int n) {
        
            char[][] board = new char[n][n];//棋盘
            //初始化棋盘
            for (char[] item : board) {
        
                Arrays.fill(item, '.');
            }
            backtrack(board, 0);
            return res;
        }
    
        /*
        路径：borad中小于row的哪些行都已经被放置了皇后，就相当于已经被选择过的列表
        选择列表：第row行中的所有列，都可以用来放置皇后
        结束条件：row超过board的最后一行，证明棋盘满了
        */
        public void backtrack(char[][] board, int row) {
        
            //触发了结束条件,直接把填好的棋盘放入res中
            if (row == board.length) {
        
                res.add(turn(board));
                return;//一定不能忘记，否则无法结束
            }
    
            int columns = board[0].length;
            for (int col = 0; col < columns; col++) {
        //遍历选择列表
                //排除不合法的选择
                if (!isValid(board, row, col)) {
        
                    continue;
                }
                //把选择 加入到路径
                board[row][col] = 'Q';
                //进入下一行决策
                backtrack(board, row + 1);
                //撤销选择
                board[row][col] = '.';
            }
        }
    
        public boolean isValid(char[][] board, int row, int col) {
        
            int n = board.length;
    
            //看当前列是否已经有皇后了
            for (int i = 0; i < row; i++) {
        
                if (board[i][col] == 'Q') {
        
                    return false;
                }
            }
    
            //检查右上方是否有皇后
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        
                if (board[i][j] == 'Q') {
        
                    return false;
                }
            }
            //检查左上方是否有皇后
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        
                if (board[i][j] == 'Q') {
        
                    return false;
                }
            }
    
            //我们不用检测当前行、列以下的棋盘，因为是从上往下开始填的
            return true;//没有冲突
        }
    
        /**
         * 用来做类型转换
         *
         * @param board
         * @return
         */
        public List<String> turn(char[][] board) {
        
            List<String> target = new LinkedList<>();
            for (char[] i : board) {
        
                StringBuffer sb = new StringBuffer();
                for (char j : i) {
        
                    sb.append(j);
                }
                target.add(sb.toString());
            }
            return target;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210216181047631.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70