八皇后1

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展

示例:

 输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
通过次数9,283提交次数12,235

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/eight-queens-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对角线的计算方式是

主对角线的计算方式是：row-cloumn 在主对角线上的点的坐标的row-column的差值相同

副对角线的计算方式是：row+column 在副对角线上的点的坐标的row+column的差值相同

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resList = new ArrayList<>();

        int[] queens = new int[n];
        Set<Integer> column = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagnoals2 = new HashSet<>();

        backtrack(resList, queens, n, 0, column, diagonals1, diagnoals2);
        return resList;
    }

    public void backtrack(List<List<String>> resList, int[] queens, int n, int row, Set<Integer> column, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            resList.add(board);
            return;
        }

        for (int i = 0; i < n; i++) {
            // 列存在
            if (column.contains(i)) continue;
            // 主对角线存在
            int diag1 = row - i;
            if (diagonals1.contains(diag1)) continue;
            // 副对角线存在
            int diag2 = row + i;
            if (diagonals2.contains(diag2)) continue;


            queens[row] = i;
            column.add(i);
            diagonals1.add(diag1);
            diagonals2.add(diag2);
            backtrack(resList, queens, n, row + 1, column, diagonals1, diagonals2);
            queens[row] = -1;
            column.remove(i);
            diagonals1.remove(diag1);
            diagonals2.remove(diag2);
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }

        return board;
    }
}

赏

谢谢你请我吃糖果

微信