转载：

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.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

java解法如下所示：

public class Solution {    public void dfs(List
     
      
       > res, List
       
         list, Set
        
          col, Set
         
           diag1, Set
          
            diag2, int row, int n){ if(row==n){ res.add(new ArrayList
           
            (list)); return; } //遍历该行的所有列 for(int i=0;i
            
             > solveNQueens(int n) { List
             
              
               > res = new ArrayList
               
                
                 >(); if(n==0) return res; Set
                 
                   col = new HashSet
                  
                   (); //列集 Set
                   
                     diag1 = new HashSet
                    
                     (); //正对角线集 Set
                     
                       diag2 = new HashSet
                      
                       (); //副对角线集 List
                       
                         list = new ArrayList
                        
                         (); //用于存放每一种情况 dfs(res, list, col, diag1, diag2, 0, n); return res; }}