LeetCode 51. N-Queens

51. N-Queens

Difficulty:: Hard

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution

Language: Java

使用Set存储已有位置 50%

class Solution {
    
    private char[] boardRow;
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        boardRow = new char[n];
        Arrays.fill(boardRow, '.');
        // 0 for row, 1 for diagonal，2 for right lean diagonal
        Set<Integer>[] sets = (Set<Integer>[])new HashSet[3];
        for (int i = 0; i < sets.length; i++) {
            sets[i] = new HashSet<>();
        }
        dfsHelper(n, sets, new int[n], 0, result);
        return result;
    }
    
    private void dfsHelper(int n, Set<Integer>[] sets, int[] cur, int row, List<List<String>> result) {
        if (row >= n) {
            result.add(convert(cur));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!sets[0].contains(col) && !sets[1].contains(row + col) && !sets[2].contains(row - col)) {
                sets[0].add(col);
                sets[1].add(row + col);
                sets[2].add(row - col);
                cur[row] = col;
                dfsHelper(n, sets, cur, row + 1, result);
                sets[0].remove(col);
                sets[1].remove(row + col);
                sets[2].remove(row - col);
            }
        }
    }
    
    private List<String> convert(int[] cur) {
        List<String> res = new ArrayList<>();
        for (int i : cur) {
            boardRow[i] = 'Q';
            res.add(new String(boardRow));
            boardRow[i] = '.';
        }
        return res;
    }
}

使用数组存储已有位置 96%

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        List<List<Integer>> lines = new ArrayList<>();
        // 因为有 2 * n 个斜行
        boolean[][] sets = new boolean[3][n * 2 + 1];
        dfsHelper(n, lines, 0, new ArrayList<>(), sets);
        parseResult(lines, result, n);
        return result;
    }
    
    private void dfsHelper(int n, List<List<Integer>> lines, int index, List<Integer> line, boolean[][] sets) {
        if (index == n) {
            lines.add(new ArrayList<>(line));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 防止出现负数
            int left = index - i + n;
            int right = index + i;
            if (sets[0][i] || sets[1][left] || sets[2][right]) {
                continue;
            }
            line.add(i);
            sets[0][i] = true;
            sets[1][left] = true;
            sets[2][right] = true;
            dfsHelper(n ,lines, index + 1, line, sets);
            line.remove(line.size() - 1);
            sets[0][i] = false;
            sets[1][left] = false;
            sets[2][right] = false;
        }
    }
    
    private void parseResult(List<List<Integer>> lines, List<List<String>> result, int n) {
        char[] lineChars = new char[n];
        Arrays.fill(lineChars, '.');
        for (List<Integer> line : lines) {
            List<String> one = new ArrayList<>();
            int prev = 0;
            for (int col : line) {
                lineChars[prev] = '.';
                lineChars[col] = 'Q';
                one.add(new String(lineChars));
                prev = col;
            }
            lineChars[prev] = '.';
            result.add(one);
        }
    }
}