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.."]]

这道题就是求解n皇后问题。皇后不能出在同一条直线、竖线以及斜线上。

想法就是　　1、建立一个n的数组pos[n]，表示第i行的皇后放在第pos[i]处。

　　　　　　2、然后需要在第num个放皇后的时候，需要依次判断前num个数字（i :  0 --> num-1），这个位置的数字不能与pos[i]，pos[i]-(num-i)，pos[i]+(num-i)这三个数字相同，判断完之前的所有数字之后，就可以放入该数字了。

结果是3ms。算是还可以的成绩。

public class Solution {    public List
     
      
       > solveNQueens(int n) {        List
       
        
         > result = new ArrayList
         
          
           >(); int[] pos = new int[n]; putQueen(pos,0,result); return result; } public void putQueen(int[] pos,int num,List
           
            
             > result){ if( num == pos.length ){ List
             
               res = new ArrayList
              
               (); char[] ans = new char[pos.length]; for( int j =0;j
               
                = 0) exi[pos[i]-(num-i)] = 1; if( pos[i]+num-i < pos.length) exi[pos[i]+num-i] = 1; } for( int i = 0; i
               
              
             
            
           
          
         
        
       
      
     

52题

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

这题和上面的一样，就是求出解的个数。

代码就是简单修改一下即可。

public class Solution {    public int totalNQueens(int n) {        int[] pos = new int[n];        return putQueen(pos,0,0);    }	public int putQueen(int[] pos,int num,int total){		if( num == pos.length ){			return total+1;		}		int[] exi = new int[pos.length];		for( int i = 0;i
     
      = 0)				exi[pos[i]-(num-i)] = 1;			if( pos[i]+num-i < pos.length)				exi[pos[i]+num-i] = 1;		}				for( int i = 0; i