算法从入门到放弃——第四期 岛屿_u014783007的博客-CSDN博客

之前有写了一篇岛屿的问题，今天来看一个岛屿的变种，N皇后

题目如下

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

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

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

示例 1： 

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

这题在leetcode是困难，但是做过岛屿之后，明眼一看感受是能做， 虽然返回奇奇怪怪，但是本质还是岛屿问题，岛屿问题模板就是bfs岛屿块，脑海里两层循环有了，之后就是放“Q”，放第一个肯定放哪都行，放第二个就要验证能不能放了，而验证的方法需要考虑一下，这里如果我们是从左往右，从上到下放，那么我需要检测我的上方，左方，左上，右上四个角度是不是已经放过“Q”了即可，如果不满足条件就回溯。

好像结束了，没错，过程就是这么简单，然后只要代码实现就可以了

    public static void setChess(String[][] chess, int row, List<List<String>> result) {
        if (row == chess.length) {
            List<String> ss = new ArrayList<>();
            for (int i = 0; i < chess.length; i++) {
                String s = "";
                for (int j = 0; j < chess[0].length; j++) {
                    s+=chess[i][j];
                }
                ss.add(s);
            }
            result.add(new ArrayList<>(ss));
            ss.clear();
            return;
        }

        for (int col = 0; col < chess[0].length; col++) {
            if (positionIsValid(chess, row, col)) {
                chess[row][col] = "Q";
                setChess(chess, row + 1, result);
                chess[row][col] = ".";
            }
        }
    }

    public static boolean positionIsValid(String[][] chess, int row, int col) {
        //注意外层是从上到下，从左到右遍历的
        //那么对于当前节点而言，有可能填过Q区域，只能在上，左，右上，左上四个方向上
        for (int i = 0; i < row; i++) {
            if (chess[i][col].equals("Q")) {
                return false;
            }
        }
        for (int i = 0; i < col; i++) {
            if (chess[row][i].equals("Q")) {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < chess[0].length; i--, j++) {
            if (chess[i][j].equals("Q")) {
                return false;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j].equals("Q")) {
                return false;
            }
        }
        return true;
    }

这种题目一般不会作为面试出现，总体而言为了考察递归和回溯，但是需要很多额外的方法去体现算法，这不太符合面试的要求，当然熟练掌握回溯做这道题应该也不会有难度