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 the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
use dfs / backtracking
time = O(n!), space = O(n)
class Solution { Set<Integer> usedCols = new HashSet<>(); Set<Integer> diag1 = new HashSet<>(); Set<Integer> diag2 = new HashSet<>(); int count = 0; public int totalNQueens(int n) { helper(0, n); return count; } private void helper(int row, int n) { if(row == n) { count++; return; } for(int col = 0; col < n; col++) { if(isValid(row, col)) { usedCols.add(col); diag1.add(row + col); diag2.add(row - col); helper(row + 1, n); usedCols.remove(col); diag1.remove(row + col); diag2.remove(row - col); } } } private boolean isValid(int row, int col) { return !(usedCols.contains(col) || diag1.contains(row + col) || diag2.contains(row - col)); } }
原文：https://www.cnblogs.com/fatttcat/p/11406816.html