spring自定义注解

51. N 皇后

难度困难637

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

上图为 8 皇后问题的一种解法。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

通过次数82,902

提交次数113,295

在真实的面试中遇到过这道题？

题解

class Solution {
    public List<List<String>> solveNQueens(int n) {
        //先构建棋盘
        char[][] chess = new char[n][n];
        for(int i = 0; i <n; i++){
            for(int j = 0; j <n;j++){
                chess[i][j] = '.';
            }
        }
        List<List<String>> res = new ArrayList<>();
        traceBack( res, chess, 0);
        return res;
    }
    //回溯
    void traceBack(List<List<String>> res, char[][] chess, int row){
        if( row == chess.length){
            res.add( construct(chess));
            return;
        }
        for(int col = 0; col < chess.length; col++){
            if( valid(chess, row, col)){
                chess[row][col] = 'Q';
                traceBack(res, chess, row+1);
                chess[row][col] = '.';
            }
        }
    }

    //row 表示行， col  表示列 valid函数表示当前的格子能否放入Q
    boolean valid( char[][] chess, int row, int col){
        //判断列有没有Q
        for(int i = 0 ; i < row ; i++){
            if(chess[i][col] =='Q'){
                return false;
            }
        }
        //判断右上角有没有Q
        for(int i = row - 1, j = col +1 ; i >= 0 && j < chess.length; i--, j++){
            if(chess[i][j] =='Q'){
                return false;
            }
        }
        //判断左上角有没有Q
        for(int i = row - 1, j  = col -1; i>= 0 && j >=0; i--, j--){
            if(chess[i][j] =='Q'){
                return false;
            }
        }
        return true;
    }

    //把数组转为list
    List<String> construct(char[][] chess){
        List<String> temp = new ArrayList<>();
        for(int i =0; i < chess.length; i++){
            temp.add(new String(chess[i]));
        }
        return temp;
    }


}

---

参考:

N皇后，经典回溯算法（图文详解）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com