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.
use dfs
time = O(n! * n^2), space = O(n)
class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<>(); Set<Integer> usedCols = new HashSet<>(); Set<Integer> diag1 = new HashSet<>(); Set<Integer> diag2 = new HashSet<>(); dfs(usedCols, diag1, diag2, 0, n, new ArrayList<>(), res); return res; } private void dfs(Set<Integer> usedCols, Set<Integer> diag1, Set<Integer> diag2, int level, int n, List<Integer> pos, List<List<String>> res) { if(level == n) { List<String> list = new ArrayList<>(); for(int idxQ : pos) { StringBuilder sb = new StringBuilder(); for(int i = 0; i < n; i++) { if(i == idxQ) { sb.append(‘Q‘); } else { sb.append(‘.‘); } } list.add(sb.toString()); } res.add(list); return; } for(int j = 0; j < n; j++) { if(isValid(level, j, usedCols, diag1, diag2)) { pos.add(j); usedCols.add(j); diag1.add(j + level); diag2.add(level - j); dfs(usedCols, diag1, diag2, level + 1, n, pos, res); pos.remove(pos.size() - 1); usedCols.remove(j); diag1.remove(j + level); diag2.remove(level - j); } } } private boolean isValid(int row, int col, Set<Integer> usedCols, Set<Integer> diag1, Set<Integer> diag2) { return !usedCols.contains(col) && !diag1.contains(row + col) && !diag2.contains(row - col); } }
原文：https://www.cnblogs.com/fatttcat/p/11406800.html